26 Winter Holiday Round 6 Review

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

K 小L的游戏1

周期性

题目分析

给定小 L 从起点 $0$ 开始，交替向右移动 $m, n, m, n, \dots$ 的距离，即第奇数步走 $m$，第偶数步走 $n$。当她的坐标 $\ge z$ 时停止。我们需要判断最后一步走的是 $m$（输出 0）还是 $n$（输出 1）。

$z \le 10^{18}$，如果逐步模拟一定会 TLE，因此算法复杂度必须是 $O(1)$ 或带极小常数。

解题思路

根据题意，移动距离存在 $m+n$ 的周期性。因此，我们可以直接“跳过”完整的周期，不用真正去“模拟”整个过程。

具体做法是：计算总距离 $z$ 里面包含多少个完整的 $m+n$（即 times = z // (m + n)），然后把这些完整的周期一次性减掉。 剩下的一定小于 $m+n$（也就是最多只需要再走 2 步），此时我们再用一个极小的 while 循环（或 if-else 讨论）走完最后不到一个周期的路程，并记录步数奇偶性（op % 2），就能 $O(1)$ 级别得出最后一步的操作类型。

边界处理：代码中 op 初始值为 -1，最后输出 op % 2，是为了处理 $z$ 恰好是 $m+n$ 整数倍的边界情况。
若减去完整周期后剩余距离 $= 0$，while 循环不会执行，意味着最后一步正是周期中 $n$ 的移动，应输出 1，此时 op 保持初始值 -1。

需要注意的是，在 Python 中，负数的模运算结果与 除数 同号（与数学意义一致），因此 -1 % 2 == 1，恰好得到正确答案。刚好完成了 [-1, 0, 1] 到 [1, 0, 1] 的映射。利用语言特性回避了复杂的分支判断。

C++ / Java 中的模运算结果与 被除数 同号（即 -1 % 2 == -1）。推荐直接使用 if 分支判断或写成 (a % b + b) % b。

Code

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    ans = []
    for _ in range(t):
        m, n, z = map(int, input().split())
        x = 0
        op = -1
        times = z // (m + n)
        if times > 0:
            z -= (m + n) * times
        while x < z:
            x += m
            op += 1
            m, n = n, m
        ans.append(str(op % 2))
    print(''.join(ans))

solve()

G 小L的散步

前缀和

题目分析

给定一条由 $n$ 块砖拼接而成的路，砖块长度依次为 $a_i$。小 L 初始时脚后跟位于坐标 $0$，脚尖位于坐标 $l$（脚长为 $l$）。 接下来她会走 $m$ 步，每步向前平移 $b_i$ 的距离。我们需要判断在初始状态或某一步落地后，是否存在一条缝隙严格位于脚后跟与脚尖之间。如果存在，输出 YES 结束；如果始终没有踩到缝隙，输出 NO。

解题思路

缝隙坐标其实就是每块砖长度的前缀和数组 c。

我们遍历出所有的缝隙坐标。检查脚掌踩缝隙的本质是：脚后跟允许在缝隙上，只需检查脚后跟的前方第一条缝隙是否也小于脚尖。 因为小 L 是一直往前走的（脚后跟 y 单调递增），这意味着我们可以用类似双指针的思想。维护一个指针 cnt 指向“脚后跟前方的第一个缝隙”。

1. 每次脚后跟移动到 y 时，不断移动 cnt，直到找到第一个满足 c[cnt] > y 的缝隙。
2. 此时 c[cnt] 是脚后跟前方最近的缝隙了，我们只需检查它是否严格小于脚尖坐标（即 c[cnt] < y + l），为真则判定 YES 结束；否则继续走下一步。

缝隙刚好在脚后跟或脚尖处不算踩到缝隙。因此这里的判断条件必须是严格的开区间 $(y, y+l)$。由于 cnt 最多只遍历数组一次，时间复杂度为 $O(n+m)$。

Code

import sys
input = sys.stdin.readline

def solve():
    n, m, l = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    c = []
    c.append(a[0])
    for i in range(1, n):
        c.append(c[i-1] + a[i])
    
    y = 0
    cnt = 0
    if c[cnt] < l:
        print('YES')
        return
    for i in range(m):
        y += b[i]
        while cnt < n and c[cnt] <= y:
            cnt += 1
        if cnt < n and c[cnt] < y + l:
            print('YES')
            return
    print('NO')

solve()

H 小L的数组

值域 DP，0-1 背包

题目分析

给定一个初始值为 $0$ 的变量 $x$，以及两个长度为 $n$ 的数组 $a$ 和 $b$。在第 $i$ 步（$1 \le i \le n$），你可以选择以下两种操作之一更新 $x$：

1. $x = \max(0, x - a_i)$
2. $x = x \oplus b_i$ 你需要求出经过 $n$ 步操作后，$x$ 可能达到的最大值。

$n \le 2048$，如果简单粗暴地 DFS 搜索每一步的两种选择，时间复杂度高达 $O(2^n)$ 显然无法接受的。（加剪枝也许能 AC）

解题思路

可以发现规则一使得 $x$ 单调减，但是规则二可能增大 $x$，也可能减小 $x$。也就是 $x$ 的状态会不断转移，这是一个明显的动态规划板子。

我们仔细观察 DP 的状态空间，操作数的取值范围 $a_i, b_i < 2048$ 可以发现：规则一使得 $x$ 归零或减小，每个元素都小于 $2048$；规则二（异或）的最大结果也就是 $0 \oplus 2047 = 2047$。

这说明无论怎么操作，$x$ 一定落在 $[0, 2047]$ 的有限范围内。这就提示我们将状态空间从 $n$ 转移到有限的值域区间。 对于每一步操作，需要 $O(2048 \times n)$，总计不超过 $4.2M$ 次状态转移。

本题比较朴素，只有在 $i$ 层可达的数字才能进入 $i+1$ 层。故仅需维护出最终可达的 $x$ 即可，这里使用了一维数组 dp 滚动更新： 遍历上一层所有为 True 的状态，分别执行规则一 $\max(0, x - a_i)$ 和规则二 $x \oplus b_i$ 转移即可。最后从 $2047$ 倒序遍历第一个 True 的值即为答案。

Code

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    dp = [False] * 2048
    dp[0] = True
    for i in range(n):
        dp_nxt = [False] * 2048
        for x in range(2048):
            if dp[x]:
                dp_nxt[max(0, x - a[i])] = True
                dp_nxt[x ^ b[i]] = True
        dp = dp_nxt
    for ans in range(2047, -1, -1):
        if dp[ans]:
            print(ans)
            return

solve()

A 小L的三角尺

贪心，最大堆

题目分析

给定 $n$ 把直角三角尺，第 $i$ 把的两条直角边分别为 $x_i, y_i$。现在有 $w$ 次打磨机会，每次操作可以使某把三角尺的 $y$ 边长度减 $1$。要求打磨后所有三角尺的斜边长度总和 $\sum \sqrt{x_i^2 + y_i^2}$ 最小。

三角尺个数 $n \le 5 \times 10^5$ 与总打磨额度 $w \le 10^{6}$，面对这种“有限次操作求最优解”，必须依赖高效的数据结构和贪心策略，否则必定 TLE。

解题思路

根据勾股定理，随着 $y$ 的减小，函数 $\sqrt{x^2+y^2}$ 的斜边减小量是递减的。这意味着：对于同一把三角尺，越早打磨收益越高。

一把直角三角尺的两条直角边 $x, y$，每次允许最小步长为 $1$ 地打磨 $y$ 边。希望打磨后的斜边长度最小，也就是要让每次打磨的收益最大。

具体实现思路是：使用一个优先队列（最大堆/大根堆）存储所有三角尺打磨一次后（也就是 $y-1$ 时）的收益。每次打磨后 $y_i$ 必须 $\ge 1$ 才能被继续打磨，所有尺子能够被打磨的总次数最多是 $\sum y_i$，所以在实际的有效打磨次数 $\min(w, \sum y_i)$ 约束下：

1. 我们每次取出堆顶收益最高的三角尺。
2. 从斜边总和中减去本次打磨收益，并将对应的 $y$ 减 $1$。
3. 如果它还能继续打磨（$y \ge 1$），就计算它下一步的预期收益，并再次推入堆中，直到步数用尽或堆为空。

PS: 此题 Python 卡常数，大概率 AC，也可能因 OJ 平台抖动而 TLE。应该果断使用 C++ 以应对带有大量浮点运算和高频堆操作。

Code

import sys, heapq, math
input = sys.stdin.readline
sqrt = math.sqrt

def solve():
    n, w = map(int, input().split())
    heap = []
    ans = 0
    sum_y = 0
    lx2 = []
    ly = []
    for i in range(n):
        x, y = map(int, input().split())
        x2 = x * x
        lx2.append(x2)
        ly.append(y)
        ans += sqrt(x2 + y * y)
        sum_y += y
        if y >= 1:
            gain = sqrt(x2 + y * y) - sqrt(x2 + (y-1) * (y-1))
            heapq.heappush(heap, (-gain, i))

    steps = min(w, sum_y)
    for _ in range(steps):
        if not heap:
            break
        gain, i = heapq.heappop(heap)
        ans += gain
        ly[i] -= 1
        x2 = lx2[i]
        y = ly[i]
        if y >= 1:
            gain = sqrt(x2 + y * y) - sqrt(x2 + (y-1) * (y-1))
            heapq.heappush(heap, (-gain, i))
    print(ans)
solve()

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using ld = long double;

struct Node {
    ld gain; ll x; ll y;
    bool operator<(const Node& other) const {
        return gain < other.gain;
    }
};

void solve() {
    ll n, w;
    cin >> n >> w;
    priority_queue<Node> pq;
    ld ans = 0.0L;
    ll sumY = 0;
    for (int i = 1; i <= n; i++) {
        ll x, y;
        cin >> x >> y;
        ans += sqrtl(x * x + y * y);
        sumY += y;
        if (y >= 1) {
            ld gain = sqrtl(x * x + y * y) - sqrtl(x * x + (y-1) * (y-1));
            pq.push(Node{gain, x, y});
        }
    }
    ll steps = min(w, sumY);
    for (ll i = 1; i <= steps; i++) {
        if (pq.empty()) break;
        Node cur = pq.top();
        pq.pop();

        ans -= cur.gain;
        cur.y -= 1;
        if (cur.y >= 1) {
            ld gain = sqrtl(cur.x * cur.x + cur.y * cur.y) - sqrtl(cur.x * cur.x + (cur.y-1) * (cur.y-1));
            cur.gain = gain;
            pq.push(cur);
        }
    }
    cout << ans << endl;
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int T = 1;
    while (T --) {
        solve();
    }
    return 0;
}

B 小L的彩球

组合数学，隔板法

题目分析

将 $n$ 个有编号的小球排成一排，依次放入“左盒”或“右盒”中。题目给定了两个限制条件：

1. 左盒中一共放了 $x$ 个球，这意味着右盒中一共放了 $(n-x)$ 个球。
2. 相邻编号小球之间有连线，若两小球放入不同盒子，会有连线露在外面，恰好有 $t$ 段连线露在外面。

我们要求出满足以上条件的方案数，结果对 $998244353$ 取模。

解题思路

“露在外面的线”，其实就是相邻两小球不在同一盒子的对数。

本题的关键是发现小球只能在左盒或右盒，我们将这个问题转化为：左盒记为 0、右盒记为 1，本质上这就是一个长度为 $n$ 的 01 串。所谓 $t$ 次交替，就是将长度为 $n$ 的串分成了 $t+1$ 段同字符的区间。

例如：长度为 $7$，交替次数（相邻不同对数）为 $2$，就有 0011100。这实际上是将 01 串分为了 $3$ 段 00 | 111 | 00，有 $seq = t + 1$ 段 0、1 串交替出现。由于段数给定的情况下，每一段必然全为 0 或全为 1，方便分析也可以抽象为 0 | 1 | 0。

既然段是交替的，我们就要讨论 0 段和 1 段分别的个数：

• 开头为 0：a = ceil(seq / 2) 个 0 段；b = floor(seq / 2) 个 1 段。
• 开头为 1：b = ceil(seq / 2) 个 1 段；a = floor(seq / 2) 个 0 段。

如何把长度为 $n$ 的串分割为 $k$ 段呢？这是典型的隔板法，串有 $n-1$ 个缝，选出 $k-1$ 个缝插入隔板即为 $k$ 段，方案数为 $C_{n-1}^{k-1}$。以“开头为 0”为例：

1. 我们要把这 $x$ 个 0 放入 $a$ 个 0 段里，方案数为 $C_{x-1}^{a-1}$。
2. 同理要把剩下的 $n-x$ 个 1 放入 $b$ 个 1 段里，方案数为 $C_{n-x-1}^{b-1}$。
3. 这两个是完全独立的分配事件，所以情况一的总方案数相乘即可：$s_0 = C_{x-1}^{a-1} \times C_{n-x-1}^{b-1}$。同理算出开头为 1 的情况 $s_1$。

最后答案就是 $(s_0 + s_1) \pmod{998244353}$。

注意到边界 $x \le n$，当 $k=0$ 且 $n=0$ 时 $C_n^k=1$，若代码直接调用 $C_{n-1}^{k-1}$ 会返回 $0$，这里必须特判。例如 $t=0$ 时没有线露在外面，表示所有的球都在左盒或右盒。

这里可以套一个预处理阶乘的板子，先正向递推求出 $1 \sim MAXN$ 的阶乘数组 fac。然后用费马小定理求出 MAXN! 的模逆元，再逆向递推出所有阶乘的逆元数组 inv_fac。这样就能在 $O(1)$ 内计算组合数 $C_n^k$ 了。

Code

import sys
from math import ceil, floor
input = sys.stdin.readline

MOD = 998244353
MAXN = 1_000_000

fac = [1] * (MAXN + 1)
inv_fac = [1] * (MAXN + 1)

for i in range(1, MAXN + 1):
    fac[i] = fac[i-1] * i % MOD

inv_fac[MAXN] = pow(fac[MAXN], MOD - 2, MOD)
for i in range(MAXN - 1, -1, -1):
    inv_fac[i] = inv_fac[i+1] * (i+1) % MOD

def C(n, k):
    if k < 0 or k > n:
        return 0
    return fac[n] * inv_fac[k] % MOD * inv_fac[n-k] % MOD

def ways(n, k):
    if k == 0:
        return 1 if n == 0 else 0
    return C(n - 1, k - 1)

def solve():
    n, x, t = map(int, input().split())
    seq = t + 1
    a = ceil(seq / 2)
    b = floor(seq / 2)
    s0 = ways(x, a) * ways(n - x, b)
    s1 = ways(x, b) * ways(n - x, a)

    ans = (s0 + s1) % MOD
    print(ans)

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

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

const int MOD = 998244353;
const int MAXN = 1'000'000;

struct Comb {
    ll fac[MAXN + 1];
    ll ifac[MAXN + 1];

    static ll qpow(ll a, ll b) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    void init() {
        fac[0] = 1;
        for (int i = 1; i <= MAXN; i++) {
            fac[i] = fac[i - 1] * i % MOD;
        }
        ifac[MAXN] = qpow(fac[MAXN], MOD - 2);
        for (int i = MAXN - 1; i >= 0; i--) {
            ifac[i] = ifac[i + 1] * (i + 1) % MOD;
        }
    }

    ll C(ll n, ll k) const {
        if (k < 0 || k > n) return 0;
        return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
    }
} comb;

inline ll ways(ll n, ll k) {
    if (k == 0) return (n == 0 ? 1 : 0);
    return comb.C(n - 1, k - 1);
}

void solve() {
    ll n, x, t;
    cin >> n >> x >> t;
    ll seq = t + 1;
    ll a = (seq + 1) / 2;
    ll b = seq / 2;

    ll s0 = ways(x, a) * ways(n - x, b);
    ll s1 = ways(x, b) * ways(n - x, a);

    cout << (s0 + s1) % MOD << endl;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    comb.init();

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}