题面：

F - Try a try, AC is OK

得分就是单次提交所能获得的最高分。

1
2
3
4
5
6
7
8
9
10
11
void solve(){
    int n;
    cin>>n;
    int maxx=INT_MIN;
    for(int i=1;i<=n;++i){
        int tmp;
        cin>>tmp;
        maxx=max(tmp,maxx);
    }
    cout<<maxx<<endl;
}

A - chmod

模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
	string x, s = "xwr";
	cin >> x;
	for (auto i : x) {
		int n = i - '0';
		string t;
		t.resize(3);
		for (int i = 0; i < 3; ++i)
			t[i] = (n & (1 << i) ? s[i] : '-');
		reverse(all(t));
		cout << t;
	}
	cout << endl;
}

M - Window Decoration

注意到每个中心点的代表的面积一样的，那么并且如果一个点的上下左右四个方位中也有其他的点就一定是重叠了1单位的面积，容斥一下就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
	int n;
	cin >> n;
	map<pair<int, int>, bool>f;
	int x, y;
	for (int i = 1; i <= n; ++i) {
		cin >> x >> y;
		f[{x, y}] = true;
	}
	int num = 0;
	double ans = f.size() * 2;
	for (int i = 1; i <= 99; ++i) {
		for (int j = 1; j <= 99; ++j) {
			if (f[{i, j}]) {
				if(f[{i - 1, j}])num++;
				if(f[{i, j - 1}])num++;
				if(f[{i + 1, j}])num++;
				if(f[{i, j + 1}])num++;
			}
		}
	}
	num /= 2;
	cout << ans - num * 0.5 << endl;
}

G - Disappearing Number

一个十进制数每一位都去掉了一个数字，问你在这个条件下这个十进制数是排在第几个。
现在想想每一位从原来的10种数字变成了9种数字，那不就是个十进制转换成九进制……怎么当时往数位dp上去想了

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
	int n,x;
	cin>>n>>x;
	int base=1,ans=0;
	while(n){
		int tmp=n%10;
		n/=10;
		tmp -= tmp > x;
		ans += tmp*base;
		base *= 9;
	}
	cout<<ans+1<<endl;
}

L - Chess

写一下证明。
先令k == 2，此时的LNC数是pow(2,n)-1找哪些数是必胜哪些数是必败的：
1：最简单的情况，显然先手必胜。
2：因为此时比他小的LNC数只有1，拿掉1后剩1，对于下家来说只存在必胜态1，下家必赢，先手必败，当前状态是必败的。
3：此时比他小的LNC数也是只有1，拿掉1后剩2，下家是必败态，此时先手必胜。
推测奇数是必胜否则必败(1)。
证明：因为在二进制下的LNC数都是形如1111...111这样的也就是说末尾一定是1，而必胜态是奇数，末尾是1，必败态末尾是0，那么一定存在一种方法使得先手在轮到自己的时候减去LNC数后是转向必败态，所以一定是必胜的。
然后令k == 3，也就是k == 2不行的时候，观察什么情况下k == 3是必胜的。
此时的LNC数是1 2 4 8
1：先手必胜。
2：先手必胜。
3(10)：先手可以拿掉1或者2，但都会转向必胜态，先手必败。
4(11)：先手可以拿1或拿2，或者直接拿完，存在转向必败的情况，由于考虑最优策略先手为了赢肯定让必败态转到下家，所以先手必胜。
5(12)：拿1转向必胜，拿2转向必败，拿4转向必胜，也存在转向必败的情况，先手必胜
6(20)：拿掉1,2,4，对应变成5,4,2，都是必胜的，下家必胜，先手必败。
7(21)：拿掉1,2,4，对应变成6,5,3，存在下家必败，先手必胜。
可以发现是1,2,3,4,5,6,7,8,9对应的输赢是赢赢输赢赢输赢赢输，推测n % 3 != 0是必胜否则必败(2)。
结合(1)(2)，推测n % k != 0时一定是先手赢。
证明：
显然对于k进制下个位数一定是LNC（除了0以外，即[1,k-1]），而且如果该进制下个位数是0的话一定不是LNC，也就不能一次性全部拿走，那么n % k != 0时，对于先手而言，如果当前不是个位数，那么就一定能拿的保证剩余的数在该进制下末位是0，下家就无法把它全部拿走，直到剩个位数的时候全部拿走就行。
有点像巴什博奕，改成一次只能拿[1,k-1]个石子也是一样的输赢结果。
实现的时候只要枚举进制就行，最小非因子考虑极端情况n是一些素数相乘这样才能尽可能大，这样n在1e18的范围是很小的。

1
2
3
4
5
6
void solve(){
    int x;
    cin>>x;
    for(int k=2;;++k)
        if(x%k!=0) return cout<<k<<endl,void();
}

B - Expression Matrix

队友找规律手算硬生生算出来打表的我也不知道怎么证明这个结果一定就是最小的，放下代码：

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
void solve(){
	int n,m;
	cin>>n>>m;
	if(n==3 and m==3){
		cout<<R"(111
1*1
111)";
	}else if(n==3 and m==4){
		cout<<R"(1111
1*11
1111)";
	}else if(n==3 and m==5){
		cout<<R"(11111
1*1*1
11111)";
	}else if(n==3 and m==6){
		cout<<R"(111111
1*1*11
111111)";
	}else if(n==3 and m==7){
		cout<<R"(1111111
1*1*1*1
1111111)";
	}else if(n==3 and m==8){
		cout<<R"(11111111
1*1*1*11
11111111)";
	}else if(n==3 and m==9){
		cout<<R"(111111111
1*1*1*1*1
111111111)";
	}else if(n==4 and m==3){
		cout<<R"(111
1*1
111
111)";
	}else if(n==4 and m==4){
		cout<<R"(1111
1*11
11*1
1111)";
	}else if(n==4 and m==5){
		cout<<R"(11111
1*1*1
11+11
11111)";
	}else if(n==4 and m==6){
		cout<<R"(111111
1*1*11
11*1*1
111111)";
	}else if(n==4 and m==7){
		cout<<R"(1111111
1*1*1*1
11+1*11
1111111)";
	}else if(n==4 and m==8){
		cout<<R"(11111111
1*1*1*11
11*1*1*1
11111111)";
	}else if(n==4 and m==9){
		cout<<R"(111111111
1*1*1*1*1
11+1*1*11
111111111)";
	}else if(n==5 and m==3){
		cout<<R"(111
1*1
111
1*1
111)";
	}else if(n==5 and m==4){
		cout<<R"(1111
1*11
11+1
1*11
1111)";
	}else if(n==5 and m==5){
		cout<<R"(11111
1*1*1
11+11
1*1*1
11111)";
	}else if(n==5 and m==6){
		cout<<R"(111111
1*1*11
11+1+1
1*1*11
111111)";
	}else if(n==5 and m==7){
		cout<<R"(1111111
1*1*1*1
11+1+11
1*1*1*1
1111111)";
	}else if(n==5 and m==8){
		cout<<R"(11111111
1*1*1*11
11+1+1+1
1*1*1*11
11111111)";
	}else if(n==5 and m==9){
		cout<<R"(111111111
1*1*1*1*1
11+1+1+11
1*1*1*1*1
111111111)";
	}else if(n==6 and m==3){
		cout<<R"(111
1*1
111
1*1
111
111)";
	}else if(n==6 and m==4){
		cout<<R"(1111
1*11
11*1
1*11
11*1
1111)";
	}else if(n==6 and m==5){
		cout<<R"(11111
1*1*1
11+11
1*1*1
11+11
11111)";
	}else if(n==6 and m==6){
		cout<<R"(111111
1*1*11
11*1*1
1*1*11
11*1*1
111111)";
	}else if(n==6 and m==7){
		cout<<R"(1111111
1*1*1*1
11+1*11
1*1*1*1
11*1+11
1111111)";
	}else if(n==6 and m==8){
		cout<<R"(11111111
1*1*1*11
11*1*1*1
1*1*1*11
11*1*1*1
11111111)";
	}else if(n==6 and m==9){
		cout<<R"(111111111
1*1*1*1*1
11+1*1*11
1*1*1*1*1
11*1*1+11
111111111)";
	}else if(n==7 and m==3){
		cout<<R"(111
1*1
111
1*1
111
1*1
111)";
	}else if(n==7 and m==4){
		cout<<R"(1111
1*11
11+1
1*11
11*1
1*11
1111)";
	}else if(n==7 and m==5){
		cout<<R"(11111
1*1*1
11+11
1*1*1
11+11
1*1*1
11111)";
	}else if(n==7 and m==6){
		cout<<R"(111111
1*1*11
11+1*1
1*1*11
11*1+1
1*1*11
111111)";
	}else if(n==7 and m==7){
		cout<<R"(1111111
1*1*1*1
11+1*11
1*1*1*1
11*1+11
1*1*1*1
1111111)";
	}else if(n==7 and m==8){
		cout<<R"(11111111
1*1*1*11
11+1*1*1
1*1*1*11
11*1+1+1
1*1*1*11
11111111)";
	}else if(n==7 and m==9){
		cout<<R"(111111111
1*1*1*1*1
11+1*1*11
1*1*1*1*1
11*1+1+11
1*1*1*1*1
111111111)";
	}else if(n==8 and m==3){
		cout<<R"(111
1*1
111
1*1
111
1*1
111
111)";
	}else if(n==8 and m==4){
		cout<<R"(1111
1*11
11*1
1*11
11*1
1*11
11*1
1111)";
	}else if(n==8 and m==5){
		cout<<R"(11111
1*1*1
11+11
1*1*1
11+11
1*1*1
11+11
11111)";
	}else if(n==8 and m==6){
		cout<<R"(111111
1*1*11
11*1*1
1*1*11
11*1*1
1*1*11
11*1*1
111111)";
	}else if(n==8 and m==7){
		cout<<R"(1111111
1*1*1*1
11+1*11
1*1*1*1
11*1+11
1*1*1*1
11+1*11
1111111)";
	}else if(n==8 and m==8){
		cout<<R"(11111111
1*1*1*11
11*1*1*1
1*1*1*11
11*1*1*1
1*1*1*11
11*1*1*1
11111111)";
	}else if(n==8 and m==9){
		cout<<R"(111111111
1*1*1*1*1
11+1*1*11
1*1*1*1*1
11*1+1*11
1*1*1*1*1
11*1*1+11
111111111)";
	}else if(n==9 and m==3){
		cout<<R"(111
1*1
111
1*1
111
1*1
111
1*1
111)";
	}else if(n==9 and m==4){
		cout<<R"(1111
1*11
11+1
1*11
11*1
1*11
11*1
1*11
1111)";
	}else if(n==9 and m==5){
		cout<<R"(11111
1*1*1
11+11
1*1*1
11+11
1*1*1
11+11
1*1*1
11111)";
	}else if(n==9 and m==6){
		cout<<R"(111111
1*1*11
11+1*1
1*1*11
11*1*1
1*1*11
11*1+1
1*1*11
111111)";
	}else if(n==9 and m==7){
		cout<<R"(1111111
1*1*1*1
11+1*11
1*1*1*1
11*1+11
1*1*1*1
11+1*11
1*1*1*1
1111111)";
	}else if(n==9 and m==8){
		cout<<R"(11111111
1*1*1*11
11+1*1*1
1*1*1*11
11*1*1+1
1*1*1*11
11*1+1*1
1*1*1*11
11111111)";
	}else if(n==9 and m==9){
		cout<<R"(111111111
1*1*1*1*1
11+1*1*11
1*1*1*1*1
11*1+1*11
1*1*1*1*1
11*1*1+11
1*1*1*1*1
111111111)";
	}
}

C - Seats

首先遇到存在表示关系的问题，都可以考虑抽象成点与点之间的关系，然后就可以将关系转为边建图。
对于第$i$个人希望坐在$a_i$，可以理解为$i$到$a_i$有一条有向边。找几个样例画一下图：
所以前n个点的出度一定是1。并且可以发现相互之间存在关系的才会互相影响，又因为每个人都只有一个喜欢的座位，所以对于一块区域，如果有环，那么一定是只有一个环，且这个环生在这个区域的末尾，如第二张图。
（1）如果不是一条直链或者一整个环的区域，并且如果该区域有环，最大贡献就是环的大小。
因为如果区域内的从一个点开始断开和其他点的边，也就是不满足这个点的条件，那么这个点前面的点都不能满足。所以如果环上的点不满足，也就是环上的边断开了，这个断开处的点的前面所有点都不满足，又因为是一个环，其实也就变成了所有的点都不满足。所以存在环的区域贡献其实就是环的大小。这一点其实就是有向有环图为什么没有拓扑序，因为没有了先后关系。
（2）如果不是一条直链或者一整个环的区域，并且如果该区域没有环，最大贡献就是最长路。有向无环图，可以拓扑dp跑最长路。
（3）如果是一整个环的区域，归到（1）中解决。
（4）如果是一条直链的区域，归到（2）中解决。
具体的实现先处理自环，直接累加答案。然后用tarjan找环，对于强联通分量(SCC)的大小是大于1的SCC，累加SCC的大小。
处理完环之后跑拓扑序上的最长路dp，其实不用管环，因为环是在最后出现的并且每个点出度都是1,比如第二张图中到3就停下来了原因是2还有1连着它，做拓扑序的时候不满足前面的点都出队的条件，进不了队列，在3出队之后就停下来了有环并不影响结果。
然后统计所有有向无环的区域的汇点的最长路径累加即可。对于小于等于n的点，汇点可以用出度为0判断，对于大于n的点，汇点可以用只有一条入边，也就是入度为1来判断，因为大于n汇点是0有可能是和谁都没有连边的情况。并且要注意大于n的最长路要减去1，因为末尾大于n的那个位置并不是一个嘉宾。

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
struct SCC {
	int n;
	vector<vector<int>> edge, scc;
	vector<int> stk;
	vector<int> dfn, low, bel;
	int idx, cnt;

	SCC() {}
	SCC(int n) {
		init(n);
	}

	void init(int n) {
		this->n = n;
		edge.assign(n, {});
		dfn.assign(n, -1);
		low.resize(n);
		bel.assign(n, -1);
		stk.clear();
		idx = cnt = 0;
	}

	void addEdge(int u, int v) {
		edge[u].push_back(v);
	}

	void dfs(int u) {
		dfn[u] = low[u] = idx++;
		stk.push_back(u);
		for (auto v : edge[u]) {
			if (dfn[v] == -1) dfs(v);
			if (bel[v] == -1) low[u] = min(low[u], low[v]);
		}
		if (dfn[u] == low[u]) {
			int v;
			vector<int> c;
			do {
				v = stk.back();
				c.push_back(v);
				bel[v] = cnt;
				stk.pop_back();
			} while (v != u);
			cnt++;
			scc.push_back(c);
		}
	}

	vector<int> work() {
		for (int i = 0; i < n; i++)
			if (dfn[i] == -1) dfs(i);
		return bel;
	}
};


void solve() {
	int n;
	cin >> n;
	vector<int> deg(2 * n + 1), out(2 * n + 1);
	vector<vector<int>> edge(n + 1);
//	tarjan
	SCC scc(2 * n);
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		int t;
		cin >> t;
		scc.addEdge(i - 1, t - 1);
		edge[i].push_back(t);
		if (i == t) ans++;
//		deg存入度,用于拓扑序
		deg[t]++;
//		出度
		out[i]++;
	}
//	保存一下入度
	vector<int> in(2 * n + 1);
	for (int i = 1; i <= 2 * n; ++i) in[i] = deg[i];
//	for(int i = 1;i<=2*n;++i)
//		cout<<deg[i]<<" \n"[i == 2*n];


//	先处理环
	scc.work();
	for (int i = 0; i < scc.cnt; ++i)
		if (scc.scc[i].size() > 1) ans += scc.scc[i].size();

	queue<int> q;
	vector<int> dist(2 * n + 1);
//	跑dp
	for (int i = 1; i <= n; ++i)
		if (deg[i] == 0) q.push(i), dist[i]++;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u > n) continue;
		int v = edge[u][0];
		dist[v] = max(dist[v], dist[u] + 1);
		if (--deg[v] == 0) q.push(v);
	}
	for (int i = 1; i <= 2 * n; ++i) {
		if (i <= n) {
			if (out[i] == 0) ans += dist[i];
		} else {
			if (in[i]) ans += dist[i] - 1;
		}
	}
	cout << ans << endl;
}

2024.08.06upd:好吧这个东西叫做基环树……当时没学vp的时候硬是用tarjan做出来了

剩下的金银牌题以后再补。