题面：

24年的好像打完了……从cf上随便找了一个打着玩。

四川的依然还是那么简单，单挑差两题ak（cf上的没有C I J题）。

签到/简单题

A题就是求方程x+y=k的解的个数。直接枚举就行。

M题在说有n个旅客在位置0同时出发赶飞机，飞机的位置是x。每个人都是按一定的速度匀速运动。初始时，飞机预定在时刻p0起飞。有m 个广播，第i个广播表示在某个时刻（可能早于p0时刻）告诉所有旅客飞机延误到了pi， 保证ti和pi是递增的。每个旅客在每个时刻都会根据当前自己的位置、当前自己的速度和当前预定的起飞时间来决定行动：如果赶得上飞机就继续移动，否则就原地停留，求总共有多少人可以顺利登机。问最终有多少个旅客赶得上飞机。先预处理姜所有的广播时间和p0比较，如果早于p0就改成p0，然后计算其总共延长的时间，找到最大的延长时间，如果这段时间按该乘客的移动速度可以到达机场就说明这个乘客能登机，遍历一遍就可以统计出有多少人能顺利起飞。这题是简单题里面通过率最低的一个，我感觉还是题目实在是太绕了导致的（我至少读了20min的题面还没理解wa了一次）。怎么会有这么反人类的题目背景还说是True Story……

H题是告诉你日语中一些动词的罗马音变换形式。写个循环找后缀去匹配。

K题是构造排列，求一个最大化相邻数字之间的差等于k的、长度为n的排列。贪心去构造，每相邻k的数字放在一块，可以反证出不同块之间绝对互相干扰并且此时是最优解，所以最后将这些块随便按什么顺序组合都行，全部输出就可以过了。

D题，两个玩家博弈玩石头剪刀布，每个玩家的卡牌个数总数相同，计分数为赢一局加一分，输一局减一分，出拳一样分数不增不减，双方明牌，Alice先手，希望最小化得分，Bob后手，希望最大化得分，求两者均最优策略下的得分是多少。那么显然后手占优，最后的答案一定是所有可能结果中最大得分的那一个，范围给的小，直接枚举排列就行。

B题在说n个人（0索引开始的编号）围成环形吃火锅，每个人都有喜欢的火锅材料，从第0个人开始一共循环进行m次操作，分两种情况，如果当前火锅中有这个编号的人喜欢吃的材料那么这个人就会把这个东西从火锅里面捞出来吃，并且好感度++,否则就把材料放火锅里面，这个人的好感度不变。求这m轮操作后所有人好感度的总和。也不难只要先计算一次2n个操作，因为2n个操作中，喜欢第i个材料的人的总数一定是偶数，这样就能在内部处理好所有的情况，然后数有几个2n的倍数，之后再加上剩余的好感度就可以了。

L - Spicy Restaurant

形式化来说就是给了一个无向图，每个顶点有一个属性$ W_i $，边权是1，$ Q $个询问，第i个询问给定顶点$ p_i
$和阈值$ a_i $，问距离点$ p_i $最近的$ W_i \le a_i $的$ i $距离$ p_i $有多远。$ 1 \le W_i \le 100 $。

vp的时候MLE了一次。

显然是最短路相关的题，离线查询后暴力每一个顶点的最短路，这种写法肯定要超时，因为最劣是n*最短路复杂度。注意到$ W_i $范围很小，所以可以考先预处理出每一个阈值对应的最短路，将所有的小于这个阈值的顶点与一个超级源点链接，从源点开始跑最短路，跑100种情况就行，但是这样用dij跑的话会有问题，空间和时间都会超。

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
// dij爆空间爆时间
struct SP {
	struct Edge {
		int to;
		int w;
		Edge(int a, int b) {
			to = a;
			w = b;
		}
	};

	typedef pair<int, int> PII;
	int n, s;
	vector<vector<Edge>> edge;
	vector<int> dist;
	vector<bool> st;

	SP(int _n, int _s) : n(_n), s(_s), edge(_n + 1), dist(_n + 1), st(_n + 1) {};

	void dij() {
		fill(all(dist), 1e18);
		dist[s] = 0;
		priority_queue<PII, vector<PII>, greater<>> heap;
		heap.emplace(0, s);
		while (!heap.empty()) {
			auto ver = heap.top().second;
			heap.pop();
			if (st[ver]) continue;
			for (auto &i : edge[ver]) {
				int j = i.to;
				if (dist[j] > dist[ver] + i.w) {
					dist[j] = dist[ver] + i.w;
					heap.emplace(dist[j], j);
				}
			}
		}
	}
};

void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> w(n);
	for (int i = 0; i < n; ++i) cin >> w[i];
	SP sp1(n,0ll);
	for(int i = 0,v,u;i<m;++i){
		cin>>u>>v;
		sp1.edge[u].push_back({v,1});
		sp1.edge[v].push_back({u,1});
	}
	vector<SP> hot;
	for(int i = 1;i<=100;++i){
		SP sp(n,0ll);
		sp.edge = sp1.edge;
		for(int j = 0;j<n;++j){
			if(w[j] <= i) sp.edge[0].push_back({j + 1,0});
		}
		sp.dij();
		hot.push_back(sp);
	}
	
	while(q--){
		int p,a;
		cin>>p>>a;
		a--;
		cout<<(hot[a].dist[p] == 1e18 ? -1 :hot[a].dist[p])<<endl;
	}
}

注意到边权是1，所以可以直接跑bfs求最短路。

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
//正解
void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> w(n);
	for (int i = 0; i < n; ++i) cin >> w[i];
	vector<vector<int>> edge(n + 1);
	for (int i = 0, u, v; i < m; ++i) {
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	vector<vector<int>> dist(101);
	auto bfs = [&](int x) {
		queue<int> q;
		vector<int> d(n + 1, -1);
		for (int i = 1; i <= n; ++i) {
			if (w[i - 1] <= x) q.push(i),d[i] = 0;
		}

		while (!q.empty()) {
			auto u = q.front();
			q.pop();

			for (int v : edge[u]) {
				if (d[v] == -1) {
					d[v] = d[u] + 1;
					q.push(v);
				}
			}

		}
		dist[x] = d;
	};
	while(q--){
		int a,p;
		cin>>p>>a;
		cout<<dist[a][p]<<endl;
	}

}

E - Don’t Really Like How The Story Ends

给定一张无向图，问最少添加多少条边，可以使得1,2,··· ,n是 这张图的一个合法DFS序列。

考虑什么时候不得不加边：如果在我们dfs的过程中走到了i，并且不可能在下一步走到i+1，那么我们必须添加一条边使得下一步能走到i+1，就是在说当前的DFS栈中，最深的一个有未访问邻居的 点与i+1不相邻。

vp的时候的代码，写的很乱很丑，乱搞一遍过的。

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
void solve() {
	int n,m;
	cin>>n>>m;
	vector<vector<int>> edge(n+1);
	
	for(int i = 0,u,v;i<m;++i){
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	
	int p = 2;
	
	int ans = 0;
	
	vector<bool> st(n+1);
	vector<bool> b(n+1);
	for(int i = 1;i<=n;++i) sort(all(edge[i]));
	
	function<void(int)> dfs = [&](int u)->void{
//		cerr<<u<<' '<<ans<<endl;
		if(u > n) return;
		st[u] = true;
		
		for(auto i : edge[u]) b[i] = true;
		int ok = 0;
		for(int i = 0;i<si(edge[u]);++i){
			int v = edge[u][i];
			if(st[v])continue;
			ok = 1;
//			p++;
			if(v != p){
				p++;
//				cerr<<u<<endl;
				ans++;
				dfs(p - 1);
				--i;
			}else{
//				cerr<<u<<endl;
				p++;
				dfs(p - 1);
			}
		}
		
		if(!ok && p <= n && !b[p]){
			p++;
			ans++;
//			cerr<<u<<' '<<p<<endl;
//			cerr<<p<<endl;
			dfs(p - 1);
		}
		
	};
	
	dfs(1);
	
	cout<<ans<<endl;
}