Feb 9, 2026

26 Winter Holiday Round 4 Review

https://ac.nowcoder.com/acm/contest/120564
本文给出的 Python 代码在 nowcoder 使用 pypy3 环境均可 AC

A. 本场比赛灵感来源于树状数组出题组

枚举

题目分析

给定 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 。对于第 $x$ 个数字 $a_x$ ，如果其他数字中有至少 80% 的数字小于等于 $a_x$ ，则将其分在 A 组，否则分在 B 组。求 A 组中数字之和。

解题思路

看到数据范围 $n \leq 10^3$ ，就应该选择无脑遍历。可能比较坑的一点是：“如果其他数字中有至少 80% 的数字小于等于 ax”，这句话加粗了”至少”，但还有一个重点是”其他数字中”，笔者赛时读了好几遍都选择性地忽略了，甚至直到赛后补题才发现。

具体做法：对每个 $a_x$ ，遍历其余 $n-1$ 个数统计 $\leq a_x$ 的个数 $\text{cnt}$ ，若 $\text{cnt} / (n-1) \geq 0.8$ 则累计到答案中。

另外注意使用整数运算而不是浮点运算，虽然这道题不至于卡精度。

Code

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if i == j:
                continue
            if arr[i] >= arr[j]:
                cnt += 1
        if cnt * 10 >= (n-1) * 8:
        # cnt / (n-1) >= 0.8
            ans += arr[i]
    print(ans)
solve()

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> arr(n+1, 0);
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= n; j++){
            if(i == j) continue;
            if(arr[i] >= arr[j]) cnt++;
        }
        if(10 * cnt >= 8 *(n-1)){
            sum += arr[i];
        }
    }
    cout << sum << endl;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

赛后复盘

赛时尝试了另一种思路：降序排序后，能进 A 组的一定是最大的若干个元素，找到分界线即可。

降序排序后，位置 $i$ （0-indexed）的元素在其他 $n-1$ 个数中， $\leq$ 它的至少有 $n-1-i$ 个（它后面的所有数）。条件 $\frac{n-1-i}{n-1} \geq 0.8$ 化简为 $i \leq 0.2(n-1)$ ，取 $f = \lfloor 0.2(n-1) \rfloor$ ，则位置 $\leq f$ 的元素都能进 A 组。

但相等的元素要么全进要么全不进（它们排名相同），所以不能直接在 $f$ 处一刀切，而是要找到值发生变化的边界：遍历排序数组，只在 arr[i-1] != arr[i] 时判断 $i \leq f$ ，找到最小的满足条件的值作为阈值 $k$ ，最终把 $\geq k$ 的全部加起来。

能 AC，但边界处理语义不良，本题 $n \leq 10^3$ ， $O(n^2)$ 暴力是更稳妥的选择。

import sys, math
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort(reverse=True)
    f = math.floor((n-1) * 0.2)
    k = arr[0]
    for i in range(1, n):
        if arr[i-1] != arr[i]:
            if i <= f:
                k = arr[i]
            else:
                break
    print(sum([i for i in arr if i >= k]))
solve()

B. 构造部落

前缀和

题目分析

部落时代有 $n$ 位首领，第 1 位首领在位的第 1 年为公元 $s$ 年，第 $i$ 位首领在位时间为 $t_i$ 年。首领按编号顺序连续在位，即第 $i$ 位首领结束后次年第 $i+1$ 位首领立即即位。

现有 $q$ 件文物，每件文物记录了在第 $x$ 位首领在位的第 $y$ 年发生的事件，求其对应的公元年份。

解题思路

每位首领在位的起始年份可以通过前缀和递推：第 1 位首领的起始年是 $s$ ，第 $i$ 位首领的起始年 = 前一位的起始年 + 前一位的在位时间。预处理完毕后，对于查询 $(x, y)$ ，答案即为第 $x$ 位首领的起始年 $+ \, y - 1$ 。

用字典存储每位首领的 (起始年, 在位时间)，查询时直接 $O(1)$ 回答。

Code

import sys
input = sys.stdin.readline

def solve():
    n, q, s = map(int, input().split())
    arr = list(map(int, input().split()))
    live = {}
    for i, d in enumerate(arr):
        live[i+1] = (s, d)
        s += d
    for _ in range(q):
        xi, yi = map(int, input().split())
        s, d = live[xi]
        print(s + yi - 1)
solve()

I. 初华的扭蛋机

概率

题目分析

赌城里有一个 6 种颜色小球的扭蛋机，颜色为 W、G、B、P、Y、O，每种数量无穷且等概率 $\frac{1}{6}$ 。你有 6 枚筹码，每枚可以下注到一种颜色区域或留在手中。下注结束后扭蛋机抽 3 次，对于每种颜色 $c$ ，设其区域中有 $x$ 枚筹码：

摇出 1 颗该颜色：获得 $2x$ 枚筹码
摇出 2 颗：获得 $3x$ 枚筹码
摇出 3 颗：获得 $10x$ 枚筹码

最终筹码数 = 各颜色获得的筹码 + 手上剩余筹码。求使最终筹码数量期望值最大的下注方案。

解题思路

戒赌题。

本题无需输入，根据已有概率常识即可推测出最优下注方案，这里回顾式地计算期望：

设某颜色区域下注了 $x$ 枚筹码，3 次抽取中该颜色出现 $k$ 次的概率服从二项分布 $B(3, \frac{1}{6})$ ：

$P(k) = \binom{3}{k} \left(\frac{1}{6}\right)^k \left(\frac{5}{6}\right)^{3-k}$

$P(0) = \frac{125}{216}$ ，收益 $0$
$P(1) = \frac{75}{216}$ ，收益 $2x$
$P(2) = \frac{15}{216}$ ，收益 $3x$
$P(3) = \frac{1}{216}$ ，收益 $10x$

下注 $x$ 枚筹码到一种颜色的期望收益为：

$E(x) = \frac{75 \cdot 2x + 15 \cdot 3x + 1 \cdot 10x}{216} = \frac{205x}{216}$

注意下注的 $x$ 枚筹码本身已经投出去了，所以净期望为 $E(x) - x = \frac{205x - 216x}{216} = \frac{-11x}{216} < 0$ 。

也就是说，下注到任何颜色的期望净收益都是负的，无论怎么分配都不如不下注。所以最优策略就是 6 枚筹码全部留在手中，一枚也不下注。

Code

print('######')

H. 时不时使使用玉米加农炮掩饰害羞的邻座艾莉同学

枚举 / 模拟

题目分析

在一张 $n$ 行 $m$ 列的地图上，每个单元格 $(i,j)$ 有 $a_{i,j}$ 名敌人。使用”玉米加农炮”选择坐标 $(x,y)$ 后，会消灭与 $(x,y)$ 曼哈顿距离不超过 2 的所有方格上的敌人。

敌方进行 $q$ 次增援，每次在 $(x,y)$ 增加 $z$ 名敌人。每次增援后，输出使用一次炮弹能消灭最多敌人的方格坐标。

（本题没有敌人受到伤害，仅寻找位置坐标）

解题思路

先列出炮弹可以造成伤害的向量（曼哈顿距离 $\leq 2$ 的所有偏移），然后枚举向每个坐标发射炮弹可以获得的收益，顺便维护出一个最大值。增援时，我们把爆炸反过来，倒推可以被哪些坐标造成伤害，向他们累加消灭增援的收益，继续维护最大值。

具体来说，曼哈顿距离 $\leq 2$ 的偏移量共 13 个（含原点）：

                 (0, 2)
        (-1, 1)  (0, 1)  (1, 1)
(-2,0)  (-1, 0)  (0, 0)  (1, 0) (2, 0)
        (-1,-1)  (0,-1)  (1,-1)
                 (0,-2)

预处理：对每个候选炮弹中心 $(i,j)$ ，把它能覆盖到的 13 个格子的敌人数求和，得到 $\text{cost}(i,j)$ 。
增援更新： $(x,y)$ 增加敌人时，所有能覆盖 $(x,y)$ 的炮弹中心（即 $(x,y)$ 的 13 个偏移）的 cost 都要加 $z$ 。

坑：笔者貌似和这套题相性不高，该题行数是 $x$ ，列数是 $y$ ，刚好和坐标系里常用的反过来，WA 了好几次才看出来。

Code

import sys
input = sys.stdin.readline

direction = [(-2,0), (-1,0), (1,0), (2,0), (0,-2), (0,-1), (0,1), (0,2), (-1,-1), (-1,1), (1,1), (1,-1), (0,0)]

def solve():
    n, m, q = map(int, input().split())
    net = {}
    cost = {}
    for i in range(1, n+1):
        tmp = list(map(int, input().split()))
        for j in range(1, m+1):
            net[(i, j)] = tmp[j-1]
            cost[(i, j)] = 0
    mx = 0
    target = []
    for i in range(1, n+1):
        for j in range(1, m+1):
            for d in direction:
                x, y = i+d[0], j+d[1]
                if (x, y) in net:
                    cost[(x, y)] += net.get((i, j))
                    if cost.get((x, y)) > mx:
                        mx = cost.get((x, y))
                        target = [x, y]
    for i in range(q):
        x, y, z = map(int, input().split())
        for d in direction:
            xi, yi = x+d[0], y+d[1]
            if (xi, yi) in net:
                cost[(xi, yi)] += z
                if cost.get((xi, yi)) > mx:
                    mx = cost.get((xi, yi))
                    target = [xi, yi]
        print(' '.join(map(str, target)))

solve()

C. 墨提斯的排列

格雷码

题目分析

构造一个长度为 $2^n$ 的排列 $p_0, p_1, \ldots, p_{2^n-1}$ （即 $0$ 到 $2^n-1$ 的一个排列），使得相邻两项异或值之和最小： $\min \sum_{i=1}^{2^n-1} (p_{i-1} \oplus p_i)$

解题思路

要让相邻异或值之和尽可能小，理想情况是每对相邻元素只有 1 个二进制位不同，此时每对贡献恰好是某个 $2^k$ 。

这恰好就是格雷码（Gray Code）的定义：相邻两个码字之间恰好只有 1 位不同。 $n$ 位格雷码恰好覆盖 $0$ 到 $2^n - 1$ 的所有整数各一次，满足排列要求。

格雷码的生成公式为： $G(i) = i \oplus \lfloor i/2 \rfloor$

即 i ^ (i >> 1)。直接用这个公式输出即可。

Code

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = [str(i ^ (i>>1)) for i in range(2**n)]
    print(' '.join(arr))

solve()

F. 爱音的01串构造

构造

题目分析

给定整数 $a, b$ ，构造一个由 $a$ 个 0 和 $b$ 个 1 组成的 01 字符串，使得所有非空连续子串的 mex 之和最大。其中 mex 定义为字符串最小未出现的非负整数，例如 $\text{mex}(\texttt{"0"})=1$ ， $\text{mex}(\texttt{"1"})=0$ ， $\text{mex}(\texttt{"1100"})=2$ 。

解题思路

构造题的代码实现思路一般比较简单，很困难就说明想错了。mex 的定义更通俗的是，未出现在字符串中的最小非负整数。

分析各类子串的 mex 值：

只含 0 的子串：mex = 1
只含 1 的子串：mex = 0
同时含 0 和 1 的子串：mex = 2

为了最大化 mex 之和，应尽量让更多子串同时包含 0 和 1（贡献 2），尽量减少纯 0 或纯 1 的子串（贡献 0 或 1）。纯字符子串来源于连续的相同字符段，因此我们应该让相同字符尽量分散。

可以试着举些例子验证：

具体构造策略：将数量多的字符分隔成数量少字符+1个片段，再把数量少的字符均匀地插入片段间隙。设 $a > b$ （否则交换 0 和 1）， $a$ 个 0 将序列切分为 $b+1$ 段，将 $b$ 个 1 均匀分配到这些段中即可。

Code

import sys
input = sys.stdin.readline

def solve():
    a, b = map(int, input().split())
    if a == b:
        print('01' * a)
    else:
        c0, c1 = '0', '1'
        if a < b:
            b, a = a, b
            c1, c0 = c0, c1
        ans = ''
        t = a // (b + 1)
        remain = a % (b + 1)
        for i in range(b + 1):
            ans += c0 * t
            if remain > 0:
                ans += c0
                remain -= 1
            if b > 0:
                ans += c1
                b -= 1
        print(ans)

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