题解：P11629 [WC2025] Nim 游戏

DimStar
  2026-07-18 16:42:06 2026-07-18 16:42:06 创建   2026-11-04 08:26:27 2026-11-04 08:26:27 更新      1.4k 字  

前言

太诡异了，遂写题解。

提示：我是听了讲，看了题解，搞了好久才搞明白的。我比较笨，描述不清楚，请多多包涵。

Solution

先考虑第一问。

其实已经是困难的。

尝试使用针对位运算类型问题常见 Trick，从高位到低位贪心处理。

异或值为 0 的位不管，异或值为 1 的位需要处理，如何处理呢？

显然需要将某个数的这一位取反，使得异或值为 0。

考虑两种取反的可能：

  1. 将某个数的这一位从 1 变为 0，显然需要将该数加上一坨，然后向上一位进位，低位全为 0。

  2. 将某个数的这一位从 0 变为 1，显然需要将该数加上一坨，低位全为 0。

低位全为 0 是显然的，因为这是当前花费最小的方式，且给低位提供了最大的操作空间。

现在考虑我们使用哪种方式操作，发现这个向上进位很混乱邪恶，难以考虑，并且按照贪心顺序，此前高位异或值为 0，向上进位会破坏异或值，导致极高的代价。

所以优先考虑第二种。

现在还需要决策选哪个位置置 1，发现肯定选代价最小的，因为如果留着给后面低位在这个位置置 1，显然这个位置原有 1 产生的“负贡献”不会增大。

那么如果 我们就已经会做了，此时每一位第一个位置一定是 0。

那如果当前位所有数都为 1 呢？

这意味着之前也没有进行高位的操作（否则这一位一定会有零），因此这一位一定是最高的初始异或值为 1 的位。

所以我们一定会在高位进行两次把 0 变成 1 的操作（注意是两次以保证异或值为 0），为什么不考虑将 1 变成 0？发现如果将 1 变成 0，就会进位，改变高位异或值，于是还要对更高位操作，相当于对更高位将 0 置 1。

现在我们就已经会 query（查询答案）

现在我们就只需要考虑找方案，使用搜索，配合 query 函数提前 check 剪枝即可。

放代码：

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
#include <bits/stdc++.h>
#define nmf(i, s, e) for (int i = s; i <= e; i++)
#define ref(i, s, e) for (int i = s; i >= e; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
#define int LL
int n, m;
LL a[100005], xorsum;

bool vis[100005];             // 标记已经操作过，低位全为 0 的数
vector<pair<LL, int>> v0[61]; // 这一位初值为 0 的数及其低位的值

LL ans;
vector<vector<pair<int, LL>>> ans2;
vector<pair<int, LL>> now;    // 存已经被操作过的数和她们各自被加的值

void clear()
{
    xorsum = 0;
    nmf(i, 0, 60) v0[i].clear();
    nmf(i, 1, n) vis[i] = 0;
    ans = LLONG_MAX;
    ans2.clear();
    assert(now.empty());
}

int to_del[65], top;
LL query(LL xorval)
{
    LL ret = 0;
    top = 0;
    ref(i, 60, 0)
    {
        if ((xorval >> i) & 1)
        {
            LL flag = 0;
            for (auto &[val, id] : v0[i])
            {
                if (vis[id])
                    continue;
                vis[id] = 1;
                flag = val;
                to_del[++top] = id;
                break;
            }
            ret += ((1ll << i) - flag);
            xorval ^= flag;
        }
    }
    nmf(i, 1, top)
        vis[to_del[i]] = 0;
    return ret;
}
void dfs(LL xorval, LL sum)
{
    if (ans2.size() >= m)
        return;
    if (xorval == 0)
        return ans2.push_back(now);
    const int s = __lg(xorval), S = 1ll << s;
    for (auto &[val, id] : v0[s])
    {
        if (ans2.size() >= m)
            return;
        if (vis[id])
            continue;
        if (query(xorval ^ (S ^ val)) + sum + S - val > ans)
            return;
        vis[id] = 1;
        now.push_back({id, S - val});
        dfs(xorval ^ (S ^ val), sum + S - val);
        vis[id] = 0;
        now.pop_back();
    }
    // 选择一个低位已经被清零的数操作，即修改 now 中的元素
    if (!now.empty())
    {
        if (query(xorval ^ S) + sum + S > ans)
            return;
        const int sz = now.size();
        nmf(i, 0, sz - 1)
        {
            if (ans2.size() >= m)
                return;
            now[i].second += S;
            dfs(xorval ^ S, sum + S);
            now[i].second -= S;
        }
    }
}

void solve()
{
    cin >> n >> m;
    nmf(i, 1, n) cin >> a[i], xorsum ^= a[i];
    if (xorsum == 0)
    {
        cout << "0\n";
        cout << "1\n";
        cout << "0\n";
        cout << "\n";
        cout << "\n";
        return;
    }
    nmf(j, 0, 60)
    {
        nmf(i, 1, n)
        {
            if (!((a[i] >> j) & 1))
            {
                v0[j].push_back({a[i] & ((1ll << j) - 1), i});
            }
        }
        sort(v0[j].begin(), v0[j].end(), greater<>());
    }

    if (v0[__lg(xorsum)].empty()) // 最高异或值为 1 的位出现全 1
    {
        int s = __lg(xorsum);
        nmf(d, s + 1, 60)
        {
            if (v0[d].size() >= 2) // 贪心选择，代价最小的两个
            {
                vis[v0[d][0].second] = 1;
                vis[v0[d][1].second] = 1;
                ans = min(ans, query(xorsum ^ (v0[d][0].first ^ v0[d][1].first)) +
                                   (((1ll << d) - v0[d][0].first) + ((1ll << d) - v0[d][1].first)));
                vis[v0[d][0].second] = 0;
                vis[v0[d][1].second] = 0;
            }
        }
    }
    else
    {
        ans = query(xorsum);
    }
    cout << ans << '\n';
    if (v0[__lg(xorsum)].empty())
    {
        int s = __lg(xorsum);
        nmf(d, s + 1, 60)
        {
            if (ans2.size() >= m)
                break;
            if (v0[d].size() >= 2)
            {
                nmf(i, 0, (int)(v0[d].size()) - 2)
                {
                    if (ans2.size() >= m)
                        break;
                    nmf(j, i + 1, (int)(v0[d].size()) - 1) // 由于会有低位相等的位置，因此需要枚举以找方案
                    {
                        if (ans2.size() >= m)
                            break;
                        if (query((xorsum ^ (v0[d][i].first ^ v0[d][j].first))) + (((1ll << d) - v0[d][i].first) + ((1ll << d) - v0[d][j].first)) > ans)
                            break;
                        vis[v0[d][i].second] = 1;
                        vis[v0[d][j].second] = 1;
                        now.push_back({v0[d][i].second, ((1ll << d) - v0[d][i].first)});
                        now.push_back({v0[d][j].second, ((1ll << d) - v0[d][j].first)});
                        dfs((xorsum ^ (v0[d][i].first ^ v0[d][j].first)),
                            (((1ll << d) - v0[d][i].first) + ((1ll << d) - v0[d][j].first)));
                        vis[v0[d][i].second] = 0;
                        vis[v0[d][j].second] = 0;
                        now.clear();
                    }
                }
            }
        }
    }
    else
    {
        dfs(xorsum, 0);
    }
    cout << ans2.size() << '\n';
    for (auto &it : ans2)
    {
        sort(it.begin(), it.end());
        cout << it.size() << '\n';
        for (auto &i : it)
            cout << i.first << ' ';
        cout << '\n';
        for (auto &i : it)
            cout << i.second << ' ';
        cout << '\n';
    }
    clear();
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int c, T = 1;
    cin >> c >> T;
    while (T--)
        solve();
    return 0;
}
  • 标题: 题解：P11629 [WC2025] Nim 游戏
  • 作者: DimStar
  • 创建于 : 2026-07-18 16:42:06
  • 更新于 : 2026-11-04 08:26:27
  • 链接: https://dimstar-zhang.github.io/2026/07/18/题解：P11629-WC2025-Nim-游戏/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
题解：P11629 [WC2025] Nim 游戏
  1. 前言
  2. Solution