Codeforces Round #786

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<<sep<<0<<endl;
        else cout<<1<<sep<<y/x<<endl;
	}
	return;
}

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<string,int> 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<<ma[s]<<endl;
	}
	return;
}

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<<s1.length());
		else if(s2.length()==1)ans=1;
		else ans=-1;
		cout<<ans<<endl;
	}
	return;
}

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"<<endl;
		else cout<<"No"<<endl;
	}
	return;
}

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])<max(a[i-2],a[i-3]):
                    print('NO')
                    f=1
                    break
                i-=2
        else:
            first=a.pop(0)
            if first>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<b)swap(a,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<<ans<<endl;
	return;
}

---

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<<ans<<endl;
	}
	return;
}