A. 假期计划(holiday)
首先我们可以跑 \(n\) 次 bfs，预处理出哪些景点之间可以转 \(k\) 次车到达。
然后我们设路径是 \(\text{Home} \to A \to B \to C \to D \to \text{Home}\)。我们对于每个点 \(X\)，预处理 \(\text{Home} \to Y \to X\) 路径中 \(a_X + a_Y\) 前三大的值，以及此时对应的 \(Y\)。然后我们枚举 \(A, B\)，然后暴力 \(3 \times 3\) 枚举 \(A\) 和 \(B\) 的前三大。可以证明答案一定在前三大内。
考场代码
#include <bits/stdc++.h>
typedef long long LL;
typedef __int128_t Lint;
const int N = 2500 + 5;
const int M = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int n, m, K;
LL a[N];
struct Edge { int to, nxt; } edge[M << 1];
int head[N];
void add_edge(int u, int v) { static int k = 1; edge[k] = (Edge){v, head[u]}, head[u] = k++; }
int dis[N][N];
bool vis[N];
std::queue<int> q;
void bfs(int st) {
while(!q.empty()) q.pop();
for(int i = 1; i <= n; i++) vis[i] = false, dis[st][i] = INF;
dis[st][st] = 0, vis[st] = true, q.push(st);
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if(vis[v]) continue;
dis[st][v] = dis[st][u] + 1, vis[v] = true, q.push(v);
}
}
}
bool e[N][N];
int r[N][3];
void print(Lint x) {
char stk[200]; int top = 0;
if(x == 0) stk[top++] = '0';
while(x) stk[top++] = x % 10 + '0', x /= 10;
for(top--; top >= 0; top--) putchar(stk[top]);
}
int main() {
freopen("holiday.in", "r", stdin);
freopen("holiday.out", "w", stdout);
scanf("%d%d%d", &n, &m, &K);
for(int i = 2; i <= n; i++) scanf("%lld", &a[i]);
for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v), add_edge(v, u); }
for(int i = 1; i <= n; i++) bfs(i);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) e[i][j] = (i == j ? false : dis[i][j] <= K + 1);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) if(e[1][j] && e[j][i] && (r[i][0] == 0 || a[r[i][0]] < a[j])) r[i][0] = j;
for(int j = 1; j <= n; j++) if(e[1][j] && e[j][i] && j != r[i][0] && (r[i][1] == 0 || a[r[i][1]] < a[j])) r[i][1] = j;
for(int j = 1; j <= n; j++) if(e[1][j] && e[j][i] && j != r[i][0] && j != r[i][1] && (r[i][2] == 0 || a[r[i][2]] < a[j])) r[i][2] = j;
}
Lint ans = 0;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(e[i][j]) {
int x1 = r[i][0], x2 = r[i][1], y1 = r[j][0], y2 = r[j][1];
if(x1 == j) x1 = r[i][1], x2 = r[i][2];
else if(x2 == j) x2 = r[i][2];
if(y1 == i) y1 = r[j][1], y2 = r[j][2];
else if(y2 == i) y2 = r[j][2];
if(x1 != y1) {
if(x1 && y1) ans = std::max(ans, (Lint)a[i] + a[j] + a[x1] + a[y1]);
} else {
if(x1 && y2) ans = std::max(ans, (Lint)a[i] + a[j] + a[x1] + a[y2]);
if(x2 && y1) ans = std::max(ans, (Lint)a[i] + a[j] + a[x2] + a[y1]);
}
print(ans), printf("\n");
return 0;
}
B. 策略游戏(game)
考虑如果小 L 已经选了一个正数，那么小 Q 一定会选一个最小值；反之则小 Q 一定会选一个最大值。
所以如果小 L 已经决定要选一个正数，那么他相当于已经知道小 Q 会选哪个数了。如果小 Q 将要选的是一个正数，那么小 L 一定会选择最大的正数，否则他会选最小的正数。反过来，如果小 L 已经决定要选一个负数，也是一样的道理。由于最开始的选择权在小 L，所以他一定是在正数和负数的解中取最大的一个。
至于 \(0\)，我们现在一直都没考虑过它，但其实我们可以随便将他归到正数或者负数。
然后就做完了，好水的 T2 啊。
考场代码
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 5;
const LL LLINF = 0x3f3f3f3f3f3f3f3fLL;
const int NONE = 1e9 + 1;
int n, m, Q;
int a[N], b[N];
struct ST {
int lg[N], mn[N][21], mx[N][21];
int calcmin(int x, int y) { return x == NONE || y == NONE ? (x == NONE ? y : x) : std::min(x, y); }
int calcmax(int x, int y) { return x == NONE || y == NONE ? (x == NONE ? y : x) : std::max(x, y); }
void preprocess(int *arr, int bd, int type) {
lg[0] = -1;
for(int i = 1; i <= bd; i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= bd; i++) mn[i][0] = mx[i][0] = (type == 2 ? arr[i] : (type == 1 ? (arr[i] >= 0 ? arr[i] : NONE) : (arr[i] <= 0 ? arr[i] : NONE)));
for(int j = 1; j <= 20; j++)
for(int i = 1; i + (1 << j) - 1 <= bd; i++) {
mn[i][j] = calcmin(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
mx[i][j] = calcmax(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
}
int getmin(int l, int r) {
int k = lg[r - l + 1];
return calcmin(mn[l][k], mn[r - (1 << k) + 1][k]);
}
int getmax(int l, int r) {
int k = lg[r - l + 1];
return calcmax(mx[l][k], mx[r - (1 << k) + 1][k]);
}
} sta[2], stb;
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d%d%d", &n, &m, &Q);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
sta[0].preprocess(a, n, 0), sta[1].preprocess(a, n, 1), stb.preprocess(b, m, 2);
while(Q--) {
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
int mn2 = stb.getmin(l2, r2), mx2 = stb.getmax(l2, r2);
LL ans = -LLINF;
if(mn2 >= 0 && sta[1].getmax(l1, r1) != NONE) ans = std::max(ans, (LL)sta[1].getmax(l1, r1) * mn2);
if(mn2 <= 0 && sta[1].getmin(l1, r1) != NONE) ans = std::max(ans, (LL)sta[1].getmin(l1, r1) * mn2);
if(mx2 >= 0 && sta[0].getmax(l1, r1) != NONE) ans = std::max(ans, (LL)sta[0].getmax(l1, r1) * mx2);
if(mx2 <= 0 && sta[0].getmin(l1, r1) != NONE) ans = std::max(ans, (LL)sta[0].getmin(l1, r1) * mx2);
printf("%lld\n", ans);
}
return 0;
}
C. 星战(galaxy)
首先发现一个结论：输出 YES 当且仅当每个点都有恰好一条出边。
证明也很显然。充分性：对于每个点，我们考虑一直沿着唯一的出边走，那么最坏情况下走 \(n – 1\) 条边就能走完 \(n\) 个点（否则一定有重复的点），所以走 \(n\) 条边一定能走完所有点，并且会有重复，即出现了环。必要性：根据条件，边数等于 \(n\)，如果有点有多条出边，那么一定会出现有的点没有出边，不符合题意。
然后我们显然可以维护边数，但是怎么维护每个点只有一条出边这个信息呢？根号算法应该是过不了的，难道要用一些 nb 的数据结构？其实不用，我们考虑直接哈希。显然我们只需要有每 \(n\) 条边，而且每个点各一条出边，至于是哪 \(n\) 条，我们不关心。所以哈希应该和边无关，我们可以考虑只哈希每条边的起点。然后，这 \(n\) 个点的顺序其实也是无关紧要的。这就让我们想到了 XOR Hashing 或者 Sum Hashing。考虑对于每次操作维护边的起点的 XOR/SUM，但是这样很容易哈希冲突。所以我们给每个点随机赋一个很大的权值，就可以有效避免哈希冲突。这个很好维护。
挺巧妙的一道题。
赛后代码
#include <bits/stdc++.h>
typedef long long LL;
const int N = 5e5 + 5;
int n, m, Q;
int ind[N], d[N];
int cnt = 0;
LL bigrand() { return (LL)rand() << 31 | rand(); } // linux 下 rand() 的范围是 0~2^31-1
LL a[N], b[N], c[N];
int main() {
freopen("galaxy.in", "r", stdin);
freopen("galaxy.out", "w", stdout);
scanf("%d%d", &n, &m);
cnt = m;
LL val = 0, xor_all = 0;
for(int i = 1; i <= n; i++) a[i] = bigrand(), xor_all ^= a[i];
for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); ind[v]++, b[v] ^= a[u], val ^= a[u]; }
for(int i = 1; i <= n; i++) d[i] = ind[i], c[i] = b[i];
scanf("%d", &Q);
while(Q--) {
int t, x, y;
scanf("%d", &t);
if(t == 1) scanf("%d%d", &x, &y), cnt--, d[y]--, val ^= a[x], c[y] ^= a[x];
else if(t == 2) scanf("%d", &x), cnt -= d[x], d[x] = 0, val ^= c[x], c[x] = 0;
else if(t == 3) scanf("%d%d", &x, &y), cnt++, d[y]++, val ^= a[x], c[y] ^= a[x];
else if(t == 4) scanf("%d", &x), cnt += ind[x] - d[x], d[x] = ind[x], val ^= b[x] ^ c[x], c[x] = b[x];
puts(cnt == n && val == xor_all ? "YES" : "NO");
}
return 0;
}
D. 数据传输(transmit)
首先如果是一条链，那么我们显然可以设出 DP 状态：\(f(i, j)\) 表示前 \(i\) 项，上一台机器距离这台已经 \(j\) 根网线了，传输的最小代价。转移也很显然：
\[f(i, j) = \begin{cases} \min\limits_{1 \le j’ \le K}f(i – 1, j’), &j = 1\\ f(i – 1, j – 1), &j > 1\\ \end{cases} \]
然后我们发现这是一棵树，不是一条链。怎么办呢？虽然说它不是一条链，但是其实我们可以把两个点的路径拉出来，这就相当于是一条链了。这显然就是一个 ddp，考虑把转移写成矩阵，然后就是链上乘积。这个可以用倍增解决，不必用树剖。
感觉比较板，没有 T3 有意思。其实比 T3 简单吧。
赛后代码
coming soon.
原文地址：http://www.cnblogs.com/xxeray/p/csp-s-2022-solution.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
