Codeforces Round 906 (Div. 2--ABC)

A.Doremy's Paint 3

题目

一个元素全为整数的数组，如果满足相邻两个元素和相同，我们就认定此数组is good。给定一个长度为n的数组a，可以任意改变元素顺序，判定数组a是否is good。

输入

首行t测试数据数量，

每组数据第一行n，数组长度，

第二行数组a的n个数字，

输出

"YES"或“NO”，判定a是否is good。

解析

 相邻元素和相同，等价于数组中奇数位置元素相同，偶数位置元素相同。故数组中最多出现两种元素，即奇数位和偶数位数字不同的情况。同时奇数位数字出现个数最多比偶数位数字出现次数多一，否则组不成数组。故，只需遍历数组统计奇偶位数字出现次数即可，时间复杂度。

代码

 
T = int(input().strip())
 
for t in range(T):
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    s = set(a)
    if len(s) > 2:
        print("NO")
    elif len(s) == 2:
        odd = a.count(a[0])
        even = n - odd
        if abs(odd - even) <= 1:
            print("YES")
        else:
            print("NO")
    else:#奇偶位数字相同
        print("YES")

B.Qingshan Loves Strings

题目

 一个字符串s，一个字符串t，由0和1组成。定义一个字符串is good需要满足相邻字符不同，如1或101或0101字符串is good。判断通过将t插入到s的任意位置，是否可以让s is good。

输入

首行t测试数据数量，

每组数据第一行s长度n和t长度m，

第二行s

第三行t

输出

YES or NO

解析

 如果s不满足is good，说明s中有连续的1或0，能够将连续1分开的只有以0开头和结尾的t，能够将连续0分开的只有以1开头和结尾的t，故答案为YES的只有上述三种情况。时间复杂度粗略估计，绰绰有余。

代码

 
T = int(input().strip())
 
def check(s):
    l = 1
    for c in s:
        if c == l:
            return False
        else:
            l = c
    return True
 
for k in range(T):
    n, m = map(int, input().strip().split())
    s = input().strip()
    t = input().strip()
 
    if check(s): # 遗漏点
        print("YES")
    else:
        if check(t):
            if t[0] == t[-1] == "0" and s.count("00") == 0:
                print("YES")
            elif t[0] == t[-1] == "1" and s.count("11") == 0:
                print("YES")
            else:
                print("NO")
        else:
            print("NO")

C.Qingshan Loves Strings 2

题目

字符串s由0和1组成，定义一个字符串is good需要满足：第一个与倒数第一个字符不同，第二个与倒数第二个不同，依次类推。 可以执行的操作只有一个，向s任意位置插入“01”字符串，判断字符串s是否能在300次以内的操作满足is good条件。

输入

首行t测试数据数量，

每个测试样例首行为字符串s的长度n，

第二行字符串s

输出

对于每个样例，如果s不可能成为good，输出“-1”

否则第一行输出操作个数p

第二行输入插入“01”字符的位置，0表示插入s开头，其他数值i表示插入到第i个字符之后。

解析

依次对比字符串首位字符，如果不同，则去掉首位字符，查看得到的新字符串的首位。如果相同，两种情况，同为1，则要在开头添加“01”；同为“0”，则要在末尾添加“01”。依次判断保存添加结果即可，需注意插入操作对插入位置的影响，其他为模拟过程。

代码

from collections import deque
 
def solve():
    n = int(input().strip())
    q = deque(input().strip())
 
    cnt0 = cnt1 = 0
    for c in q:
        if c == "1":
            cnt1 += 1
        else:
            cnt0 += 1
 
    if cnt0 != cnt1:
        print("-1")
        return
 
    res = list()
    d = 0
 
    while len(q) > 1:
        if q[0] == q[-1]:
            if q[0] == "0":
                q.append("0")
                q.append("1")
                res.append(n-d)
            else:
                q.appendleft("1")
                q.appendleft("0")
                res.append(d)
            n += 2
 
        while len(q) > 1 and q[0] != q[-1]:
            q.pop()
            q.popleft()
            d += 1
 
    print(len(res))
    for r in res:
        print(r, end=" ")
    print()
 
K = int(input().strip())
 
for k in range(K):
    solve()
        

 尾

这次B提交错误两次，C未做完没提交，跟上次差不多。将原题目贴出来，B提交错误的两次是没理解对题目意思，英文的阅读理解还是有一定问题的。

比如

 可以插入多次这种字眼会忽略掉，还有

开始以为1，101，0101是一个完整地数字，后来才发现这是三个例子1和101和0101，愁了半天。还是要慢慢读题目，然后看题目给的例子，最后有些题目末尾有作者写的note，一定要好好看，确认自己理解无误。不然提交错了，白白扣分。不用着急做后边的题，反正也不会，争取不提交错误就行。

 CF灰407——>CF灰692