Znzryb's Blog
0%

第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——连线博弈

Posted on Edited on

思路讲解

一个比较好的博客。

https://blog.csdn.net/notonlysuccess/article/details/130959107

2025“钉耙编程”中国大学生算法设计暑期联赛（3）

随机化做法与随机值异或的应用。

其实就是求被不同区间覆盖的不同情况数量。

当然这道题目有所不同，不过也差不多。

一种更加方便的实现。

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
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

心路历程（WA，TLE，MLE……）

SG 函数

有的时候你得到的规律可能会发生裂化，这个时候一定要校验。

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
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;
}
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
    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 数据：

1
2
3
4
5
6
1
8 2
0 1
4 5

YES