Znzryb's Blog
0%

Posted on Edited on

思路讲解

  1. 单条边的传输关系是单调的
    对一条漏水系数为 w 的边，从上游输入 x，到下游得到 x - ⌊x/w⌋；这是关于 x 的非减函数。
    因而“想让下游至少得到 need”的逆运算也是单调：最小的上游输入 x 满足 x - ⌊x/w⌋ ≥ need。你代码里的 get(need, w) 就是在做这件事（通过二分求最小可行 x）。

  2. 一次修边只能选择一条路径上的一条边
    每天只走“根→某个节点”的一条简单路径，因此修哪条边只会影响包含该边的那些路径。
    若我们要求所有**“弱点”节点**（即 R[u] < 目标值 mid 的节点）都至少收到 mid，那么被修的那条边必须同时位于它们各自的从根到该点路径上。
    这些路径的公共部分正是 根→(所有弱点的 LCA) 的路径。所以：

必要条件：可行的被修边一定在 root → anc 这条路径上，其中 anc 是所有 R[u]<mid 的节点的 LCA。

  1. 把“树下游的要求”折算为“对 anc 入水量的要求”
    如果我们暂时不修边，问：“从 anc 向下，把整棵以 anc 为根的子树都喂到 ≥ mid，需要 anc 处至少有多少输入？”
    由于每条边的传输是单调的，这个“所需的 anc 输入量”是单调的，可以二分出最小可行值 need_at_anc。
    你用 dfs2(anc, candidate, mid) 来判定“给 anc 值为 candidate 时，子树是否都 ≥ mid”，并对 candidate 二分拿到最小的 need_at_anc。这一步只会遍历 anc 的子树，而不是整棵树，所以可控。

  2. 把 anc 的需求一路往上折算，看是否能借“修一条边”满足
    假设我们已经知道：只要 anc 处能拿到至少 need_at_anc 的输入，它子树就都 OK。
    现在看 root → anc 这条路径。我们在这条路径上自下而上地把需求往上游推：

  • 当前在节点 node 处需要 need；让 fa=node 的父亲，边权 w=A[node]。
  • 若修边选在 (fa,node) 上，则 node 能直接拿到 R[fa]（因为这条边不再漏水）。于是只要 R[fa] ≥ need 就已经满足了——这就是你代码里的“只要某一层祖先的 R[ancestor] ≥ need****，我们就能在这个祖先与其子之间修边，一步到位”的判定。
  • 否则，如果暂时不修这条边，就要通过这条漏水边把 need 推到父亲处，父亲的所需输入变为 get(need, w)。继续往上迭代，直到找到某个祖先 y 满足 R[y] ≥ 当前 need，那么在 (y, its child) 修边即可；若最终到根也没有成功，则该 mid 不可行。

这正是你 check(mid) 的核心：

  • 先找弱点集合 wp = { i | R[i] < mid }，若空则已可行。

  • 把 anc = LCA(wp 所有点)。

  • 对 anc 的所需输入二分最小可行 need_at_anc（用 dfs2 验证）。

  • 把 need_at_anc 沿 anc→root 方向往上折算：

    • 若某处祖先的原始 R[ancestor] ≥ 当前 need → 可在它与子之间修边，成功；
    • 否则用 get(need, w) 把需求继续往上推；
    • 推到顶都不行则失败。

于是，一次修边能否让所有点 ≥ mid 被转换为上述流程的一个布尔判断。

AC代码

AC

https://www.codechef.com/viewsolution/1194966856

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

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