Codeforces Round 925 (Div. 3)
A. Recovering a Small String
考点：模拟
思路：
因为数据范围非常的小，可以直接三个for循环暴力解决。
复杂度：O(![]()
)
import sys input = sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) b=[0]*3 for i in range(1,27): for j in range(1,27): for k in range(1,27): if i+j+k==n: b[2]=chr(ord('a')+(i-1)) b[1]=chr(ord('a')+(j-1)) b[0]=chr(ord('a')+(k-1)) break print(b[0],end='') print(b[1], end='') print(b[2], end='') print()B. Make Equal
考点：前缀，贪心
思路：
因为题目要求所有数都要相等，那么我们就先算每个瓶子平均要有的水量，然后看前缀是否大于等于当前的平均水量。只要有一个小于那就是不满足。
复杂度：O(n)
import sys input = sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) a=list(map(int,input().split())) s=sum(a)//n st=0 ok=True for i in range(n-1): st+=a[i] if st<(i+1)*s: ok=False break if ok: print("Yes") else: print("No")C. Make Equal Again
考点：模拟
思路：
由题意可知，只可能看第一个数和最后一个数，数他们两个分别有多少连续的数，然后用总长度相减取最小值输出即可。
复杂度：O(n)
import sys input = sys.stdin.readline t=int(input()) for _ in range(t): n=int(input()) a=list(map(int,input().split())) ks=a[0] js=a[-1] min_z=10**18 cnt1 = 1 for i in range(1,n): if ks==a[i]: cnt1+=1 else: break min_z=min(n-cnt1,min_z) cnt2=1 for i in range(n-2,-1,-1): if a[i]==js: cnt2+=1 else: break min_z = min(n - cnt2, min_z) min_z = min(n - cnt1, min_z) if ks==js: min_z=min(min_z,n-cnt1-cnt2) if min_z<0: min_z=0 print(min_z)D. Divisible Pairs
考点：数论，哈希表
思路：
将题目转换一下：
，可以转换为
。
，可以转换为
。
然后用哈希表统计一下输出即可。
复杂度：O(n)
import sys input = sys.stdin.readline t=int(input()) for _ in range(t): n,x,y=map(int,input().split()) a=list(map(int,input().split())) cnt=0 mp={} for v in a: rx=v%x ry=v%y need=((-rx)%x,ry) cnt+=mp.get(need,0) key=(rx,ry) mp[key]=mp.get(key,0)+1 print(cnt)E. Anna and the Valentine's Day Gift
考点：博弈论，贪心
思路：
由题目可知，只有Anna可以将数的位数变小，Sasha只能让数组中的元素个数变少，但是赢的条件是跟位数有关。
所以我们可以先把零0个数用数组统计出来，然后降序排序。Anna想赢肯定是要优先将0多的数给反转，Sasha想赢也要优先把零多的合并。
也就是说他们两个都会选零多的。又因为他们是一人选一次，所以Anna选奇数次。
于是我就可以先算数组字符的总长度，然后减去Anna奇数次选的零的数量，看这个剩余的结果是不是大于m就行了。
复杂度：O(n)
import sys input = sys.stdin.readline sys.setrecursionlimit(10000) t=int(input()) def pd(a): cnt=0 n=len(a) for i in range(n-1,-1,-1): if a[i]=='0': cnt+=1 else: break return cnt for _ in range(t): n,m=map(int,input().split()) a=list(input().split()) zh=0 b=[] for v in a: zh+=len(v) b.append(pd(v)) b.sort(reverse=True) for i in range(0,n,2): zh-=b[i] if zh>m: print("Sasha") else: print("Anna")