Znzryb's Blog
0%

Posted on Edited on

思路讲解

难点其实就在与这个想到把

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
vector<vll> valids(SZ(seg));
FOR(i, 0, SZ(seg) - 1) {
    auto [hs, len] = seg[i];
    FOR(j, 0, SZ(s) - 1) {
        if (len + j - 1 >= SZ(s)) {
            break;
        }
        ll r = len + j - 1;
        if (cal(hss, j, r) == hs) {
            valids[i].PB(j);
        }
    }
    if (valids[i].empty()) {
        cout << 0 << "\n";
        return;
    }
}
// 特判没有*的情况
if (!have) {
    cout << SZ(valids[0]) << "\n";
    return;
}
ll ans = 0;
// *之间的这个长度是一定的
if (t.back() == '*' && t.front() == '*') {
    ll on = SZ(s) - 1;
    ROF(i, SZ(valids.back()) - 1, 0) {
        ll p = valids.back()[i];
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        ll ed = p + seg.back()[1] - 1;
        ans += (up - 0 + 1) * (on - ed + 1);
        on = ed - 1;
    }
} else if (t.back() == '*') {
    ll on = SZ(s) - 1;
    ROF(i, SZ(valids.back()) - 1, 0) {
        ll p = valids.back()[i];
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        ll ed = p + seg.back()[1] - 1;
        auto t = lower_bound(all(valids[0]), up) - valids[0].begin() + 1;
        ans += t * (on - ed + 1);
        on = ed - 1;
    }
} else if (t.front() == '*') {
    for (auto p : valids.back()) {
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        ans += up - 0 + 1;
    }
} else {
    for (auto p : valids.back()) {
        bool ok = true;
        ll up = p;
        ROF(j, SZ(seg) - 2, 0) {
            ll len = seg[j][1];
            auto it = upper_bound(all(valids[j]), up - len);
            if (it == valids[j].begin()) {
                ok = false;
                break;
            }
            it--;
            up = *it;
        }
        if (!ok) {
            continue;
        }
        auto t = lower_bound(all(valids[0]), up) - valids[0].begin() + 1;
        ans += t;
    }
}
cout << (long long)ans;

AC代码

https://qoj.ac/submission/1395803

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

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

Posted on Edited on

思路讲解

https://chatgpt.com/share/68cf5c55-f5c8-8013-b94f-360aabb163b8

这道题目就是懒更新，一般来说，塞进懒更新库的是比较乐观的估计，或者说是比较好的估计。

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
priority_queue<Val> pq;
multiset<ll> s{A[0]}, rem(A.begin() + 1, A.end());
ll ans = 0;
auto add = [&](ll x) {
    auto it = rem.lower_bound(K-x);
    if (it == rem.end())
        return;
    pq.push({x, x + *it - K});
};
auto find = [&](ll x) {
    auto it = rem.lower_bound(K - x);
    if (it == rem.end())
        return INF;
    return *it;
};
auto get = [&]() {
    while (!pq.empty()) {
        auto [val, res] = pq.top();
        ll node = find(val);
        ll lres = node + val - K;
        if (lres == res) {
            return (pll){res, node};
        } else {
            pq.pop();
            pq.push({val, lres});
        }
    }
    return (pll){INF, INF};
};
add(A[0]);
FOR(i, 2, N) {
    ll lans = *s.begin() + *rem.begin();
    auto [res, node] = get();
    if (res < lans) {
        lans = res;
        s.insert(node);
        rem.erase(rem.find(node));
        add(node);
    } else {
        ll node=*rem.begin();
        s.insert(node);
        rem.erase(rem.begin());
        add(node);
    }
    ans += lans;
}

AC代码

https://qoj.ac/submission/1381898

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

Posted on Edited on

思路讲解

我发现，这个还是要解偶，就是说，我们要得到放的种类数，但是这个“种类”，就是第 1 小的数字放在哪里，第 2 小的数字放在哪里，。。。，第 n 小的数字放在哪里。其中具体放什么数字，直接从这个他后面的数字中取就可以了。

AC代码

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

会算多的想法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i=4;i<=N;i+=2){

    // 这个代码的问题在于不是所有的都能换
    // 只有处于末尾位置的节点才可以换
    FOR(k,1,N){
        if(i-2-k<0) break;
        dp[i]+=dp[i-2]*(i-2-k)*2;
        dp[i]+=dp[i-2];
        dp[i]%=mod;
    }

    // 分母是 （i-1）！
    ans[i]=dp[i]*inv[i-1];
    ans[i]%=mod;
}

但是我认为总体大思路是没有问题的，其实难点就在于如何知道可以更换的末尾节点有多少个。