假期练习 #1

大致内容

起因是 Hello 2025 中的一道图上 K-th 问题，然后就想着去找一点类似的题来做

T1.0 Another Exercise on Graphs (hard version)

万恶之源

题意概述

给定一张简单无向带权图（无自环无重边），多次询问 $x$ 到 $y$ 的所有路径中第 $K$ 大边的最小值。

解题思路

简直是在变魔法

因为答案一定会是某一条边，所以可以枚举答案
每次枚举一条边就把小于等于这条边权值的边的 “代价” 看作 0，其他边的 “代价” 看作 1，然后对 $x$ 和 $y$ 求最短路长度，如果 $x$ 和 $y$ 间的最短路长度小于 $K$ ，那么就说明答案比当前边的权值小（因为存在一条路径以这条边为第 $K$ 大的边）
我们可以从小到大来枚举边，这样每次只需要改变一条边对应的 “代价”，对于某一对 $x$ ， $y$ ， $K$ ，答案就是枚举过程中第一个满足条件的边的权值
由于任何时刻，最短路长度不会低于 0，考虑将边权为 0 的边的两个端点 “缩在一起”，只有在这些新点之间的边才是有贡献的，那就很自然地想到这和 Kruskal 法求取最小生成树是等价的
所以只需要枚举 MST 上的 n-1 条边

AC 代码

c++

#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef vector<vector<vector<ll>>> v3ll;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

ll get_fa(vll &fa, ll x) {
    if (x == fa[x])
        return x;
    else
        return fa[x] = get_fa(fa, fa[x]);
}

void solve() {
    ll n, m, q;
    cin >> n >> m >> q;

    vll fa(n + 1);
    vector<tuple<ll, ll, ll>> eg;

    v2ll dis(n + 1, vll(n + 1, INF));

    v3ll ans(n + 1, v2ll(n + 1, vll(n + 1, INF)));

    for (ll i = 1; i <= n; i++)
        fa[i] = i, dis[i][i] = 0;

    for (ll i = 1; i <= m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = 1;
        eg.emplace_back(make_tuple(u, v, w));
    }

    sort(eg.begin(), eg.end(),
         [](tuple<ll, ll, ll> a, tuple<ll, ll, ll> b) {
             auto [x1, y1, z1] = a;
             auto [x2, y2, z2] = b;
             return z1 < z2;
         });

    //	for(auto [x,y,z]:eg){
    //		OOO
    //		cout<<x<<' '<<y<<' '<<z<<endl;
    //	}

    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            for (ll k = 1; k <= n; k++) {
                dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
            }
        }
    }

    for (ll k = 0; k < m; k++) {

        auto [u, v, w] = eg[k];
        if (get_fa(fa, u) == get_fa(fa, v))
            continue;

        for (ll i = 1; i <= n; i++) {
            for (ll j = i + 1; j <= n; j++) {
                dis[i][j] = dis[j][i] =
                    min(dis[i][j],
                        min(dis[i][u] + dis[v][j], dis[i][v] + dis[u][j]));
                ans[i][j][dis[i][j] + 1] = ans[j][i][dis[i][j] + 1] =
                    min(ans[i][j][dis[i][j] + 1], w);
            }
        }
        fa[get_fa(fa, v)] = get_fa(fa, u);
    }

    //	OOO

    while (q--) {
        ll u, v, k;
        cin >> u >> v >> k;
        cout << ans[u][v][min(k, n - 1)] << ' ';
    }

    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt; // 非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}

T1.1 P2048 [NOI2010] 超级钢琴

题意概述

求一个数列中长度在 $[L, R]$ 范围内的连续子串和的前 $K$ 大值之和

解题思路

前提结论：

可以通过逐步取最大值的方法得到答案
每个阶段的最大值一定在以某一点 $i$ 为左端点的最值方案中

所以，用前缀和优化子串求和，问题转化为前缀和数组中前 $K$ 大个数对的差值

也就不难想到用 ST 表 实现速查区间最值，用于在确定左端点时求最值

先把所有端点对应的最值存入 set

记录为 ${s, t, l, r}$ ，即这个方案的起点 $s$ ，终点范围 $l & r$ ，取到的最值位置 $t$

每次取出最值，再把 ${s, t^{'}, l, t - 1}$ 和 ${s, t^{″}, t + 1, r}$ 存入 set

就能保证每一时刻，以任意为左端点的最值都在 set 内，进而全局最值也在

每次取最大值的开销是 $\log n$ 级别，取 $k$ 次，预处理 st 表是 $n \log n$ 级别

整体时间复杂度 $Θ ((n + k) \log n)$

AC 代码

c++

#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

struct Elm {
    ll s, t, l, r, key;
    bool operator<(const Elm &a) const { return key > a.key; }
};

void solve() {
    ll n, k, L, R, ans = 0;
    cin >> n >> k >> L >> R;

    vector<ll> v(n + 1, 0);
    v2ct<ll> st(n + 1, vector<ll>(21, 0));
    multiset<Elm> hp;

    for (ll i = 1; i <= n; i++) {
        cin >> v[i];
        v[i] += v[i - 1];
        st[i][0] = i;
    }

    for (ll k = 1; k <= 20; k++)
        for (ll i = 1; i <= n; i++) {
            ll g = min(n, i + (1 << (k - 1)));
            st[i][k] = (v[st[i][k - 1]] >= v[st[g][k - 1]] ? st[i][k - 1]
                                                           : st[g][k - 1]);
        }

    function<ll(ll, ll)> get_max = [&](ll l, ll r) {
        ll g = __lg(r - l + 1);
        ll w = (g == -1 ? 0 : (1 << g));
        if (g == -1)
            g++;
        return v[st[l][g]] >= v[st[r - w + 1][g]] ? st[l][g]
                                                  : st[r - w + 1][g];
    };

    function<void(ll, ll, ll)> cstr = [&](ll s, ll l, ll r) {
        if (l > r)
            return;

        Elm tmp = {};
        tmp.s = s;
        tmp.l = l;
        tmp.r = r;
        tmp.t = get_max(tmp.l, tmp.r);
        tmp.key = v[tmp.t] - v[s - 1];

        hp.insert(tmp);
    };

    for (ll i = 1; i <= n && i + L - 1 <= n; i++)
        cstr(i, i + L - 1, min(n, i + R - 1));

    for (ll i = 1; i <= k; i++) {
        Elm cur = *hp.begin();
        hp.erase(hp.begin());
        ans += cur.key;

        cstr(cur.s, cur.l, cur.t - 1);
        cstr(cur.s, cur.t + 1, cur.r);
    }

    //	OOO
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}

T1.2 P5283 [十二省联考 2019] 异或粽子

什么逆天题目折磨我整整一天半

前置知识

可持久化权值线段树，可持久化字典树，01-Trie，树上二分思想

解法思路

看到这道题，就觉得和上面那道超级钢琴很像，都是前 $K$ 大值之和

思考一下，发现完全可以把相同的解法模式套到这道题上：

首先，用前缀异或和优化子串求异或和，问题转化为前缀异或和数组中前 $K$ 大个数对的异或值
然后对于每个位置，求出固定其为左端点时的最优策略，同样记为 ${s, t, l, r}$ ，即这个方案的起点 $s$ ，终点范围 $l & r$ ，取到的最值位置 $t$
把所有端点对应的最值存入 set
每次取出最值，再把 ${s, t^{'}, l, t - 1}$ 和 ${s, t^{″}, t + 1, r}$ 存入 set
就能保证每一时刻，以任意为左端点的最值都在 set 内，进而全局最值也在

先把所有端点对应的最值存入 set

记录为 ${s, t, l, r}$ ，即这个方案的起点 s，终点范围 l&r，取到的最值位置 t

每次取出最值，再把 ${s, t^{'}, l, t - 1}$ 和 ${s, t^{″}, t + 1, r}$ 存入 set

就能保证每一时刻，以任意为左端点的最值都在 set 内，进而全局最值也在

但是，有一个问题：

在上一个问题中，我们可以通过 ST 表 快速求取确定左端点时的最值及其对应的右端点；
而在这一个问题当中要求的变成了最大异或和，这不是一个 RMQ 问题，应该怎么快速解决

>> 隆重介绍：01-Trie

这是一个字符集只有 0/1 的 Trie，在确定一个数后，可以在给定的数集中快速找到异或最大值

怎么做？每次尽量取和 key 值这一位上相反的即可

但是我们不止要取全局最值，还要取给定区间内的最值。这又怎么办？

答：在要求的时候，如果我们能够 “变出一个” 恰以我们这个区间为 “全局” 的 01-Trie 呢？是不是就能解决问题了？

这么一说，熟不熟悉？

可持久化字典树，堂堂开启！

问题解决！！！

AC 代码

c++

#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

struct Ps_Trie { // 封装好的可持久化字典树 01 Trie

    struct Node {
        ll s[2], key, num;
        Node() { s[0] = s[1] = key = 0; }
    };

    ll cnt = 0;
    vector<Node> tree;
    vector<ll> root;

    Ps_Trie() {
        cnt = 0;
        tree.assign(2, Node());
        root.assign(2, 0);
    }

    void add_num(ll &rt, ll pre, ll key,
                 ll id) { // 插入一个新数 版本数增加一
        rt = ++cnt;
        ll o = rt;

        root.emplace_back(0);
        tree.emplace_back(Node());

        for (ll i = 31; i >= 0; i--) {

            ll g = (1ll << i);
            tree[o].key = tree[pre].key + 1;

            if (key & g) {
                tree[o].s[1] = ++cnt;
                tree.emplace_back(Node());

                tree[o].s[0] = tree[pre].s[0];
                o = tree[o].s[1];
                pre = tree[pre].s[1];
            } else {
                tree[o].s[0] = ++cnt;
                tree.emplace_back(Node());

                tree[o].s[1] = tree[pre].s[1];
                o = tree[o].s[0];
                pre = tree[pre].s[0];
            }
        }
        tree[o].key = tree[pre].key + 1;
        tree[o].num = id;
        //		cout<<key<<' '<<tree[o].key<<endl;
    }

    ll query_mxor(
        ll l, ll r,
        ll key) { // 在版本 [l,r] 中查找与 key 异或值最大的数 *的下标
        if (r < l)
            swap(l, r);
        ll res = 0, o1 = root[max(l - 1, 0ll)], o2 = root[r];
        for (ll i = 31; i >= 0; i--) {

            ll g = (1ll << i);
            ll t = (key & g ? 1 : 0);
            if (tree[tree[o2].s[!t]].key - tree[tree[o1].s[!t]].key > 0) {
                res += g;
                o2 = tree[o2].s[!t];
                o1 = tree[o1].s[!t];
            } else {
                o2 = tree[o2].s[t];
                o1 = tree[o1].s[t];
            }
        }
        //		cout<<endl;
        //		cout<<tree[o2].num<<endl;
        return tree[o2].num;
    }
};

struct Elm {
    ll s, t, l, r, key;
    bool operator<(const Elm &a) const { return key > a.key; }
};

void solve() {
    ll n, k, ans = 0;
    cin >> n >> k;

    Ps_Trie tr = Ps_Trie();
    vector<ll> v(n + 1);
    multiset<Elm> hp;

    for (ll i = 1; i <= n; i++) {
        cin >> v[i], v[i] ^= v[i - 1];
        tr.add_num(tr.root[i], tr.root[i - 1], v[i], i);
    }

    function<void(ll, ll, ll)> cstr = [&](ll s, ll l, ll r) {
        if (l > r)
            return;

        Elm tmp = {};
        tmp.s = s;
        tmp.l = l;
        tmp.r = r;
        tmp.t = tr.query_mxor(l, r, v[s - 1]);
        tmp.key = v[tmp.t] ^ v[s - 1];

        hp.insert(tmp);
    };

    for (ll i = 1; i <= n; i++)
        cstr(i, i, n);

    while (k--) {
        Elm tmp = *hp.begin();
        hp.erase(hp.begin());
        ans += tmp.key;

        cstr(tmp.s, tmp.l, tmp.t - 1);
        cstr(tmp.s, tmp.t + 1, tmp.r);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}

注

在这份代码中，我为可持久化数据结构引入了完全随用随开的动态开点，又由于涉及引用与指针，以及 vector 动态分配空间的玄学操作，尽量不要改动其中开辟新节点和为变量赋值的顺序，容易引起玄学问题

后记

骄傲的人类总以阅历的浅薄或时间的短暂充当辩护的陈词。懒惰是他们固有的过失，以命运为托辞而放弃对瓶颈的征服使生命丧失了它的全部价值。罔顾足够的实践和积淀，所感知的自我全能性总会被极度过分地夸大，而他们所没有意识到或不愿承认的是，即便虚无的预设得到满足，他们也无法完成被轻视的任务。人类社会的繁衍生息是恒定生命节律中相似的循环，而在回溯类比前人足迹的过程中很容易明晰个体的定位。当信息差被抹平而数据将人击溃，应当理解令人失望的处境而投身义务的工作。（摘自王公随笔一则）

假期练习 #1 ​

大致内容 ​

T1.0 Another Exercise on Graphs (hard version) ​

题意概述 ​

解题思路 ​

AC 代码 ​

T1.1 P2048 [NOI2010] 超级钢琴 ​

题意概述 ​

解题思路 ​

AC 代码 ​

T1.2 P5283 [十二省联考 2019] 异或粽子 ​

前置知识 ​

解法思路 ​

>> 隆重介绍：01-Trie ​

AC 代码 ​

注 ​

后记 ​

假期练习 #1

大致内容

T1.0 Another Exercise on Graphs (hard version)

题意概述

解题思路

AC 代码

T1.1 P2048 [NOI2010] 超级钢琴

题意概述

解题思路

AC 代码

T1.2 P5283 [十二省联考 2019] 异或粽子

前置知识

解法思路

>> 隆重介绍：01-Trie

AC 代码

注

后记