CSP-S 2022 题解

CSP-S 2022 题解

前言

由于打的肽粉了，NOIP 考前补了一下题。

T1：假期计划

题目链接：luogu P8817

题目大意

给你一个无向图，然后要你规划出一条路径，其中起点和终点都是 1 号点，然后你从中选四个不同的特殊点，形成五段路，保证每段的边数不超过 k 的情况下，四个特殊点的点权和最大。

思路

首先看到 $n$ 是 $2000$，而且边权相同，那我们完全可以用 $O(n^2)$ dfs 搜出如果这个点是特殊点，下一个可以是那些。

那把这些建图，就变成你要找一个其中一个点固定的五元环。
考虑怎么找，直接找肯定超时，考虑一个类似折中的感觉，你先找两条路径，然后看看能否拼起来。
那这样还是太多了，考虑走两步走到的位置，那对于每个位置有 $n$ 种，我们选出最优的（反正后面连着的时候也不管它）

但是这样自然有问题，就是你要五元环中每个点都不用。
那我们考虑保留前几大的，然后这些之间比一下把能用的跟最优答案比。
思考一下不难发现只要取前三大即可。

代码

#include
#include
#include
#include
#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;
}
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

T2：策略游戏

题目链接：luogu P8818

题目大意

给你一个数组 A 和一个数组 B，每次游戏给你 A 的区间和 B 的区间。
然后先手选 A 区间里的一个数，后手再选 B 区间里的一个数，两个数相乘构成分数。
先手要最大化分数，后手要最小化分数，问你每次游戏的分数。

思路

直接思考每个人的过程，分类讨论即可。主要的讨论方式就是针对 $0$，正负数展开。

可以假设先手放的数，放的 $0$ 就不管了，如果放的是正数，后手如果有负数就会放最小的负数，否则有 $0$ 放 $0$，没有就放最小的正数。
那放的负数也是相同的道理。

那对于先手而言，他如果无论放正数负数都会变成负数，那就有 $0$ 放 $0$。
否则模拟一下放最小正数和最大负数，选贡献大的。
如果有一种情况能避免的话，那就正数选最大，负数选最小（如果两种都可以就都试一下选最大）。

大概就是这样的分类讨论。

代码

#include
#include
#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;
}
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
113
114
115
116
117
118
119
120

T3：星战

题目链接：luogu P8819

题目大意

给你一个有向图，每次操作有删除一条边，恢复某条已经删了的边，删除所有还在的连着某个点的边，恢复所有连着这个点的被删掉的边。
每次操作之后，问你是否每个点都有恰好一个出边，而且都能走到一个环里。

思路

考虑先转化题意。
发现只要每个点都满足初度恰好为 $1$，另一个能走到环的条件也能满足。
那你有出边嘛，那就能一直走下去，自然就是环了。

那如果只有 $1,3$ 操作，那就很容易维护，问题是 $2,4$ 操作，它的是入边。
所以你入度是方便维护的，但是出度就不太行。
那你考虑入度初度之间的关系，那就是入度和跟出度和一样。
而且在这个限制条件下都是 $n$。

那如果满足的这个条件，也不一定行。
那要如何判断是每个点都贡献了一次，而不是一个点贡献了多次呢？
可以用哈希，每个点随机一个点权，每条边以它做入边的点做贡献。
那合法的情况就是当前所有存在的边的权和是所有点的权和。

那你每个点记录着入边的边权和就行。

代码

#include
#include 
#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;
}
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

T4：数据传输

题目大意

给你一棵树，多次询问每次你要从树上的一个点走到另一个点。
每次走你可以走到距离你当前点边数不超过 k 条边的点，并加上你走到的点的点权（起点和终点也要加），问你需要的最小点权。

思路

一个直观的想法是在树上按着 DP，甚至只需要在路径上的点里面看。
但这样在 $k=1,2$ 没问题，但是在 $k=3$ 的时候会有一个特别的情况：
就是走两步往外选一个点停下算贡献，再走回来然后走两步。
不过也不会有问题，你用一个 $w_i$ 记录它以及它一步能走到的边权最小的点权，就也可以弄。

那至于在树上，你就拆成 LCA 的两段。
那你可以用树链剖分或者倍增，这里用的是倍增，来造每一段的转移。
那思考怎么转移，那你不难想象到是从 $(x,a)\to (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
#include
#include
#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;
}
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