石子游戏

GitHub跳转原题关系图 Canvas 关系图返回列表

把最大必胜子游戏数转化为区间调度，预处理最早结束区间并用倍增回答询问。

OJ: shumeng

题目 ID: CSP202605D

难度:未知

标签:贪心区间调度倍增前缀异或离线

日期: 2026-07-31 16:22

形式化题目

给定长度为 $n$ 的序列 $b_1,\dots,b_n$ 。定义子游戏 $(l,r)$ 为：把 $b_l,\dots,b_r$ 重新编号成 $1..r-l+1$ 后，所有奇数位置石子数的异或和为 $0$ 则小 C 必胜。共 $q$ 个询问 $[L,R]$ ，要求把 $[L,R]$ 分割成若干连续子区间，最大化其中小 C 必胜的子游戏数量。

思路

必胜子游戏的前缀异或判定

子游戏 $(l,r)$ 必胜当且仅当“奇数位置石子数异或和为 $0$ ”。注意判定只看子游戏内部的位置奇偶性：如果 $l$ 是原数组的奇数下标，那么子游戏内的奇数位置就是原数组的奇数下标，异或和为 $0$ 等价于

\text{odd}[r]=\text{odd}[l-1],

其中 $\text{odd}[i]$ 是原数组奇数下标的异或前缀和。若 $l$ 是偶数下标，则用偶数下标的异或前缀和 $\text{even}$ 判定。

转成区间调度

不贡献必胜的子区间只负责填补空隙，可以任意插入。因此问题等价于：在 $[L,R]$ 内选择最多互不相交的必胜子区间。这是经典的区间调度问题，贪心策略是每次选择结束最早且与已选区间不相交的必胜区间。

预处理每个起点的最早结束位置

逆序扫描 $l$ ，维护 latest 记录当前后缀中每种前缀异或值最近出现的位置。对起点 $l$ ，查找使 $[l,r]$ 必胜的最早 $r$ ，记为 first_good_end[l]。再令 best_end[l] 为“起点不小于 $l$ 的必胜区间中最早的结束位置”，一次贪心选择后的下一个起点就是 best_end[l] + 1。

用倍增回答询问

从 $L$ 开始不断选择并跳转到下一个起点，跳转关系只与位置有关，与询问边界无关。对跳转做倍增预处理，询问时用二进制拆分统计在 $[L,R]$ 内能选多少个区间，每次 $O(\log n)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

const int LOG = 21; // 2^21 > 1e6

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

    int n, q;
    cin >> n >> q;
    // 奇数下标与偶数下标各自的异或前缀和
    vector<unsigned int> prefix_odd(n + 1, 0);
    vector<unsigned int> prefix_even(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        unsigned int value;
        cin >> value;
        prefix_odd[i] = prefix_odd[i - 1];
        prefix_even[i] = prefix_even[i - 1];
        if (i & 1) prefix_odd[i] ^= value;
        else prefix_even[i] ^= value;
    }

    // 逆序扫描后，latest 保存当前后缀中每种前缀异或值的最小位置。
    // 键带一个奇数/偶数标记位，避免两类前缀异或互相串扰。
    unordered_map<unsigned long long, int> latest;
    latest.reserve((n + 1) * 4);
    vector<int> first_good_end(n + 1, n + 1);
    for (int left = n; left >= 1; left--) {
        unsigned long long odd_key =
            (static_cast<unsigned long long>(prefix_odd[left]) << 1) | 1ULL;
        unsigned long long even_key =
            (static_cast<unsigned long long>(prefix_even[left]) << 1);
        latest[odd_key] = left;
        latest[even_key] = left;

        unsigned long long target_key;
        if (left & 1) {
            target_key =
                (static_cast<unsigned long long>(prefix_odd[left - 1]) << 1) | 1ULL;
        } else {
            target_key =
                (static_cast<unsigned long long>(prefix_even[left - 1]) << 1);
        }
        unordered_map<unsigned long long, int>::iterator it =
            latest.find(target_key);
        if (it != latest.end()) first_good_end[left] = it->second;
    }

    // 选择起点不小于 left 的所有必胜区间中，结束位置最靠前的一个。
    // jump[left] 是选完一次最优区间后的下一个起点（结束位置 + 1）。
    vector<int> jump(n + 3, n + 2);
    int best_end = n + 1;
    for (int left = n; left >= 1; left--) {
        best_end = min(best_end, first_good_end[left]);
        if (best_end <= n) jump[left] = best_end + 1;
    }
    jump[n + 1] = n + 2;

    // 对跳转关系做倍增，询问时用二进制拆分快速计数
    vector<vector<int>> up(LOG, vector<int>(n + 3, n + 2));
    for (int i = 1; i <= n + 1; i++) up[0][i] = jump[i];
    for (int level = 1; level < LOG; level++) {
        for (int i = 1; i <= n + 1; i++) {
            up[level][i] = up[level - 1][up[level - 1][i]];
        }
    }

    // 对每个询问做贪心区间调度：从 left 开始，只要下一个区间还落在 [L,R] 内就选择
    for (int query = 0; query < q; query++) {
        int left, right;
        cin >> left >> right;
        int current = left;
        int answer = 0;
        for (int level = LOG - 1; level >= 0; level--) {
            int next_position = up[level][current];
            if (next_position <= right + 1) { // 选择 2^level 个区间后仍不越界
                current = next_position;
                answer += 1 << level;
            }
        }
        cout << answer << '\n';
    }
    return 0;
}

复杂度

时间：预处理 $O(n\log n)$ ，每次询问 $O(\log n)$ ，总时间复杂度 $O((n+q)\log n)$ 。
空间：倍增表 $O(n\log n)$ ，空间复杂度 $O(n\log n)$ 。

总结

允许零贡献区间后，分割 DP 可以转化为选择不相交的有效区间；固定每个起点的最早结束区间后，区间调度可用倍增加速。判定必胜的关键是把“子游戏内部奇偶位置”转成原数组上带奇偶标记的前缀异或。

题目来自第 42 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 256 MB

题目背景

小 C 和小 S 正在玩一种石子游戏，规则如下：

有 $m$ 个仓库，从左到右编号为 $1,2,\cdots,m$ ， $i$ 号仓库初始存有 $a_i$ 个石子。
两位玩家轮流操作，小 S 先手。每轮操作可任选一个仓库 $i$ ，从中取出任意大于 $0$ 数量的石子，将取出石子移至 $i−1$ 号仓库。特别地，若 $i=1$ ，取出的石子将直接被丢弃。
当全部仓库石子均被清空时游戏终止，此时无法进行操作的玩家判负。

聪明的小 C 发现他必胜的条件为：所有奇数编号仓库的石子数异或和为 $0$ ，即 $a_1 \oplus a_3 \oplus \cdots \oplus a_{2k - 1} = 0$ ， $m=2k - 1$ 或 $2k$ ，其中 $\oplus$ 表示二进制异或操作。

题目描述

给定 $n$ 个仓库，从左到右编号为 $1,2,\cdots,n$ ， $i$ 号仓库初始存有 $b_i$ 个石子。

定义子游戏 $\left(l,r\right)$ ：选取仓库 $l \sim r$ 进行上述石子游戏，将其视作一组新仓库， $i$ 号仓库初始石子数为 $a_i=b_{i+l-1}$ 。

共有 $q$ 个互相独立的询问，每个询问给出区间 $[L,R]$ 。小 C 需要把 $[L,R]$ 分割为若干个子区间 $[l_1,r_1], [l_2,r_2], \cdots, [l_k,r_k]$ ，满足 $l_1=L, r_k=R, r_i=l_{i+1}-1 \left(1 \le i < k \right)$ ，使得在 $k$ 个子游戏 $(l_1,r_1), (l_2,r_2), \cdots, (l_k,r_k)$ 中他必胜的子游戏数量尽可能地多。求所有合法分割方案里，小 C 必胜的子游戏数量的最大值。

输入格式

从标准输入读入数据。

第一行读入两个正整数 $n,q$ ，表示仓库数量和询问次数。

第二行读入 $n$ 个非负整数 $b_1,b_2,\cdots,b_n$ ，表示各仓库的石子个数。

接下来 $q$ 行，每行读入两个正整数 $L,R$ ，表示一个询问。题目保证 $1 \le L \le R \le n$ 。

输出格式

输出到标准输出。

输出 $q$ 行，每行一个整数，表示每组询问中小 C 能得到的必胜子游戏数量的最大值。

input1

output1

1
20
2

样例 1 解释

容易得知，只有子游戏 $\left(1,3\right), \left(1,4\right), \left(4,4\right)$ 是小 C 必胜的。

因此第一个询问 $\left(2,3\right)$ 中不存在一个区间满足小 C 必胜，答案为 $0$ ；

第二个询问 $\left(1,4\right)$ 可以分割为 $\left(1,3\right)$ 和 $\left(4,4\right)$ ，答案为 $2$ 。

子任务

保证对于所有测试点，均有 $1\le n,q\le 10^6,\ 0\le b_i<2^{31}$ 。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n,q\le$
1	30	$100$
2	30	$3000$
3	20	$10^5$
4	20	$10^6$

提示

本题输入输出量较大，请采用效率较高的输入输出方式。