CSP-S 2022 题解
前言
由于打的肽粉了，NOIP 考前补了一下题。
T1：假期计划
题目链接：luogu P8817
题目大意
给你一个无向图，然后要你规划出一条路径，其中起点和终点都是 1 号点，然后你从中选四个不同的特殊点，形成五段路，保证每段的边数不超过 k 的情况下，四个特殊点的点权和最大。
思路
首先看到 \(n\) 是 \(2000\)，而且边权相同，那我们完全可以用 \(O(n^2)\) dfs 搜出如果这个点是特殊点，下一个可以是那些。
那把这些建图，就变成你要找一个其中一个点固定的五元环。
考虑怎么找，直接找肯定超时，考虑一个类似折中的感觉，你先找两条路径，然后看看能否拼起来。
那这样还是太多了，考虑走两步走到的位置，那对于每个位置有 \(n\) 种，我们选出最优的（反正后面连着的时候也不管它）
但是这样自然有问题，就是你要五元环中每个点都不用。
那我们考虑保留前几大的，然后这些之间比一下把能用的跟最优答案比。
思考一下不难发现只要取前三大即可。
代码
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
const int N = 2505;
int n, m, k, dis[N][N], maxn[N], maxx[N], maxp[N];
vector <int> G[N], G1[N];
queue <int> q;
bool in[N];
ll a[N], ans;
void dfs(int now, int num, ll an) {
if (num == 4) {
if (dis[now][1] <= k) ans = max(ans, an);
return ;
}
for (int i = 0; i < G1[now].size(); i++) {
int x = G1[now][i];
if (x > 1 && !in[x]) {
in[x] = 1;
dfs(x, num + 1, an + a[x]);
in[x] = 0;
}
}
}
void check(int A, int b, int c, int d) {
if (A == b || A == c || A == d) return ;
if (b == c || b == d) return ;
if (c == d) return ;
if (!A || !b || !c || !d) return ;
ans = max(ans, a[A] + a[b] + a[c] + a[d]);
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i = 2; i <= n; i++) scanf("%lld", &a[i]);
memset(dis, 0x7f, sizeof(dis));
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d %d", &x, &y);
G[x].push_back(y); G[y].push_back(x);
}
for (int S = 1; S <= n; S++) {
for (int i = 0; i < G[S].size(); i++) {
int x = G[S][i]; dis[S][x] = 0; q.push(x);
}
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = 0; i < G[now].size(); i++) {
int x = G[now][i];
if (dis[S][x] > dis[S][now] + 1) {
dis[S][x] = dis[S][now] + 1; q.push(x);
}
}
}
}
if (n <= 20 || (n <= 200 && k == 0)) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && dis[i][j] <= k) {
G1[i].push_back(j);
}
for (int i = 0; i < G1[1].size(); i++) {
int x = G1[1][i];
in[x] = 1; dfs(x, 1, a[x]); in[x] = 0;
}
}
else {
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= n; j++)
if (i != j && dis[1][j] <= k && dis[j][i] <= k) {
if (a[j] > a[maxn[i]]) maxp[i] = maxx[i], maxx[i] = maxn[i], maxn[i] = j;
else if (a[j] > a[maxx[i]]) maxp[i] = maxx[i], maxx[i] = j;
else if (a[j] > a[maxp[i]]) maxp[i] = j;
}
}
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++)
if (i != j && dis[i][j] <= k) {
check(maxn[i], i, j, maxn[j]);
check(maxx[i], i, j, maxn[j]);
check(maxp[i], i, j, maxn[j]);
check(maxn[i], i, j, maxx[j]);
check(maxx[i], i, j, maxx[j]);
check(maxp[i], i, j, maxx[j]);
check(maxn[i], i, j, maxp[j]);
check(maxx[i], i, j, maxp[j]);
check(maxp[i], i, j, maxp[j]);
}
}
printf("%lld", ans);
return 0;
}
T2：策略游戏
题目链接：luogu P8818
题目大意
给你一个数组 A 和一个数组 B，每次游戏给你 A 的区间和 B 的区间。
然后先手选 A 区间里的一个数，后手再选 B 区间里的一个数，两个数相乘构成分数。
先手要最大化分数，后手要最小化分数，问你每次游戏的分数。
思路
直接思考每个人的过程，分类讨论即可。主要的讨论方式就是针对 \(0\)，正负数展开。
可以假设先手放的数，放的 \(0\) 就不管了，如果放的是正数，后手如果有负数就会放最小的负数，否则有 \(0\) 放 \(0\)，没有就放最小的正数。
那放的负数也是相同的道理。
那对于先手而言，他如果无论放正数负数都会变成负数，那就有 \(0\) 放 \(0\)。
否则模拟一下放最小正数和最大负数，选贡献大的。
如果有一种情况能避免的话，那就正数选最大，负数选最小（如果两种都可以就都试一下选最大）。
大概就是这样的分类讨论。
代码
#include<cstdio>
#include<iostream>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 1e5 + 100;
int n, m, q, log2_[N], tmpa[3], tmpb[3];
int a[N], b[N], anum[3][N], bnum[3][N];
int l1, r1, l2, r2;
//0:0 1:1 2:-1
struct ST_max {
int f[21][N];
void Init(int n) {
for (int i = 1; i <= 20; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
int k = log2_[r - l + 1];
return max(f[k][l], f[k][r - (1 << k) + 1]);
}
}Amax_z, Amax_f, Bmax_z, Bmax_f;
struct ST_min {
int f[21][N];
void Init(int n) {
for (int i = 1; i <= 20; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
}
int query(int l, int r) {
int k = log2_[r - l + 1];
return min(f[k][l], f[k][r - (1 << k) + 1]);
}
}Amin_z, Amin_f, Bmin_z, Bmin_f;
ll slove() {
if (tmpb[1] && tmpb[2]) {
if (tmpa[0]) return 0;
ll ans = -1e18;
if (tmpa[1]) ans = max(ans, 1ll * Amin_z.query(l1, r1) * Bmin_f.query(l2, r2));
if (tmpa[2]) ans = max(ans, 1ll * Amax_f.query(l1, r1) * Bmax_z.query(l2, r2));
return ans;
}
if (tmpb[1] && !tmpa[1]) {
if (tmpa[0]) return 0;
return 1ll * Amax_f.query(l1, r1) * Bmax_z.query(l2, r2);
}
if (tmpb[2] && !tmpa[2]) {
if (tmpa[0]) return 0;
return 1ll * Amin_z.query(l1, r1) * Bmin_f.query(l2, r2);
}
if (tmpb[0]) return 0;
ll ans = -1e18;
if (tmpb[1]) {
ans = max(ans, 1ll * Amax_z.query(l1, r1) * Bmin_z.query(l2, r2));
}
if (tmpb[2]) {
ans = max(ans, 1ll * Amin_f.query(l1, r1) * Bmax_f.query(l2, r2));
}
return ans;
}
int main() {
log2_[0] = -1; for (int i = 1; i < N; i++) log2_[i] = log2_[i >> 1] + 1;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] > 0) {
Amax_z.f[0][i] = Amin_z.f[0][i] = a[i];
Amax_f.f[0][i] = -INF; Amin_f.f[0][i] = INF;
}
if (a[i] < 0) {
Amax_f.f[0][i] = Amin_f.f[0][i] = a[i];
Amax_z.f[0][i] = -INF; Amin_z.f[0][i] = INF;
}
if (!a[i]) anum[0][i]++;
if (a[i] > 0) anum[1][i]++;
if (a[i] < 0) anum[2][i]++;
}
for (int i = 1; i <= m; i++) {
scanf("%d", &b[i]);
if (b[i] > 0) {
Bmax_z.f[0][i] = Bmin_z.f[0][i] = b[i];
Bmax_f.f[0][i] = -INF; Bmin_f.f[0][i] = INF;
}
if (b[i] < 0) {
Bmax_f.f[0][i] = Bmin_f.f[0][i] = b[i];
Bmax_z.f[0][i] = -INF; Bmin_z.f[0][i] = INF;
}
if (!b[i]) bnum[0][i]++;
if (b[i] > 0) bnum[1][i]++;
if (b[i] < 0) bnum[2][i]++;
}
Amax_z.Init(n); Amin_z.Init(n); Bmax_z.Init(m); Bmin_z.Init(m);
Amax_f.Init(n); Amin_f.Init(n); Bmax_f.Init(m); Bmin_f.Init(m);
for (int op = 0; op < 3; op++) {
for (int i = 1; i <= n; i++) anum[op][i] += anum[op][i - 1];
for (int i = 1; i <= m; i++) bnum[op][i] += bnum[op][i - 1];
}
for (int i = 1; i <= q; i++) {
scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
for (int op = 0; op < 3; op++) {
tmpa[op] = anum[op][r1] - anum[op][l1 - 1];
tmpb[op] = bnum[op][r2] - bnum[op][l2 - 1];
}
printf("%lld\n", slove());
}
return 0;
}
T3：星战
题目链接：luogu P8819
题目大意
给你一个有向图，每次操作有删除一条边，恢复某条已经删了的边，删除所有还在的连着某个点的边，恢复所有连着这个点的被删掉的边。
每次操作之后，问你是否每个点都有恰好一个出边，而且都能走到一个环里。
思路
考虑先转化题意。
发现只要每个点都满足初度恰好为 \(1\)，另一个能走到环的条件也能满足。
那你有出边嘛，那就能一直走下去，自然就是环了。
那如果只有 \(1,3\) 操作，那就很容易维护，问题是 \(2,4\) 操作，它的是入边。
所以你入度是方便维护的，但是出度就不太行。
那你考虑入度初度之间的关系，那就是入度和跟出度和一样。
而且在这个限制条件下都是 \(n\)。
那如果满足的这个条件，也不一定行。
那要如何判断是每个点都贡献了一次，而不是一个点贡献了多次呢？
可以用哈希，每个点随机一个点权，每条边以它做入边的点做贡献。
那合法的情况就是当前所有存在的边的权和是所有点的权和。
那你每个点记录着入边的边权和就行。
代码
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
const int N = 5e5 + 100;
int n, m, ru[N], chu[N];
ll a[N], sum, g[N], now[N], nows;
int main() {
srand(19491001);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) a[i] = 1ll * rand() * rand(), sum += a[i];
for (int i = 1; i <= m; i++) {
int x, y; scanf("%d %d", &x, &y);
chu[x]++; ru[y]++; g[y] += a[x];
}
for (int i = 1; i <= n; i++) now[i] = g[i], nows += g[i];
int q; scanf("%d", &q);
while (q--) {
int op; scanf("%d", &op);
if (op == 1) {
int x, y; scanf("%d %d", &x, &y);
now[y] -= a[x]; nows -= a[x];
}
if (op == 2) {
int x; scanf("%d", &x);
nows -= now[x]; now[x] = 0;
}
if (op == 3) {
int x, y; scanf("%d %d", &x, &y);
now[y] += a[x]; nows += a[x];
}
if (op == 4) {
int x; scanf("%d", &x);
nows += g[x] - now[x]; now[x] = g[x];
}
if (nows == sum) printf("YES\n");
else printf("NO\n");
}
return 0;
}
T4：数据传输
题目大意
给你一棵树，多次询问每次你要从树上的一个点走到另一个点。
每次走你可以走到距离你当前点边数不超过 k 条边的点，并加上你走到的点的点权（起点和终点也要加），问你需要的最小点权。
思路
一个直观的想法是在树上按着 DP，甚至只需要在路径上的点里面看。
但这样在 \(k=1,2\) 没问题，但是在 \(k=3\) 的时候会有一个特别的情况：
就是走两步往外选一个点停下算贡献，再走回来然后走两步。
不过也不会有问题，你用一个 \(w_i\) 记录它以及它一步能走到的边权最小的点权，就也可以弄。
那至于在树上，你就拆成 LCA 的两段。
那你可以用树链剖分或者倍增，这里用的是倍增，来造每一段的转移。
那思考怎么转移，那你不难想象到是从 \((x,a)\rightarrow (y,b)\)，即从 \(x\) 点，现在上一个到的点距离 \(a\) 条边，走到 \(y\) 点，上一个到的点的距离 \(b\) 条边需要的最小费用。
然后你可以根据这个 \(a,b\) 建立转移矩阵，那就是 \(f_{a,b}\) 的位置的值。
然后转移就是不放点，这个位置放点，在这个位置走出去放点。
然后考虑两段的矩阵如何算答案。
考虑枚举两边的 \((0,a),(0,b)\)。
那正常了来说是两点的费用加起来，不过有两个特别的：
\(a=b=0\)，那 lca 这个位置被统计了两次，要减一次。
\(a=b=2\)，那 lca 这个位置就需要往别处走存一下，所以要加上 \(w_{lca}\)。
然后就可以了。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 2e5 + 100;
struct node {
int to, nxt;
}e[N << 1];
int n, Q, K, le[N], KK, fa[N][21], deg[N];
ll v[N], w[N];
struct matrix {
int n, m;
ll a[3][3];
}f[N][21];
matrix operator *(matrix x, matrix y) {
matrix z; z.n = x.n; z.m = y.m;
for (int i = 0; i < z.n; i++)
for (int j = 0; j < z.m; j++)
z.a[i][j] = 1e18;
for (int k = 0; k < x.m; k++)
for (int i = 0; i < z.n; i++)
for (int j = 0; j < z.m; j++)
z.a[i][j] = min(z.a[i][j], x.a[i][k] + y.a[k][j]);
return z;
}
void add(int x, int y) {
e[++KK] = (node){y, le[x]}; le[x] = KK;
}
void dfs(int now, int father) {
deg[now] = deg[father] + 1;
fa[now][0] = father; for (int i = 1; i <= 20; i++) fa[now][i] = fa[fa[now][i - 1]][i - 1];
if (K == 1) {
f[now][0].n = f[now][0].m = 1;
f[now][0].a[0][0] = v[father];
}
if (K == 2) {
f[now][0].n = f[now][0].m = 2;
f[now][0].a[0][0] = v[father]; f[now][0].a[0][1] = 0;
f[now][0].a[1][0] = v[father]; f[now][0].a[1][1] = 1e18;
}
if (K == 3) {
f[now][0].n = f[now][0].m = 3;
f[now][0].a[0][0] = v[father]; f[now][0].a[0][1] = 0; f[now][0].a[0][2] = 1e18;
f[now][0].a[1][0] = v[father]; f[now][0].a[1][1] = 1e18; f[now][0].a[1][2] = 0;
f[now][0].a[2][0] = v[father]; f[now][0].a[2][1] = 1e18; f[now][0].a[2][2] = w[now];
}
for (int i = 1; i <= 20; i++) f[now][i] = f[now][i - 1] * f[fa[now][i - 1]][i - 1];
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != father) dfs(e[i].to, now);
}
int LCA(int x, int y) {
if (deg[x] < deg[y]) swap(x, y);
for (int i = 20; i >= 0; i--)
if (deg[fa[x][i]] >= deg[y]) x = fa[x][i];
if (x == y) return x;
for (int i = 20; i >= 0; i--)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
matrix work(int x, int y) {
matrix re; re.n = re.m = K;
for (int i = 0; i < re.n; i++) for (int j = 0; j < re.m; j++) re.a[i][j] = (i == j) ? v[x] : 1e18;
for (int i = 20; i >= 0; i--)
if (deg[fa[x][i]] >= deg[y]) re = re * f[x][i], x = fa[x][i];
return re;
}
int main() {
scanf("%d %d %d", &n, &Q, &K);
for (int i = 1; i <= n; i++) scanf("%lld", &v[i]), w[i] = v[i];
for (int i = 1; i < n; i++) {
int x, y; scanf("%d %d", &x, &y);
add(x, y); add(y, x);
w[x] = min(w[x], v[y]); w[y] = min(w[y], v[x]);
}
for (int i = 0; i <= 20; i++) {
f[0][i].n = f[0][i].m = K;
for (int j = 0; j < K; j++)
for (int k = 0; k < K; k++)
f[0][i].a[j][k] = 1e18;
}
dfs(1, 0);
while (Q--) {
int x, y; scanf("%d %d", &x, &y); int lca = LCA(x, y);
matrix lx = work(x, lca), ry = work(y, lca);
ll ans = 1e18;
for (int i = 0; i < K; i++)
for (int j = 0; j < K; j++) {
ll now = lx.a[0][i] + ry.a[0][j];
if (!i && !j) now -= v[lca];
if (i == 2 && j == 2) now += w[lca];
ans = min(ans, now);
}
printf("%lld\n", ans);
}
return 0;
}