codeforces日常练习0604

Coloring

题目可以简单理解为有ceil(n/k)个盒子，要求往里面放置颜色不同的球。

根据题意就要使用鸽巢原理，令c=ceil(n/k)，如果有一个颜色的出现的次数大于c，那么由鸽巢原理可知必然会出现一个盒子由两种及以上的颜色，因此无解。

但是即使没有违反该条件的球，也不代表有解，假设最后一个盒子中的球(装球最少的盒子)数量为y，而出现次数为c的颜色的个数为x，如果x>y，要么违反最少的盒子的球的数量要么装到其他盒子中(一个盒子中就会出现两种颜色及以上)，因此要多判断一次。

for _ in range(R()):
    n,m,k=RR()
    nums=RR()
    # 排序
    nums.sort()
    # 计数
    memo=Counter(nums)
    # 组数
    c=ceil(n/k)
    # 如果一种颜色出现次数大于组数，那么必然有一个组会出现相同的颜色
    if nums[-1]>c:
        print('NO')
    else:
        # 最后一段的个数
        tmp=n%k
        # 可能取模为0的长度为k
        if not tmp:tmp=k
        # 如果出现次数为c的颜色的个数大于最后一段的长度，那么必然有一组出现次数大于1
        if memo[c]>tmp:
            print('NO')
        else:
            print('YES')

Password Cracking

考虑最简单的变化——在左侧添加第二个字符，在右侧添加倒数第二个字符。

那么令原字符串为Tcd，其中cd是最后两个字符，那么有变化Tcd→Tcdc→dcT′Tcdc→cdcT′Tcdc

for _ in range(R()):
    n,m,k=RR()
    nums=RR()
    # 排序
    nums.sort()
    # 计数
    memo=Counter(nums)
    # 组数
    c=ceil(n/k)
    # 如果一种颜色出现次数大于组数，那么必然有一个组会出现相同的颜色
    if nums[-1]>c:
        print('NO')
    else:
        # 最后一段的个数
        tmp=n%k
        # 可能取模为0的长度为k
        if not tmp:tmp=k
        # 如果出现次数为c的颜色的个数大于最后一段的长度，那么必然有一组出现次数大于1
        if memo[c]>tmp:
            print('NO')
        else:
            print('YES')

Row Major

规定了对于n的因数d，不能出现两个距离为d的位置字符相同，在此基础上最小化不同种类的字符数

为了最小化，那么就找最小的不属于n的因数的正整数x，每隔x去相同的字符，也就是周期为x。

for _ in range(R()):
    n=R()
    if n==1:
        print('a')
        continue
    x=2
    while n%x==0:
        x+=1

    ans=[]
    for i in range(n):
        ans.append(chr(ord('a')+i%x))
    print("".join(ans))