推荐

GESP C++ 八级历年真题题解

_Separation 2026-5-17 20:35:36 19 浏览 0 点赞 0 收藏
#GESP

GESP C++ 八级历年真题题解

1. 区间

题目大意

给定长度为 nn 的序列 AA，有 qq 次询问，每次给出 l,r,xl,r,x，要求统计 xx 在区间 Al,Al+1,…,ArA_l,A_{l+1},\dots,A_r 中出现了多少次。

解题思路

对每个数值 xx，记录它在序列中出现的所有下标，并保持升序。

对于询问 l,r,xl,r,x，只需要在 xx 的下标数组中二分：

ans=#{pos∣l≤pos≤r}\text{ans}=\#\{pos\mid l\le pos\le r\}

也就是：

upper_bound(r)−lower_bound(l)\text{upper\_bound}(r)-\text{lower\_bound}(l)

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, q;
inline void solve() {
    cin >> n;
    map<int, vector<int> > mp;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        mp[x].push_back(i);
    }
    cin >> q;
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        if (!mp.count(x)) {
            printf("0\n");
            continue;
        }
        vector<int> &v = mp[x];
        int Ans = upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l);
        printf("%d\n", Ans);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

2. 小杨的旅游

题目大意

给定一棵 nn 个点的树，部分城市有传送门。任意两个传送门城市之间可以花费 00 时间互相传送。每次询问从 uu 到 vv 的最短时间。

解题思路

从 uu 到 vv 有两种方案：

  1. 直接在树上走，距离为：
dist(u,v)dist(u,v)
  1. 从 uu 走到最近的传送门，传送到另一个传送门，再走到 vv：
near(u)+near(v)near(u)+near(v)

其中 near(x)near(x) 表示点 xx 到最近传送门的树上距离。

所以答案为：

min⁡(dist(u,v),near(u)+near(v))\min(dist(u,v), near(u)+near(v))

树上距离用 LCA\text{LCA} 求，最近传送门距离用多源 BFS\text{BFS} 求。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k, q;
vector<int> G[N];
int dep[N], fa[20][N];
int dis[N];
void bfs_dep() {
    queue<int> que;
    que.push(1);
    dep[1] = 1;
    fa[0][1] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : G[u]) {
            if (v == fa[0][u]) continue;
            fa[0][v] = u;
            dep[v] = dep[u] + 1;
            que.push(v);
        }
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            fa[j][i] = fa[j - 1][fa[j - 1][i]];
        }
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for (int j = 19; j >= 0; j--) {
        if ((d >> j) & 1) x = fa[j][x];
    }
    if (x == y) return x;
    for (int j = 19; j >= 0; j--) {
        if (fa[j][x] != fa[j][y]) {
            x = fa[j][x];
            y = fa[j][y];
        }
    }
    return fa[0][x];
}
int dist(int x, int y) {
    int z = lca(x, y);
    return dep[x] + dep[y] - 2 * dep[z];
}
inline void solve() {
    cin >> n >> k >> q;
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs_dep();
    queue<int> que;
    for (int i = 1; i <= n; i++) dis[i] = inf;
    for (int i = 1, x; i <= k; i++) {
        cin >> x;
        dis[x] = 0;
        que.push(x);
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : G[u]) {
            if (dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
        }
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        int Ans = dist(u, v);
        if (k > 0) Ans = min(Ans, dis[u] + dis[v]);
        printf("%d\n", Ans);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

3. 奖品分配

题目大意

有 NN 名同学和 MM 种奖品，第 ii 种奖品有 aia_i 个。每位同学恰好获得一个奖品，剩余奖品不超过 11 个。求分配方案数，对 109+710^9+7 取模。

解题思路

若：

S=a0+a1+⋯+aM−1S=a_0+a_1+\cdots+a_{M-1}

题目保证：

N≤S≤N+1N\le S\le N+1

如果 S=NS=N，所有奖品都用完，方案数为多重排列：

N!a0!a1!⋯aM−1!\frac{N!}{a_0!a_1!\cdots a_{M-1}!}

如果 S=N+1S=N+1，会剩下一个奖品。枚举剩下的是哪一种，等价于：

N!a0!a1!⋯aM−1!×S\frac{N!}{a_0!a_1!\cdots a_{M-1}!}\times S

因为每种奖品作为剩余奖品的贡献系数为 aia_i，总和为 SS。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2005;
const LL mod = 1000000007;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL fac[N], inv[N];
LL qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline void solve() {
    cin >> n >> m;
    LL Ans = fac[n];
    int sum = 0;
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        sum += x;
        Ans = Ans * inv[x] % mod;
    }
    if (sum == n + 1) Ans = Ans * sum % mod;
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

4. 大量的工作沟通

题目大意

公司结构是一棵以 00 为根的有根树。一次合作给出若干员工，要求找一个能管理所有参与员工的员工；如果有多个，输出编号最大的。

解题思路

能管理所有参与员工的节点，就是这些员工的公共祖先。

所有公共祖先中，最深的公共祖先是这些点的 LCA\text{LCA}，但题目要的是 编号最大 ，而不是深度最大。

所有公共祖先就是 LCA\text{LCA} 的所有祖先。因此答案是：

LCA 到根路径上的最大编号LCA\text{ 到根路径上的最大编号}

预处理每个节点从根到它路径上的最大编号 mx[u]\text{mx[u]} 即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}

int n, q;
vector<int> G[N];
int dep[N], fa[20][N], mx[N];
void bfs() {
    queue<int> que;
    que.push(0);
    dep[0] = 1;
    fa[0][0] = 0;
    mx[0] = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int v : G[u]) {
            dep[v] = dep[u] + 1;
            fa[0][v] = u;
            mx[v] = max(mx[u], v);
            que.push(v);
        }
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            fa[j][i] = fa[j - 1][fa[j - 1][i]];
        }
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for (int j = 19; j >= 0; j--) {
        if ((d >> j) & 1) x = fa[j][x];
    }
    if (x == y) return x;
    for (int j = 19; j >= 0; j--) {
        if (fa[j][x] != fa[j][y]) {
            x = fa[j][x];
            y = fa[j][y];
        }
    }
    return fa[0][x];
}
inline void solve() {
    cin >> n;
    for (int i = 1, f; i < n; i++) {
        cin >> f;
        G[f].push_back(i);
    }
    bfs();
    cin >> q;
    while (q--) {
        int m, x;
        cin >> m >> x;
        int g = x;
        for (int i = 2; i <= m; i++) {
            cin >> x;
            g = lca(g, x);
        }
        printf("%d\n", mx[g]);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

5. 公倍数问题

题目大意

有一个 N×MN\times M 的矩阵，位置 (i,j)(i,j) 上的数必须是 ii 和 jj 的公倍数。对每个 k=1,2,…,Kk=1,2,\dots,K，求矩阵中最多有多少个元素可以是 kk，最后输出：

∑k=1Kk×ansk\sum_{k=1}^{K} k\times ans_k

解题思路

如果 Ai,jA_{i,j} 可以是 kk，那么 kk 必须同时是 ii 和 jj 的倍数，即：

i∣k,j∣ki\mid k,\quad j\mid k

所以：

$$ans_k=(k\text{ 在 }[1,N]\text{ 内的因数个数})\times(k\text{ 在 }[1,M]\text{ 内的因数个数}) $$

用类似筛法统计每个 kk 有多少个不超过 NN 的因数、多少个不超过 MM 的因数即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, k;
int dn[N], dm[N];
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= k; j += i) {
            dn[j]++;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = i; j <= k; j += i) {
            dm[j]++;
        }
    }
    LL Ans = 0;
    for (int i = 1; i <= k; i++) Ans += 1LL * i * dn[i] * dm[i];
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

6. 接竹竿

题目大意

给定卡牌序列。依次把牌放到队列末尾，若队列中已经有相同点数的牌，则把两张相同点数牌之间的所有牌全部取出，包括这两张牌。多次询问 [l,r][l,r]，问只用这段牌玩游戏后，最后剩余多少张牌。

点数范围为 1∼131\sim13。

解题思路

游戏过程中队列中不会存在两个相同点数的牌，因此队列长度最多为 1313。

对每个左端点 ll，从 ll 开始向右模拟到 nn，即可得到所有以 ll 为左端点的询问答案。

复杂度为：

O(n2+q)O(n^2+q)

然后必然超时。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 15010;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, q;
int a[N], Ans[N];
vector<pair<int, int> > qs[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        qs[i].clear();
    }
    cin >> q;
    for (int i = 1, l, r; i <= q; i++) {
        cin >> l >> r;
        qs[l].push_back({r, i});
    }
    for (int l = 1; l <= n; l++) {
        sort(qs[l].begin(), qs[l].end());
        int st[20] = {}, len = 0;
        int pos[14] = {0};
        int p = 0;
        for (int r = l; r <= n; r++) {
            int x = a[r];
            if (pos[x]) {
                int pp = pos[x];
                while (len >= pp) {
                    pos[st[len]] = 0;
                    len--;
                }
            } else {
                st[++len] = x;
                pos[x] = len;
            }
            while (p < (int)qs[l].size() && qs[l][p].first == r) {
                Ans[qs[l][p].second] = len;
                p++;
            }
        }
    }
    for (int i = 1; i <= q; i++) printf("%d\n", Ans[i]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

那么更好的解题思路：递推 + 分块跳跃

设：

f(l,r)f(l,r)

表示只玩区间 [l,r][l,r] 这段牌，最后剩余多少张牌。

考虑区间第一张牌 ala_l。

设 nxtlnxt_l 表示 ll 后面第一个满足：

anxtl=ala_{nxt_l}=a_l

的位置。

情况一：nxtl≤rnxt_l \le r

也就是 ala_l 在区间内会再次出现。

由于 nxtlnxt_l 是 ala_l 后面第一次出现的位置，所以在处理到 nxtlnxt_l 之前，ala_l 一定还在队列里。

当处理到 nxtlnxt_l 时，ala_l 到 anxtla_{nxt_l} 之间的所有牌都会被取走。

所以：

[l,nxtl][l,nxt_l]

这一整段处理完后，相当于什么都不剩。

于是：

f(l,r)=f(nxtl+1,r)f(l,r)=f(nxt_l+1,r)

情况二：nxtl>rnxt_l > r

也就是 ala_l 在区间内不会再次出现。

那么 ala_l 一定会留在最后队列里，剩下的就是处理 [l+1,r][l+1,r]。

所以：

f(l,r)=1+f(l+1,r)f(l,r)=1+f(l+1,r)

因此对于每个位置 ll，在固定右端点 rr 时，都可以看成一条 跳边 ：

如果 nxtl≤rnxt_l \le r：

l→nxtl+1,代价=0l \rightarrow nxt_l+1,\quad 代价=0

否则：

l→l+1,代价=1l \rightarrow l+1,\quad 代价=1

那么询问 [l,r][l,r] 的答案，就是从 ll 一直跳到 r+1r+1 的总代价。

关于动态维护方面，可以按右端点 rr 从小到大离线处理询问。

初始时，每个位置都是：

i→i+1,代价=1i \rightarrow i+1,\quad 代价=1

当扫描到位置 rr 时，设上一次出现同样点数的位置是 prepre。

那么此时：

nxtpre=rnxt_{pre}=r

所以位置 prepre 的跳边应该改成：

pre→r+1,代价=0pre \rightarrow r+1,\quad 代价=0

这是一个单点修改。

然后对于所有右端点为 rr 的询问，求从 ll 跳到 r+1r+1 的路径代价。

用分块维护每个位置跳出当前块的位置和代价，就可以做到：

  • 修改一个位置：O(n)O(\sqrt n)；
  • 查询一次：O(n)O(\sqrt n)。

这样的话整体复杂度约为：

O((n+q)n)O((n+q)\sqrt n)

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;

const int N = 15010;
const int B = 130;

int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, q, tot;
int a[N], fa[N], w[N], jp[N], sum[N];
int bl[N], L[N], R[N];
int Ans[N], lst[20];
void build(int b) {
    for (int i = R[b]; i >= L[b]; i--) {
        if (i == n + 1) {
            jp[i] = i;
            sum[i] = 0;
        } else if (bl[fa[i]] != b) {
            jp[i] = fa[i];
            sum[i] = w[i];
        } else {
            jp[i] = jp[fa[i]];
            sum[i] = w[i] + sum[fa[i]];
        }
    }
}
int ask(int l, int t) {
    int res = 0;
    while (bl[l] != bl[t]) {
        res += sum[l];
        l = jp[l];
    }
    while (l != t) {
        res += w[l];
        l = fa[l];
    }
    return res;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    vector<vector<pair<int, int> > > qs(n + 2);
    for (int i = 1, l, r; i <= q; i++) {
        cin >> l >> r;
        qs[r].push_back({l, i});
    }
    int len = n + 1;
    tot = (len + B - 1) / B;
    for (int b = 1; b <= tot; b++) {
        L[b] = (b - 1) * B + 1;
        R[b] = min(b * B, len);
        for (int i = L[b]; i <= R[b]; i++) {
            bl[i] = b;
        }
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i + 1;
        w[i] = 1;
    }
    fa[n + 1] = n + 1;
    w[n + 1] = 0;
    for (int b = tot; b >= 1; b--) {
        build(b);
    }
    for (int i = 1; i <= 13; i++) {
        lst[i] = 0;
    }
    for (int r = 1; r <= n; r++) {
        int x = a[r];
        if (lst[x]) {
            int p = lst[x];
            fa[p] = r + 1;
            w[p] = 0;
            build(bl[p]);
        }
        lst[x] = r;
        for (auto it : qs[r]) {
            int l = it.first;
            int id = it.second;
            Ans[id] = ask(l, r + 1);
        }
    }
    for (int i = 1; i <= q; i++) printf("%d\n", Ans[i]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

7. 最远点对

题目大意

给定一棵树，每个节点为黑色或白色。求一对白色、黑色不同颜色节点之间的最大距离。

解题思路

要求：

max⁡u∈白点,v∈黑点dist(u,v)\max_{u\in 白点,v\in 黑点} dist(u,v)

先找出黑点集合的直径端点 A,BA,B。

树上有性质：对于任意点 xx，它到黑点集合中最远点的距离一定是：

max⁡(dist(x,A),dist(x,B))\max(dist(x,A),dist(x,B))

所以枚举所有白点，取最大值即可。

若黑白反过来也可以，题目保证两种颜色都存在。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int c[N], dis[N];
vector<int> G[N];
void bfs(int s) {
    for (int i = 1; i <= n; i++) dis[i] = -1;
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : G[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
}
int fc(int col) {
    int res = -1;
    for (int i = 1; i <= n; i++) {
        if (c[i] == col && (res == -1 || dis[i] > dis[res])) {
            res = i;
        }
    }
    return res;
}
inline void solve() {
    cin >> n;
    int st = -1;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        if (c[i] == 1) st = i;
    }
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(st);
    int A = fc(1);
    bfs(A);
    int B = fc(1);
    vector<int> da(n + 1), db(n + 1);
    bfs(A);
    for (int i = 1; i <= n; i++) da[i] = dis[i];
    bfs(B);
    for (int i = 1; i <= n; i++) db[i] = dis[i];
    int Ans = 0;
    for (int i = 1; i <= n; i++) {
        if (c[i] == 0) {
            Ans = max(Ans, max(da[i], db[i]));
        }
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

8. 空间跳跃

题目大意

二维空间中有若干水平挡板。人在挡板上可以左右移动，走出左端点或右端点后会竖直下落到下方第一个挡板上。移动和下落都消耗时间。求从第 ss 个挡板左端点出发，到达第 tt 个挡板的最短时间；无法到达输出 −1-1。

解题思路

把每个挡板的左端点和右端点看成两个状态。

状态之间有两类边：

  1. 同一挡板左右端点互相移动，代价为：
ri−lir_i-l_i
  1. 从端点竖直下落到下方第一个挡板，代价为高度差。落到某挡板后，如果要继续移动，还要移动到该挡板的左右端点。

因为边权非负，用 Dijkstra\text{Dijkstra} 求最短路。

如果下落直接落到目标挡板，可以直接更新答案，不一定要走到目标挡板端点。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2010;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Seg {
    LL l, r, h;
};
struct Node {
    LL d;
    int u;
    bool operator < (const Node &o) const {
        return d > o.d;
    }
};
int n, s, t;
Seg a[1010];
LL dis[N];
int id(int i, int side) {
    return (i - 1) * 2 + side;
}
int below(LL x, LL h) {
    int res = 0;
    LL best = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i].h < h && a[i].l <= x && x <= a[i].r) {
            if (a[i].h > best) {
                best = a[i].h;
                res = i;
            }
        }
    }
    return res;
}
inline void solve() {
    cin >> n >> s >> t;
    for (int i = 1; i <= n; i++) cin >> a[i].l >> a[i].r >> a[i].h;
    if (s == t) {
        printf("0\n");
        return;
    }
    for (int i = 1; i <= 2 * n; i++) dis[i] = inf;
    priority_queue<Node> q;
    dis[id(s, 1)] = 0;
    q.push({0, id(s, 1)});
    LL Ans = inf;
    while (!q.empty()) {
        Node cur = q.top(); q.pop();
        int u = cur.u;
        LL d = cur.d;
        if (d != dis[u]) continue;
        int p = (u + 1) / 2, side = (u - 1) % 2 + 1, other = id(p, 3 - side);
        LL len = a[p].r - a[p].l;
        if (dis[other] > d + len) {
            dis[other] = d + len;
            q.push({dis[other], other});
        }
        LL x = (side == 1 ? a[p].l : a[p].r);
        int b = below(x, a[p].h);
        if (b) {
            LL drop = a[p].h - a[b].h;
            if (b == t) Ans = min(Ans, d + drop);
            LL toL = drop + x - a[b].l, toR = drop + a[b].r - x;
            if (dis[id(b, 1)] > d + toL) {
                dis[id(b, 1)] = d + toL;
                q.push({dis[id(b, 1)], id(b, 1)});
            }
            if (dis[id(b, 2)] > d + toR) {
                dis[id(b, 2)] = d + toR;
                q.push({dis[id(b, 2)], id(b, 2)});
            }
        }
    }
    Ans = min(Ans, dis[id(t, 1)]); Ans = min(Ans, dis[id(t, 2)]);
    if (Ans == inf) printf("-1\n");
    else printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

9. 手套配对

题目大意

有 nn 对不同手套，每对有左手和右手。问从 2n2n 只手套中取出 mm 只，恰好包含 kk 对完整手套的方案数。

解题思路

先选出哪 kk 对手套完整取出：

(nk)\binom{n}{k}

已经取了 2k2k 只，还需要取：

m−2km-2k

只单只手套。

这些单只手套必须来自剩下 n−kn-k 对，并且每对最多取一只。

所以方案数为：

(nk)(n−km−2k)2m−2k\binom{n}{k}\binom{n-k}{m-2k}2^{m-2k}

若 m−2k<0m-2k < 0 或 m−2k>n−km-2k > n-k，答案为 00。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2010;
const LL mod = 1000000007;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL fac[N], inv[N], pw[N];
LL qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
LL C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
    pw[0] = 1;
    for (int i = 1; i < N; i++) pw[i] = pw[i - 1] * 2 % mod;
}
int n, m, k;
inline void solve() {
    cin >> n >> m >> k;
    int rest = m - 2 * k;
    if (rest < 0 || rest > n - k) {
        printf("0\n");
        return;
    }
    LL Ans = C(n, k) * C(n - k, rest) % mod * pw[rest] % mod;
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

10. 美丽路径

题目大意

给定一棵树，每个节点为黑色或白色。若路径上相邻节点颜色均不同，则称为美丽路径。求最长美丽路径的长度，长度按节点数计算。

解题思路

只保留颜色不同的边。

原树变成若干个森林连通块。每个连通块中的任意路径都是美丽路径。

所以答案就是这个森林中所有连通块直径的最大节点数。

对每个连通块做两次 BFS\text{BFS} 求直径即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int c[N], vis[N], dis[N];
vector<int> G[N], H[N];
pair<int, int> bfs(int s) {
    queue<int> q;
    vector<int> vec;
    q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    vec.push_back(s);
    int far = s;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (dis[u] > dis[far]) far = u;
        for (int v : H[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                dis[v] = dis[u] + 1;
                q.push(v);
                vec.push_back(v);
            }
        }
    }
    for (int x : vec) vis[x] = 0;
    return {far, dis[far]};
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        if (c[u] != c[v]) {
            H[u].push_back(v);
            H[v].push_back(u);
        }
    }
    int Ans = 1;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        vector<int> comp;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            comp.push_back(u);
            for (int v : H[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
        int s = comp[0];
        for (int x : comp) vis[x] = 0;
        int A = bfs(s).first, d = bfs(A).second;
        Ans = max(Ans, d + 1);
        for (int x : comp) vis[x] = 1;
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

11. 树上移动

题目大意

给定一棵树，每个点为黑色或白色。可以任选起点和终点，沿一条简单路径移动，要求路径上经过的黑色节点数不超过 kk，求最多能经过多少个节点。

解题思路

本题 n≤1000n\le1000，可以枚举起点。

树上两点之间路径唯一。从每个起点出发 DFS\text{DFS}，记录当前路径长度和黑点数量。

只要黑点数量不超过 kk，就更新答案。

复杂度：

O(n2)O(n^2)

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1010;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k, Ans;
int a[N];
vector<int> G[N];
void dfs(int u, int f, int dep, int cnt) {
    cnt += a[u];
    if (cnt > k) return;
    Ans = max(Ans, dep);
    for (int v : G[u]) {
        if (v == f) continue;
        dfs(v, u, dep + 1, cnt);
    }
}
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        dfs(i, 0, 1, 0);
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

12. 排队

题目大意

有 nn 位同学排成一行。给出 mm 对关系 (a,b)(a,b)，表示 aa 必须紧挨着排在 bb 的前面。求满足所有关系的排队方式数量，对 109+710^9+7 取模。

解题思路

关系 a→ba\to b 表示 aa 后面必须立刻接 bb。

因此每个点最多只能有一个后继，也最多只能有一个前驱，否则无解。

这些关系会形成若干条有向链。若出现有向环，也无解。

把每条链看成一个整体块，块内部顺序固定。若共有 cntcnt 个块，则答案为：

cnt!cnt!

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const LL mod = 1000000007;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int nxt[N], pre[N], vis[N];
set<pair<int, int> > S;
inline void solve() {
    cin >> n >> m;
    bool ok = true;
    int e = 0;
    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        if (S.count({a, b})) continue;
        S.insert({a, b});
        e++;
        if ((nxt[a] && nxt[a] != b) || (pre[b] && pre[b] != a)) ok = false;
        nxt[a] = b;
        pre[b] = a;
    }
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (x && !vis[x]) {
            vis[x] = i;
            x = nxt[x];
        }
        if (x && vis[x] == i) ok = false;
    }
    if (!ok) {
        printf("0\n");
        return;
    }
    int block = n - e;
    LL Ans = 1;
    for (int i = 1; i <= block; i++) Ans = Ans * i % mod;
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

13. 上学

题目大意

给定一张带权无向图，学校在节点 ss。多次询问某个同学家在节点 hih_i，求从 hih_i 到学校的最短时间。

解题思路

所有询问终点相同，都是学校 ss。

因此只需要从 ss 出发跑一次 Dijkstra\text{Dijkstra}，就能得到所有点到学校的最短路。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Edge {
    int to;
    LL w;
};
struct Node {
    int u;
    LL d;
    bool operator < (const Node &o) const {
        return d > o.d;
    }
};
int n, m, s, q;
vector<Edge> G[N];
LL dis[N];
inline void solve() {
    cin >> n >> m >> s >> q;
    for (int i = 1, u, v; i <= m; i++) {
        LL w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++) dis[i] = inf;
    priority_queue<Node> que;
    dis[s] = 0;
    que.push({s, 0});
    while (!que.empty()) {
        Node cur = que.top(); que.pop();
        int u = cur.u;
        if (cur.d != dis[u]) continue;
        for (auto e : G[u]) {
            int v = e.to;
            if (dis[v] > dis[u] + e.w) {
                dis[v] = dis[u] + e.w;
                que.push({v, dis[v]});
            }
        }
    }
    while (q--) {
        int h;
        cin >> h;
        printf("%lld\n", dis[h]);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

14. 割裂

题目大意

给定一棵树、若干好点对和一个坏点对。删除一个节点后，所有好点对仍需连通，而坏点对必须不连通。若删除点对端点，则视为不连通。求有多少个节点可以删除。

解题思路

一个节点能让坏点对断开，当且仅当它在坏点对路径上，包括两个端点。

同时，它不能在任何好点对路径上。

所以问题变成：

  1. 标记所有好点对路径上的节点；
  2. 统计坏点对路径上未被标记的节点数。

路径加标记使用树上差分。对好点对 (u,v)(u,v)：

$$tag_u++,\quad tag_v++,\quad tag_{lca}--,\quad tag_{fa(lca)}-- $$

最后自底向上求和，tag[x] > 0\text{tag[x] > 0} 表示节点 xx 在至少一条好路径上。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1000000 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a;
vector<int> G[N], ord;
int dep[N], fa[21][N];
int tag[N];
void bfs() {
    queue<int> q;
    q.push(1);
    dep[1] = 1;
    fa[0][1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ord.push_back(u);
        for (int v : G[u]) {
            if (v == fa[0][u]) continue;
            fa[0][v] = u;
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            fa[j][i] = fa[j - 1][fa[j - 1][i]];
        }
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int d = dep[x] - dep[y];
    for (int j = 20; j >= 0; j--) if ((d >> j) & 1) x = fa[j][x];
    if (x == y) return x;
    for (int j = 20; j >= 0; j--) {
        if (fa[j][x] != fa[j][y]) {
            x = fa[j][x];
            y = fa[j][y];
        }
    }
    return fa[0][x];
}
inline void solve() {
    cin >> n >> a;
    for (int i = 1, x, y; i < n; i++) {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs();
    for (int i = 1, u, v; i <= a; i++) {
        cin >> u >> v;
        int g = lca(u, v);
        tag[u]++; tag[v]++; tag[g]--;
        if (fa[0][g]) tag[fa[0][g]]--;
    }
    for (int i = (int)ord.size() - 1; i >= 0; i--) {
        int u = ord[i];
        if (fa[0][u]) tag[fa[0][u]] += tag[u];
    }
    int bu, bv; cin >> bu >> bv;
    int g = lca(bu, bv);
    int Ans = 0, x = bu;
    while (x != g) {
        if (tag[x] == 0) Ans++;
        x = fa[0][x];
    }
    if (tag[g] == 0) Ans++;
    x = bv;
    while (x != g) {
        if (tag[x] == 0) Ans++;
        x = fa[0][x];
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

15. 树上旅行

题目大意

给定一棵以 11 为根的有根树。每次旅行给出起点和若干移动操作：正数表示向父节点移动若干次，负数表示向编号最小的子节点移动若干次。求每次旅行终点。

解题思路

两种移动都是确定的：

  1. 向上：用倍增跳父亲；
  2. 向下：每个点的目标是编号最小的子节点，若没有子节点则停在原地，也可以倍增。

预处理：

up[j][u]up[j][u]

表示从 uu 向上走 2j2^j 步后的点。

dn[j][u]dn[j][u]

表示从 uu 沿最小子节点走 2j2^j 步后的点。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, q;
int up[20][N], dn[20][N];
int mnson[N];
int jump(int x, int k, int f[20][N]) {
    for (int j = 0; j < 20; j++) {
        if ((k >> j) & 1) x = f[j][x];
    }
    return x;
}
inline void solve() {
    cin >> n >> q;
    up[0][1] = 1;
    for (int i = 2, p; i <= n; i++) {
        cin >> p;
        up[0][i] = p;
        if (!mnson[p] || i < mnson[p]) mnson[p] = i;
    }
    for (int i = 1; i <= n; i++) {
        if (mnson[i]) dn[0][i] = mnson[i];
        else dn[0][i] = i;
    }
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++) {
            up[j][i] = up[j - 1][up[j - 1][i]];
            dn[j][i] = dn[j - 1][dn[j - 1][i]];
        }
    }
    while (q--) {
        int s, k;
        cin >> s >> k;
        int cur = s;
        for (int i = 1, x; i <= k; i++) {
            cin >> x;
            if (x > 0) cur = jump(cur, x, up);
            else cur = jump(cur, -x, dn);
        }
        printf("%d\n", cur);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

16. 遍历计数

题目大意

给定一棵树。任选 DFS\text{DFS} 起点，且每个节点遍历相邻节点的顺序任意，求可能产生多少种不同的 DFS\text{DFS} 遍历序，对 10910^9 取模。

解题思路

如果以 ss 为根进行 DFS\text{DFS}：

  • 根节点 ss 有 deg(s)deg(s) 个儿子，可以任意排列，贡献 deg(s)!deg(s)!；
  • 非根节点 uu 有 deg(u)−1deg(u)-1 个儿子，可以任意排列，贡献 (deg(u)−1)!(deg(u)-1)!。

所以以 ss 为起点的方案数为：

deg(s)!∏u≠s(deg(u)−1)!deg(s)!\prod_{u\ne s}(deg(u)-1)!

设：

base=∏u(deg(u)−1)!base=\prod_u (deg(u)-1)!

则起点 ss 的贡献为：

base×deg(s)base\times deg(s)

总答案为：

base×∑sdeg(s)=base×2(n−1)base\times \sum_s deg(s)=base\times 2(n-1)

特殊情况 n=1n=1，答案为 11。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL mod = 1000000000LL;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL fac[N], deg[N];
inline void solve() {
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        deg[u]++; deg[v]++;
    }
    if (n == 1) {
        printf("1\n");
        return;
    }
    LL Ans = 1;
    for (int i = 1; i <= n; i++) {
        Ans = Ans * fac[deg[i] - 1] % mod;
    }
    Ans = Ans * (2LL * (n - 1) % mod) % mod;
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

17. 最短距离

题目大意

构造一张 101810^{18} 个节点的完全图。两个节点编号互质时边权为 pp，不互质时边权为 qq。多次询问 a,ba,b 的最短距离。

解题思路

如果 a=ba=b，距离为 00。

若 gcd⁡(a,b)>1\gcd(a,b) > 1，直接走的代价为 qq。也可以通过节点 11 中转，两段互质边，代价为 2p2p。所以：

ans=min⁡(q,2p)ans=\min(q,2p)

若 gcd⁡(a,b)=1\gcd(a,b) = 1，直接代价为 pp。

如果 a,ba,b 都大于 11，可以选一个同时与 a,ba,b 不互质的中转点，例如取 aa 的某个质因子乘以 bb 的某个质因子，中转代价为 2q2q。

所以：

ans=min⁡(p,2q)ans=\min(p,2q)

但如果 a=1a=1 或 b=1b=1，节点 11 与所有其他节点都互质，无法用两条不互质边中转，答案就是 pp。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL p, q;
LL gcd(LL a, LL b) {return !b ? a : gcd(b, a % b);}
inline void solve() {
    cin >> n >> p >> q;
    while (n--) {
        LL a, b;
        cin >> a >> b;
        if (a == b) printf("0\n");
        else if (gcd(a, b) > 1) printf("%lld\n", min(q, 2 * p));
        else {
            if (a == 1 || b == 1) printf("%lld\n", p);
            else printf("%lld\n", min(p, 2 * q));
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

18. 最小生成树

题目大意

给定一张带权连通无向图。对于每条边，求删去这条边后图的最小生成树权值；若不存在最小生成树，输出 −1-1。

解题思路

先求原图的一棵 MST\text{MST}，权值为 sumsum。

  • 如果删的是非 MST\text{MST} 边，原 MST\text{MST} 仍然存在，答案就是 sumsum；
  • 如果删的是 MST\text{MST} 边，需要找一条非树边替代它。

对于每条非树边 (u,v,w)(u,v,w)，它可以替代 MST\text{MST} 上 uu 到 vv 路径中的任意一条边。

因此对 MST\text{MST} 做树链剖分，把非树边的权值 ww 对路径 u∼vu\sim v 做区间取最小更新。最后每条 MST\text{MST} 边查询自己的最小替代边即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Edge {
    int u, v, id;
    LL w;
};
int n, m;
vector<Edge> e;
vector<pair<int, int> > G[N];
int f[N], in[N];
LL mst;
int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
int fa[N], dep[N], siz[N], son[N], top[N], dfn[N], rev[N], tim;
int eid[N];
void dfs1(int u, int p) {
    fa[u] = p;
    dep[u] = dep[p] + 1;
    siz[u] = 1;
    for (auto x : G[u]) {
        int v = x.first;
        if (v == p) continue;
        eid[v] = x.second;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++tim;
    rev[tim] = u;
    if (son[u]) dfs2(son[u], tp);
    for (auto x : G[u]) {
        int v = x.first;
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
LL seg[N << 2];
void upd(int o, int l, int r, int ql, int qr, LL v) {
    if (ql <= l && r <= qr) {
        seg[o] = min(seg[o], v);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) upd(o << 1, l, mid, ql, qr, v);
    if (qr > mid) upd(o << 1 | 1, mid + 1, r, ql, qr, v);
}
LL ask(int o, int l, int r, int p) {
    if (l == r) return seg[o];
    int mid = (l + r) >> 1;
    LL res = seg[o];
    if (p <= mid) res = min(res, ask(o << 1, l, mid, p));
    else res = min(res, ask(o << 1 | 1, mid + 1, r, p));
    return res;
}
void path_update(int u, int v, LL w) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        upd(1, 1, n, dfn[top[u]], dfn[u], w);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    if (dfn[u] + 1 <= dfn[v]) {
        upd(1, 1, n, dfn[u] + 1, dfn[v], w);
    }
}
inline void solve() {
    cin >> n >> m;
    e.resize(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].id = i;
    }
    for (int i = 1; i <= n; i++) f[i] = i;
    vector<int> ord(m);
    for (int i = 0; i < m; i++) ord[i] = i + 1;
    sort(ord.begin(), ord.end(), [&](int x, int y) {
        return e[x].w < e[y].w;
    });
    for (int id : ord) {
        int u = e[id].u;
        int v = e[id].v;
        int fu = find(u);
        int fv = find(v);
        if (fu != fv) {
            f[fu] = fv;
            in[id] = 1;
            mst += e[id].w;
            G[u].push_back({v, id});
            G[v].push_back({u, id});
        }
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for (int i = 1; i < (N << 2); i++) seg[i] = inf;
    for (int i = 1; i <= m; i++) {
        if (!in[i]) {
            path_update(e[i].u, e[i].v, e[i].w);
        }
    }
    vector<LL> Ans(m + 1, mst);
    for (int u = 2; u <= n; u++) {
        int id = eid[u];
        LL rep = ask(1, 1, n, dfn[u]);
        if (rep == inf) Ans[id] = -1;
        else Ans[id] = mst - e[id].w + rep;
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", Ans[i]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

19. 猫和老鼠

题目大意

给定一张带权无向连通图。猫从猫窝 aa 出发，老鼠从某个节点出发要逃到洞 bb。若存在一条到 bb 的路径，使路径上每个点猫到达的最短时间都严格大于老鼠沿该路径到达该点的时间，则该节点安全。求所有安全节点奶酪价值之和。

解题思路

先从猫窝 aa 跑 Dijkstra\text{Dijkstra}，得到猫到每个点的最短时间 cat[x]cat[x]。

定义 lim[u]lim[u] 表示老鼠到达 uu 的最晚时间，若在这个时间之前到达 uu，仍然可以安全逃到洞。

对于洞 bb：

lim[b]=cat[b]lim[b]=cat[b]

若从 uu 走到 vv，边权为 ww，并且到达 vv 的时间要小于 lim[v]lim[v]，则在 uu 的最晚时间为：

lim[v]−wlim[v]-w

同时在 uu 自己也要早于猫到达：

lim[u]≤cat[u]lim[u]\le cat[u]

所以转移为：

lim[u]=max⁡min⁡(cat[u],lim[v]−w)lim[u]=\max \min(cat[u],lim[v]-w)

用优先队列做最大值传播即可。最后 lim[u]>0lim[u] > 0 的点安全。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Edge {
    int to;
    LL w;
};
struct Node {
    int u;
    LL d;
    bool operator < (const Node &o) const {
        return d > o.d;
    }
};
struct MaxNode {
    int u;
    LL d;
    bool operator < (const MaxNode &o) const {
        return d < o.d;
    }
};
int n, m, A, B;
LL c[N], cat[N], lim[N];
vector<Edge> G[N];
void dij(int s) {
    for (int i = 1; i <= n; i++) cat[i] = inf;
    priority_queue<Node> q;
    cat[s] = 0;
    q.push({s, 0});
    while (!q.empty()) {
        Node cur = q.top(); q.pop();
        int u = cur.u;
        if (cur.d != cat[u]) continue;
        for (auto e : G[u]) {
            int v = e.to;
            if (cat[v] > cat[u] + e.w) {
                cat[v] = cat[u] + e.w;
                q.push({v, cat[v]});
            }
        }
    }
}
inline void solve() {
    cin >> n >> m >> A >> B;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1, u, v; i <= m; i++) {
        LL w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dij(A);
    for (int i = 1; i <= n; i++) lim[i] = -inf;
    priority_queue<MaxNode> q;
    lim[B] = cat[B];
    q.push({B, lim[B]});
    while (!q.empty()) {
        MaxNode cur = q.top(); q.pop();
        int u = cur.u;
        if (cur.d != lim[u]) continue;
        for (auto e : G[u]) {
            int v = e.to;
            LL val = min(cat[v], lim[u] - e.w);
            if (val > lim[v]) {
                lim[v] = val;
                q.push({v, val});
            }
        }
    }
    LL Ans = 0;
    for (int i = 1; i <= n; i++) if (lim[i] > 0) Ans += c[i];
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

20. 宝石项链

题目大意

一条环形宝石项链有 nn 枚宝石，共 mm 种类型。要把项链划分成若干连续段，并且每段都包含全部 mm 种宝石。求最多能划分多少段。

解题思路

把环展开成长度 2n2n 的序列。

对于每个起点 ii，用双指针求出最短的右端点 nxt[i]\text{nxt[i]}，使得区间 [i,nxt[i]][i,nxt[i]] 包含所有 mm 种宝石。

若从 ii 开始切一段，那么下一段起点为：

nxt[i]+1nxt[i]+1

这是一个倍增跳转问题。

对于每个环上的起点 ii，统计在不超过 i+n−1i+n-1 的范围内最多能跳多少段，取最大值。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int a[N], cnt[N], nxt[20][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    int r = 0, kind = 0;
    for (int l = 1; l <= 2 * n; l++) {
        while (r < 2 * n && kind < m) {
            r++;
            if (++cnt[a[r]] == 1) kind++;
        }
        if (kind == m) nxt[0][l] = r + 1;
        else nxt[0][l] = 2 * n + 1;
        if (--cnt[a[l]] == 0) kind--;
    }
    nxt[0][2 * n + 1] = 2 * n + 1;
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= 2 * n + 1; i++) {
            nxt[j][i] = nxt[j - 1][nxt[j - 1][i]];
        }
    }
    int Ans = 0;
    for (int s = 1; s <= n; s++) {
        int cur = s, end = s + n - 1, res = 0;
        for (int j = 19; j >= 0; j--) {
            if (nxt[j][cur] <= end + 1) {
                res += 1 << j;
                cur = nxt[j][cur];
            }
        }
        Ans = max(Ans, res);
    }
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

21. 消息查找

题目大意

消息编号从 11 到 nn，每条消息可以引用一条编号更小的消息，也可以不引用。

当前位于消息 ii 时，可以执行以下操作：

  1. 移动到消息 i−1i-1；
  2. 如果消息 ii 引用了消息 rir_i，也可以直接移动到消息 rir_i。

多次询问从消息 xx 移动到消息 yy 的最少操作次数。

题目保证：

1≤y<x≤n1 \le y < x \le n

并且有引用的消息不超过 10001000 条。

解题思路

如果完全不用引用边，那么从 xx 走到 yy 的代价就是：

x−yx-y

设一条引用边为：

s→rs \to r

表示从消息 ss 可以一步跳到消息 rr，其中：

r<sr < s

对于一次询问 (x,y)(x,y)，只有满足下面条件的引用边才可能有用：

y≤r<s≤xy \le r < s \le x

如果 r<yr < y，跳过去之后就已经越过目标消息 yy，由于只能向编号更小的方向移动，就不可能再回到 yy，因此这种引用边不能使用。

状态转化

定义：

F(pos)F(pos)

表示从消息 pospos 移动到消息 yy 的最少操作次数。

不用引用边时：

F(pos)=pos−yF(pos)=pos-y

如果使用某条引用边：

s→rs\to r

那么从 pospos 走到 ss 需要：

pos−spos-s

步，再从 ss 跳到 rr 需要 11 步，之后还需要：

F(r)F(r)

步。

所以：

F(pos)=min⁡(pos−y, pos−s+1+F(r))F(pos)=\min(pos-y,\ pos-s+1+F(r))

整理成：

F(pos)=pos+min⁡(−y, F(r)−s+1)F(pos)=pos+\min(-y,\ F(r)-s+1)

关键细节

处理引用边时，按照源点 ss 从小到大排序。

对于当前引用边：

s→rs\to r

要计算 F(r)F(r)，只能使用那些源点不超过 rr 的引用边。

原因是从 rr 出发后，只能继续往更小编号移动，不可能回到源点大于 rr 的引用消息。

所以不能简单维护一个全局最优 best\text{best}，而要维护：

pre[i]pre[i]

表示源点编号不超过第 ii 条引用边源点时，当前询问下的最优值。

由于引用边数量最多只有 10001000 条，每个询问枚举所有引用边即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Edge {
    int s, r;
};
int n, q;
vector<Edge> e;
vector<int> src;
int id[1010];
LL pre[1010];
inline void solve() {
    cin >> n >> q;
    for (int i = 1, r; i <= n; i++) {
        cin >> r;
        if (r) {
            e.push_back({i, r});
        }
    }
    sort(e.begin(), e.end(), [](Edge A, Edge B) {
        return A.s < B.s;
    });
    int k = e.size();
    for (int i = 0; i < k; i++) {
        src.push_back(e[i].s);
    }
    for (int i = 0; i < k; i++) {
        id[i] = upper_bound(src.begin(), src.end(), e[i].r) - src.begin() - 1;
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        LL cur = -y;
        for (int i = 0; i < k; i++) {
            if (e[i].s > x) break;
            if (e[i].r >= y) {
                LL best = -y;
                if (id[i] >= 0) {
                    best = pre[id[i]];
                }
                LL fr = e[i].r + best;
                LL val = fr - e[i].s + 1;
                cur = min(cur, val);
            }
            pre[i] = cur;
        }
        LL Ans = x + cur;
        printf("%lld\n", Ans);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

22. 子图最短路

题目大意

给定一张带权无向图。对于每个区间 [ℓ,r][\ell,r]，只保留编号在该区间内的点，形成诱导子图。对该子图中所有点对 (u,v)(u,v) 求最短路并累加，若不连通则距离为 00。求所有区间、所有点对的距离总和，对 10910^9 取模。

解题思路

n≤100n\le100，可以枚举区间。

固定左端点 ℓ\ell，逐渐增加右端点 rr。

每次加入新点 rr 后，在当前诱导子图中从 rr 跑一次 Dijkstra\text{Dijkstra}，得到 rr 到所有旧点的最短距离。

任何新产生的最短路都可能经过新点 rr，于是更新：

dist[i][j]=min⁡(dist[i][j],d[i]+d[j])dist[i][j]=\min(dist[i][j],d[i]+d[j])

然后把当前区间内所有点对的距离加入答案。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 110;
const LL inf = 4e18;
const LL mod = 1000000000LL;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL w[N][N], dis[N][N], d[N];
int vis[N];
void dij(int l, int r) {
    for (int i = l; i <= r; i++) {
        d[i] = inf;
        vis[i] = 0;
    }
    d[r] = 0;
    for (int t = l; t <= r; t++) {
        int u = 0;
        for (int i = l; i <= r; i++) {
            if (!vis[i] && (u == 0 || d[i] < d[u])) {
                u = i;
            }
        }
        if (u == 0 || d[u] == inf) break;
        vis[u] = 1;
        for (int v = l; v <= r; v++) {
            if (w[u][v] < inf && d[v] > d[u] + w[u][v]) {
                d[v] = d[u] + w[u][v];
            }
        }
    }
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            w[i][j] = inf;
        }
        w[i][i] = 0;
    }
    for (int i = 1, u, v; i <= m; i++) {
        LL c;
        cin >> u >> v >> c;
        w[u][v] = min(w[u][v], c);
        w[v][u] = min(w[v][u], c);
    }
    LL Ans = 0;
    for (int l = 1; l <= n; l++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = inf;
            }
        }
        for (int r = l; r <= n; r++) {
            dij(l, r);
            for (int i = l; i <= r; i++) {
                dis[i][r] = dis[r][i] = min(dis[i][r], d[i]);
            }
            for (int i = l; i <= r; i++) {
                for (int j = l; j <= r; j++) {
                    if (d[i] < inf && d[j] < inf) {
                        dis[i][j] = min(dis[i][j], d[i] + d[j]);
                    }
                }
            }
            for (int i = l; i <= r; i++) {
                for (int j = i; j <= r; j++) {
                    if (dis[i][j] < inf) {
                        Ans = (Ans + dis[i][j]) % mod;
                    }
                }
            }
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

评论

0 条
还没有评论。
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  5. 京ICP备2024092232号-2
  6. 京公网安备图标 京公网安备11010802045784号
  7. DAMON THRONE