On this page

26 Winter Holiday Round 2 Review

https://ac.nowcoder.com/acm/contest/120562
本文给出代码在 nowcoder 使用 Python3 编译器均可 AC

A 比赛安排

题目分析

给定 3 个正整数 a,b,ca,b,c，判断能否将这些数排成一个序列（其中 aa 个 A 类元素，bb 个 B 类元素，cc 个 C 类元素），并且任意连续 3 个元素类型互不相同。

解题思路

为了满足任意连续 3 个元素互不相同，必须按照 ABC ABC ABC... 这样固定循环排列，需要 a=b=ca=b=c。

其末尾有 3 种情况：

  • ...ABC，完美循环，此时 a=b=ca=b=c
  • ...ABC AB，剩余 AB
  • ...ABC A，剩余 A

扩展地，对于 a,b,ca,b,c，设最小值为 min⁡(a,b,c)\min(a,b,c)。将每个都减去最小值后，剩余的（去 0）有 3 种情况：

  • []：说明完美循环
  • [1, 1]：说明有 2 种元素各多 1 个
  • [1]：说明只有 1 种元素多 1 个

其他情况都无法满足条件。

Code

import sys
input = sys.stdin.readline

def solve():
    arr = list(map(int, input().split()))
    mn = min(arr)
    arr = [x - mn for x in arr]
    arr = [x for x in arr if x != 0]
    if not arr:
        print("YES")
    elif arr == [1, 1]:
        print("YES")
    elif arr == [1]:
        print("YES")
    else:
        print("NO")

T = int(input().strip())
for _ in range(T):
    solve()

赛后分析（AI提示）

实际上，这道题有更简洁的解法。对于 a,b,ca,b,c，能够满足题意排列的充要条件是：max⁡(a,b,c)−min⁡(a,b,c)≤1\max(a,b,c) - \min(a,b,c) \leq 1

a=b=ca=b=c 时显然成立。如果 3 个数不完全相等，排列后剩余部分最多为 2 个元素（即 AB 或 A），这意味着最大值至多比最小值多 1。

优化逻辑：

def solve():
    arr = list(map(int, input().split()))
    print("YES" if max(arr) - min(arr) <= 1 else "NO")

B NCPC

题目分析

给定 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n。定义一种对决规则：任选两个不同元素 ai,aja_i, a_j，若 ai≠aja_i \neq a_j，则较小的元素被淘汰；若 ai=aja_i = a_j，则两者都被淘汰。重复此过程直到剩余 1 个元素。

对于每个位置 ii (1⩽i⩽n)(1 \leqslant i \leqslant n)，判断是否存在一种对决顺序，使得 aia_i 成为最终剩余的唯一元素。

解题思路

对决规则可以概述为：两两对决，小的淘汰，相等同归于尽。

最初分析可能会觉得，只有最大值才有机会获胜。这可能是误读题目为找到能使 aia_i 获胜的唯一最优解导致的，实际上是让你找到全部有机会获胜的元素 aia_i。

不过关键确实在于分析最大值（max⁡\max）的个数：

  1. max⁡\max 个数为奇数，例如：

    • 1 2 3 5
    • 1 2 3 5 5 5

    max⁡\max 个数大于 1 时，可以让 max⁡\max 两两对决，最后剩余的 max⁡\max 取胜。不难发现，此时所有 max⁡\max 都有机会获胜。

  2. max⁡\max 个数为偶数，且为全部元素，例如：

    • 5 5 5 5

    显然，所有元素都不能获胜。

  3. max⁡\max 个数为偶数，且不为全部，例如：

    • 1 2 3 6 6

    这一情形很容易被忽略，只考虑到 max⁡\max 两两对决，次最大值获胜。实际上还存在，取 1 个 max⁡\max 干掉所有非预期元素，只保留 1 个非最大值（如 1），最后和另一个 max⁡\max 同归于尽。

    因此所有非最大值都有机会获胜。

Code

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    mx = 0
    cnt = 0
    for x in arr:
        if x > mx:
            mx = x
            cnt = 1
        elif x == mx:
            cnt += 1
    if cnt % 2 != 0:
        for x in arr:
            print("1" if x == mx else "0", end='')
        print()
    elif cnt == n:
        print("0" * n)
    else:
        for x in arr:
            print("0" if x == mx else "1", end='')
        print()

T = int(input().strip())
for _ in range(T):
    solve()

I 01回文

题目分析

给定一个 n×mn \times m 的 01 矩阵。对于矩阵中的每个位置 (i,j)(i,j)，判断是否存在一条从 (i,j)(i,j) 出发到另一非起点位置 (x,y)(x,y) 的简单路径，使得路径上的元素序列构成回文串。

移动规则：每次只能移动到上下左右相邻的位置。

解题思路

注意：题目并没有规定为最短路径

首先，我们尝试列举回文串，试图找到规律（只列举从 0 开始的，另一情形反过来）：

  • 0 0
  • 0 0 0
  • 0 1 0
  • 0 0 0 0
  • 0 1 1 0
  • 0 0 0 0 0
  • 0 1 1 1 0
  • 0 1 0 1 0，可以发现必须由 0 开始至 0 结束。

再尝试放入矩阵中验证：

1 0 0 0     1 0 1 1
0 0 0 1     0 1 0 0

由于矩阵的所有位置都是连通的，所以只要存在至少 2 个相同的数值，就一定存在路径连通 2 个数值形成回文。

具体情形：

  1. 0 的个数（cnt0）＞ 2 且 1 的个数（cnt1）＞ 2：所有位置都可以形成回文
  2. 从 0 开始，cnt0 ≥2\geq 2，则该位置可以形成回文
  3. 从 1 开始，cnt1 ≥2\geq 2，则该位置可以形成回文

Code

import sys
input = sys.stdin.readline
write = sys.stdout.write

def solve():
    n, m = map(int, input().split())
    a = []
    cnt0 = 0
    for _ in range(n):
        tmp = list(map(int, input().strip()))
        cnt0 += tmp.count(0)
        a.append(tmp)
    cnt1 = n * m - cnt0

    out = []
    if cnt0 >= 2 and cnt1 >= 2:
        row = 'Y' * m + '\n'
        out.append(row * n)
    else:
        for i in range(n):
            row = []
            for j in range(m):
                if a[i][j] == 0:
                    row.append('Y' if cnt0 >= 2 else 'N')
                else:
                    row.append('Y' if cnt1 >= 2 else 'N')
            out.append(''.join(row) + '\n')
    write(''.join(out))

T = int(input().strip())
for _ in range(T):
    solve()

TLE（Time Limit Exceeded）提示：参照官方题解得知，C++ 中的 endl 会强制 flush 严重拖慢 IO。对应的，Python 中也必须减少输出调用次数，使用 join 拼接批量输出。

F x?y?n!

题目分析

给定整数 nn，找到两个整数 x,yx,y 满足：

  1. gcd⁡(x,y)=n\gcd(x,y)=n
  2. x≠yx \neq y
  3. 使得 x⊕yx \oplus y 最小

解题思路（AI提示）

由于 gcd⁡(x,y)=n\gcd(x,y)=n，故 x,yx,y 必须是 nn 的倍数。又因为 x≠yx \neq y，所以：∣x−y∣≥n|x-y| \geq n

减法需要借位，会削弱高位的贡献。而异或是找不同，相当于“不借位的减法”，每有一位不同就贡献 2k2^k。

  1 0 0 1 0 
^ 0 0 0 1 1 
------------
  1 0 0 0 1

所以减法的结果小于等于异或，即：x⊕y≥∣x−y∣x \oplus y \geq |x-y|

综上推导得到：x⊕y≥∣x−y∣≥nx \oplus y \geq |x-y| \geq n

于是问题变成了，如何构造出 x,yx,y 使其异或值为 nn？

使用拼接构造。在二进制中，乘以 2 就等于在后面加一个 0。把 nn 整体左移到高位，低位用长度为 nn 的 0 补足，即 x=n⋅2kx = n\cdot 2^k。

再把 nn 加进去得到 yy，即 y=x+ny = x + n。

此时计算 x⊕yx \oplus y：

  • x: [nnnnn] [00000]
  • y: [nnnnn] [nnnnn]

不难发现他们的异或值就是 nn。

Code

import sys
input = sys.stdin.readline

def solve():
    n = int(input().strip())
    k = n.bit_length()
    x = n << k
    y = x + n
    print(x, y)

T = int(input().strip())
for _ in range(T):
    solve()