Codeforces Round #786 题解
邀请到大师为大家带来优质的python解答！（比哈特）
TOC
- A.Number Transformation
- B.Dictionary
- C.Infinite Replacement
- D.A-B-C Sort
- E.Breaking the Wall
- F.Desktop Rearrangement
A.Number Transformation
Problem
寻找a，b满足 x b a = y → a = 1 , b = y / / x xb^a=y rightarrow a=1,b=y//x xba=y→a=1,b=y//x
如果无法整除则无解
cpp-version
int t,x,y;
inline void Main()
{
cin>>t;
while(t--)
{
cin>>x>>y;
if(y%x)cout<<0<
python3-version
cnt=int(input())
i=1
while i<=cnt:
xy=input().split()
x=int(xy[0])
y=int(xy[1])
if y%x==0:
print(1,int(y/x))
else:
print(0,0)
i+=1
B.Dictionary
Problem
查询串在字典中的位置，字典由2位小写字母排列组合（除去2位相等的情况）组成
字典元素650个，枚举存储即可
cpp-version
python用久了，cpp的串操作忘却干净。另一方面这题用python应该舒适一点
int t;
string s;
char nmd[2];
map ma;
inline void Main()
{
int cnt=0;
rep(i,0,25)rep(j,0,25)
{
nmd[0]='a'+i,nmd[1]='a'+j;
if(i==j)continue;
s=nmd;
ma[s]=++cnt;
}
cin>>t;
while(t--)
{
cin>>s;
cout<
python3-version
cnt=int(input())
i=1
while i<=cnt:
ab=input()
a=ab[0]
b=ab[1]
one=(ord(a)-ord('a'))
if ord(b)>ord(a):
two=ord(b)-ord('a')-1
else:
two=ord(b)-ord('a')
print(one*25+two+1)
i+=1
C.Infinite Replacement
Problem
长为len的s串由字符a组成，可将s串中字符a替换成t串。考虑如下三种情况：
- t串不包含字符a。此时s串每一位均有替换or不替换两种状态，答案为
2
l
e
n
2^{len}
2len
- t串仅包含字符a。此时答案为1
- t串包含且不仅包含字符a。此时可以进行无穷次替换，答案为-1
cpp-version
int t,ans;
string s1,s2;
inline void Main()
{
cin>>t;
while(t--)
{
cin>>s1>>s2;
bool f=0;
rep(i,0,s2.length()-1)f|=s2[i]=='a';
if(f==0)ans=(1ll<
python3-version
python的一些功能确实很舒适
cnt=int(input())
i=1
while i<=cnt:
s=input()
t=input()
if t=='a':
print(1)
elif 'a' in t:
print(-1)
else:
print(pow(2,len(s)))
i+=1
D.A-B-C Sort
Problem
考虑题目操作的性质，可以发现本质上只有相邻两位发生交换的可能。准确来说，从A序列变为C序列，只有
(
n
,
n
−
1
)
,
(
n
−
2
,
n
−
3
)
,
.
.
.
,
(
2
,
1
)
o
r
(
3
,
2
)
,
(
1
)
(n,n-1),(n-2,n-3),...,(2,1) or (3,2),(1)
(n,n−1),(n−2,n−3),...,(2,1)or(3,2),(1)的位置对可能发生互换
以
a
n
−
2
,
a
n
−
3
a_{n-2},a_{n-3}
an−2,an−3举例：
当从A中拿出
a
n
−
2
,
a
n
−
3
a_{n-2},a_{n-3}
an−2,an−3放入B时，由于B中存在偶数个元素，故一定会放在
a
n
,
a
n
−
1
a_n,a_{n-1}
an,an−1中间，其顺序任意，此后的
a
n
−
4
,
a
n
−
5
.
.
.
a_{n-4},a_{n-5}...
an−4,an−5...一定会放在
a
n
−
2
,
a
n
−
3
a_{n-2},a_{n-3}
an−2,an−3的中间
根据这一特点，可以发现在从B中拿取元素放入C时，当拿到
a
n
−
2
,
a
n
−
3
a_{n-2},a_{n-3}
an−2,an−3时，
a
n
−
4
,
a
n
−
5
.
.
.
a_{n-4},a_{n-5}...
an−4,an−5...一定已经被拿出。且此时B中元素数为偶数，故拿取
a
n
−
2
,
a
n
−
3
a_{n-2},a_{n-3}
an−2,an−3的顺序可以任意，可能产生互换
因此只要判断排序后的不降序列能否由原序列使用该操作变换得到即可
cpp-version
int t,n,a[N],b[N];
inline void Main()
{
cin>>t;
while(t--)
{
cin>>n;
rep(i,1,n)
{
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+n+1);
int flag=true;
for(int i=n;i>1;i-=2)
{
if(a[i]==b[i]&&a[i-1]==b[i-1])continue;
if(a[i]==b[i-1]&&a[i-1]==b[i])continue;
flag=false;break;
}
if(flag)cout<<"Yes"<
python3-version
cnt=int(input())
j=1
while j<=cnt:
l=int(input())
tmp=input().split()
if l==1 or l==2:
print('YES')
else:
a=[]
for aa in tmp:
a.append(int(aa))
f=0
if len(a)%2==0:
i = len(a) - 1
while i>=3:
if min(a[i],a[i-1])min(a[0],a[1]):
print('NO')
f=1
else:
i = len(a) - 1
while i >= 3:
if min(a[i], a[i - 1]) < max(a[i - 2], a[i - 3]):
print('NO')
f = 1
break
i -= 2
if f==0:
print('YES')
j+=1
E.Breaking the Wall
Problem
武器对
x
x
x位置的一次攻击可以对x位置造成2伤害，对
x
−
1
、
x
+
1
x-1、x+1
x−1、x+1位置造成1伤害(如果存在的话)，题目要求打穿两个洞需要的最少攻击次数
分析可知，打穿两个洞的答案可能由以下情况得出：
- 独立攻击
x
1
,
x
2
x_1,x_2
x1,x2位置，直到打穿。击打最弱的两块即可(两块相邻的情况会在下面包含)
- 攻击某个
x
x
x位置，使得
x
−
1
,
x
+
1
x-1,x+1
x−1,x+1位置被打穿。枚举每个x即可
- 攻击位置
x
,
x
+
1
x,x+1
x,x+1各若干次，直到打穿。
对于第三种情况，假设两个位置中数值高者为a，低者为b：
- 如果
a
>
2
b
a>2b
a>2b，则攻击a的过程中，b会被击穿，因此此时答案即为将a击穿的开销。
- 如果
a
≤
2
b
a leq 2b
a≤2b，则对a攻击
t
=
a
−
b
t=a-b
t=a−b次之后，两者会相等。此时对a、b各攻击一次，两者会受到3的伤害。进行若干次之后会出现2、1、0的情况，简单分析即可得答案对应2、1、0
然后模拟就好了，需要考虑向上取整的问题
cpp-version
int n,a[N];
inline int func(int a,int b)
{
if(a=2*b)return (a+1)/2;
int t=b-(a-b);
return (a-b)+2*(t/3)+t%3;
}
inline void Main()
{
cin>>n;
rep(i,1,n)cin>>a[i];
int ans=INF;
rep(i,1,n-1)ans=min(ans,func(a[i],a[i+1]));
if(n>2)
{
rep(i,2,n-1)ans=min(ans,min(a[i-1],a[i+1])+(max(a[i-1],a[i+1])-min(a[i-1],a[i+1])+1)/2);
sort(a+1,a+n+1);
ans=min(ans,(a[1]+1)/2+(a[2]+1)/2);
}
cout<
F.Desktop Rearrangement
Problem
赛后复现，赛时时间不太够
桌面整理规则与常见的电脑图标放置规则一致，将一个图标移动到任意位置视为一次操作，求每次修改(增加or删除图标)后整理桌面的最小操作次数
其实将桌面拉伸成一维更好理解，最后整理好的桌面图标会占据连续前缀，故没有处于这个区域的图标会消耗一次操作进行整理
对于每次修改操作，只需维护图标数量，以及修改处、边界处对答案产生的影响即可
cpp-version
int q,n,m,cnt,ans;
char tab[N][N],que[N*N];
inline void Main()
{
cin>>n>>m>>q;
rep(i,1,n)cin>>tab[i]+1;
rep(i,1,n)rep(j,1,m)
{
if(tab[i][j]=='*')++cnt;
que[(j-1)*n+i]=tab[i][j];
}
rep(i,cnt+1,n*m)if(que[i]=='*')++ans;
while(q--)
{
int x,y;cin>>x>>y;
int now=(y-1)*n+x;
if(que[now]=='*')
{
que[now]='.';
if(now>cnt)--ans;
if(now!=cnt&&que[cnt]=='*')++ans;
--cnt;
}
else
{
que[now]='*';
++cnt;
if(now>cnt)++ans;
if(now!=cnt&&que[cnt]=='*')--ans;
}
cout<
