第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——连线博弈 · znzryb
## 思路讲解
一个比较好的博客。
[https://blog.csdn.net/notonlysuccess/article/details/130959107](https://blog.csdn.net/notonlysuccess/article/details/130959107)
[2025“钉耙编程”中国大学生算法设计暑期联赛（3）](/2025/07/25/20250725-a35ed8c4)
随机化做法与随机值异或的应用。
其实就是求被不同区间覆盖的不同情况数量。
当然这道题目有所不同，不过也差不多。
一种更加方便的实现。
```cpp
cin >> N >> M;
map<ll, ll> mp;
mt19937_64 rng(time(0));
FOR(i, 1, M) {
ll x, y;
cin >> x >> y;
ll r = rng();
mp[x] ^= r;
mp[y] ^= r;
}
if (M == 0) {
if (SG(N)) {
yyy;
} else {
nnn;
}
return;
}
map<ll, ll> mp2;
ll up = -1;ll cur = 0;
mp[N]=0;
for (auto &[u, v] : mp) {
ll num = max(0ll, u - up - 1);
mp2[cur] += num;
up = u;
cur ^= v;
}
ll ans = 0;
for (auto &[u, v] : mp2) {
ans ^= SG(v);
}
if (ans) {
yyy;
} else {
nnn;
}
```
## AC代码
[https://qoj.ac/submission/1387353](https://qoj.ac/submission/1387353)
::: 源代码
```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#include <random>
#define all(vec) vec.begin(), vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var << ":" << var << "\n";
#define cend cerr << "\n-----------\n"
#define fsp(x) fixed << setprecision(x)
#define minn(vec) *min_element(vec.begin(), vec.end())
#define maxx(vec) *max_element(vec.begin(), vec.end())
#define yyy cout << "YES\n"
#define nnn cout << "NO\n"
using namespace std;
#ifdef LOCAL
template <typename T> void _print(T x) { cerr << x; }
// 可以打印多层数组，但是格式不是很好
template <typename T> void _print(vector<T> v) {
cerr << "[ ";
for (T i : v)
_print(i), cerr << " ";
cerr << "]";
}
template <typename T> void _print(set<T> s) {
cerr << "{ ";
for (T i : s)
_print(i), cerr << " ";
cerr << "}";
}
template <typename T, typename U> void _print(pair<T, U> p) {
cerr << "{";
_print(p.first);
cerr << ", ";
_print(p.second);
cerr << "}";
}
template <typename T, typename U> void _print(map<T, U> m) {
cerr << "{ ";
for (auto &p : m)
_print(p), cerr << " ";
cerr << "}";
}
// 打印两层数组，格式好一些
template <typename T> void _print(vector<vector<T>> v) {
cerr << "{\n";
for (auto i : v)
_print(i), cerr << "\n";
cerr << " }";
}
#endif
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
using i128 = __int128;
using pdd = pair<DB, DB>;
using plb = pair<ll, bool>;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vb = vector<bool>;
using tll = tuple<ll, ll, ll>;
using vii = vector<int>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vdb = vector<DB>;
using vc = vector<char>;
using arr3 = array<ll, 3>;
using arr2 = array<ll, 2>;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10,
INF = (ll)1e17 + 3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod = (ll)1e9 + 7; // 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll N, M, Q, X, K, T, lT;
inline void __();
vii sg(1110);
ll SG(ll x) {
if (x <= 200)
return sg[x];
ll idx=36+(x-36)%34;
if(idx==52){
return sg[idx+34];
}
return sg[idx];
}
// int SG(int x)
// {
// if(x<=100)return sg[x];
// x--;
// x%=34;
// x++;
// x+=68;
// return sg[x];
// }
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
sg[0] = 0;
sg[1] = 0;
FOR(i, 2, 500) {
set<ll> s;
FOR(j, 0, i - 2) { s.insert(sg[j] ^ sg[i - j - 2]); }
ll mex = 0;
while (s.count(mex))
mex++;
sg[i] = mex;
}
#ifdef LOCAL
FOR(i,0,500){
cerr<<i<<":"<<sg[i]<<"\n";
}
FOR(i,201,500){
if(SG(i)!=sg[i]){
cout<<"错误出现在"<<i<<" SG:"<<SG(i)<<" sg:"<<sg[i] <<"\n";
cout<<" 36+(x-36)%34:"<<36+(i-36)%34<<"\n";
}
}
#endif
while (lT--)
__();
return 0;
}
/*
*/
inline void __() {
cin >> N >> M;
map<ll, ll> mp;
mt19937_64 rng(time(0));
FOR(i, 1, M) {
ll x, y;
cin >> x >> y;
ll r = rng();
mp[x] ^= r;
mp[y] ^= r;
}
if (M == 0) {
if (SG(N)) {
yyy;
} else {
nnn;
}
return;
}
map<ll, ll> mp2;
ll up = -1;ll cur = 0;
mp[N]=0;
for (auto &[u, v] : mp) {
ll num = max(0ll, u - up - 1);
mp2[cur] += num;
up = u;
cur ^= v;
}
ll ans = 0;
for (auto &[u, v] : mp2) {
ans ^= SG(v);
}
if (ans) {
yyy;
} else {
nnn;
}
}
/*
AC
https://vjudge.net/solution/63829921
AC
https://qoj.ac/submission/1387353
FOR(i, 1, M) {
ll x, y;
cin >> x >> y;
s.insert(x);
s.insert(y);
}
if (M == 0) {
if (SG(N)) {
yyy;
} else {
nnn;
}
return;
}
ll up = *s.begin();
ll ans = 0;
if (up != 0) {
ans ^= SG(up - 1);
}
for (auto it = next(s.begin()); it != s.end(); ++it) {
ll p = *it;
ll num = p - up - 1;
up = p;
ans ^= SG(num);
}
#ifdef LOCAL
_print(s);
#endif
if (*s.rbegin() != N - 1) {
ll num = N - 1 - *s.rbegin();
#ifdef LOCAL
debug(num);
#endif
ans ^= SG(num);
}
if (ans) {
yyy;
} else {
nnn;
}
0:0
1:0
2:1
3:1
4:2
5:0
6:3
7:1
8:1
9:0
10:3
11:3
12:2
13:2
14:4
15:0
16:5
17:2
18:2
19:3
20:3
21:0
22:1
23:1
24:3
25:0
26:2
27:1
28:1
29:0
30:4
31:5
32:2
33:7
34:4
35:0
36:1
37:1
38:2
39:0
40:3
41:1
42:1
43:0
44:3
45:3
46:2
47:2
48:4
49:4
50:5
51:5
52:2
53:3
54:3
55:0
56:1
57:1
58:3
59:0
60:2
61:1
62:1
63:0
64:4
65:5
66:3
67:7
68:4
69:8
70:1
71:1
72:2
73:0
74:3
75:1
76:1
77:0
78:3
79:3
80:2
81:2
82:4
83:4
84:5
85:5
86:9
87:3
88:3
89:0
90:1
91:1
92:3
93:0
94:2
95:1
96:1
97:0
98:4
99:5
100:3
101:7
102:4
103:8
104:1
105:1
106:2
107:0
108:3
109:1
110:1
111:0
112:3
113:3
114:2
115:2
116:4
117:4
118:5
119:5
120:9
121:3
122:3
123:0
124:1
125:1
126:3
127:0
128:2
129:1
130:1
131:0
132:4
133:5
134:3
135:7
136:4
137:8
138:1
139:1
140:2
141:0
142:3
143:1
144:1
145:0
146:3
147:3
148:2
149:2
150:4
151:4
152:5
153:5
154:9
155:3
156:3
157:0
158:1
159:1
160:3
161:0
162:2
163:1
164:1
165:0
166:4
167:5
168:3
169:7
170:4
171:8
172:1
173:1
174:2
175:0
176:3
177:1
178:1
179:0
180:3
181:3
182:2
183:2
184:4
185:4
186:5
187:5
188:9
189:3
190:3
191:0
192:1
193:1
194:3
195:0
196:2
197:1
198:1
199:0
200:4
201:5
202:3
203:7
204:4
205:8
206:1
207:1
208:2
209:0
210:3
211:1
212:1
213:0
214:3
215:3
216:2
217:2
218:4
219:4
220:5
221:5
222:9
223:3
224:3
225:0
226:1
227:1
228:3
229:0
230:2
231:1
232:1
233:0
234:4
235:5
236:3
237:7
238:4
239:8
240:1
241:1
242:2
243:0
244:3
245:1
246:1
247:0
248:3
249:3
250:2
251:2
252:4
253:4
254:5
255:5
256:9
257:3
258:3
259:0
260:1
261:1
262:3
263:0
264:2
265:1
266:1
267:0
268:4
269:5
270:3
271:7
272:4
273:8
274:1
275:1
276:2
277:0
278:3
279:1
280:1
281:0
282:3
283:3
284:2
285:2
286:4
287:4
288:5
289:5
290:9
291:3
292:3
293:0
294:1
295:1
296:3
297:0
298:2
299:1
300:1
301:0
302:4
303:5
304:3
305:7
306:4
307:8
308:1
309:1
310:2
311:0
312:3
313:1
314:1
315:0
316:3
317:3
318:2
319:2
320:4
321:4
322:5
323:5
324:9
325:3
326:3
327:0
328:1
329:1
330:3
331:0
332:2
333:1
334:1
335:0
336:4
337:5
338:3
339:7
340:4
341:8
342:1
343:1
344:2
345:0
346:3
347:1
348:1
349:0
350:3
351:3
352:2
353:2
354:4
355:4
356:5
357:5
358:9
359:3
360:3
361:0
362:1
363:1
364:3
365:0
366:2
367:1
368:1
369:0
370:4
371:5
372:3
373:7
374:4
375:8
376:1
377:1
378:2
379:0
380:3
381:1
382:1
383:0
384:3
385:3
386:2
387:2
388:4
389:4
390:5
391:5
392:9
393:3
394:3
395:0
396:1
397:1
398:3
399:0
400:2
401:1
402:1
403:0
404:4
405:5
406:3
407:7
408:4
409:8
410:1
411:1
412:2
413:0
414:3
415:1
416:1
417:0
418:3
419:3
420:2
421:2
422:4
423:4
424:5
425:5
426:9
427:3
428:3
429:0
430:1
431:1
432:3
433:0
434:2
435:1
436:1
437:0
438:4
439:5
440:3
441:7
442:4
443:8
444:1
445:1
446:2
447:0
448:3
449:1
450:1
451:0
452:3
453:3
454:2
455:2
456:4
457:4
458:5
459:5
460:9
461:3
462:3
463:0
464:1
465:1
466:3
467:0
468:2
469:1
470:1
471:0
472:4
473:5
474:3
475:7
476:4
477:8
478:1
479:1
480:2
481:0
482:3
483:1
484:1
485:0
486:3
487:3
488:2
489:2
490:4
491:4
492:5
493:5
494:9
495:3
496:3
497:0
498:1
499:1
500:3
YES
NO
*/
```
:::
## 心路历程（WA，TLE，MLE……）
SG 函数
有的时候你得到的规律可能会发生裂化，这个时候一定要校验。
```cpp
vii sg(1110);
ll SG(ll x) {
if (x <= 200)
return sg[x];
ll idx=36+(x-36)%34;
if(idx==52){
return sg[idx+34];
}
return sg[idx];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> lT;
sg[0] = 0;
sg[1] = 0;
FOR(i, 2, 500) {
set<ll> s;
FOR(j, 0, i - 2) { s.insert(sg[j] ^ sg[i - j - 2]); }
ll mex = 0;
while (s.count(mex))
mex++;
sg[i] = mex;
}
#ifdef LOCAL
FOR(i,0,500){
cerr<<i<<":"<<sg[i]<<"\n";
}
FOR(i,201,500){
if(SG(i)!=sg[i]){
cout<<"错误出现在"<<i<<" SG:"<<SG(i)<<" sg:"<<sg[i] <<"\n";
cout<<" 36+(x-36)%34:"<<36+(i-36)%34<<"\n";
}
}
#endif
while (lT--)
__();
return 0;
}
```
```cpp
ll up = *s.begin();
ll ans = 0;
if (up != 0) {
ans ^= SG(up - 1);
}
for (auto it = next(s.begin()); it != s.end(); ++it) {
ll p = *it;
ll num = p - up - 1;
up = p;
ans ^= SG(num);
}
#ifdef LOCAL
_print(s);
#endif
if (*s.rbegin() != N - 1) {
ll num = N - 1 - *s.rbegin();
#ifdef LOCAL
debug(num);
#endif
ans ^= SG(num);
}
if (ans) {
yyy;
} else {
nnn;
}
```
hack 数据：
```cpp
1
8 2
0 1
4 5
YES
```