Zirnc's Blog

他山之石，可以攻玉。

CSP-J1

入学你校几乎两个月都在搞初赛。

结果初一还是只有两个人过了

最后是 73.5 分，水过去了。

CSP-J2

Day 0

要去大学城的广大附中，就去住酒店了。

在 tjl 大佬房间里 玩，其实是在看凤凰台。

依稀记得那晚上拜登和特朗普的比分是 264 : 214，林郑去北京见韩正了。

CCTV-7 上面中科院在帮农民种橘子？

十点多就回去昏昏沉沉地睡了，还挺香（

Day 1

早上六点半就醒了。

在酒店吃了顿自助早餐，真香。

breakfast

到处都是石实的大佬 %%% 。

ssdl

然后搭着同校热心家长的车前往广大附中。

gdfz

门口还挺热闹的，好像发生了许多事情：

于是感到很庆幸，没入考场的时候也是一场考验。。所以说带齐资料很重要。

很快就进考场了。

电脑有 8G 内存，装的是 Windows 10 神州网信政府版，感觉只是开始菜单看上去稍有不同。

下发题目之后几分钟我还在打 A+B，打完之后才一愣一愣地抄密码解压题目。

翻了一下，发现第一题好难，于是从第二题开始做。

T2 刚开始竟然用了 sort，到了最后试大样例的时候才看到一卡一卡的，于是又改成了插入排序，以为没问题了。

 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

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) { return a > b; }
int a[100005];
int main()
{
	int n, w;
	scanf("%d%d", &n, &w);
	
	for (int i = 0; i < n; i++) {
		int inp;
		scanf("%d", &inp);
		int j = 0;
		for (; j < i; j++) {
			if (a[j] < inp) break;
		}
		for (int k = i; k >= j; k--) {
			a[k+1] = a[k];
		}
		a[j] = inp;
		
		int planNum = max(1, (int)((i+1)*0.01*w));
		printf("%d ", a[planNum-1]);
	}
	return 0;
}

然后 T3 看了好久才弄懂，就暴力 stack 了。

 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

#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
#include <fstream>
#include <cstdio>
using namespace std;
int n;
int a[100003];
int main()
{
	string expr;
	getline(cin, expr);
	const int exprlen = expr.length();
	
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	int q;
	scanf("%d", &q);
	
	stack<int> s;
	for (int i = 0; i < q; i++) {
		int t;
		scanf("%d", &t);
		a[t] = !a[t];
		
		string cur;
		for (int j = 0; j < exprlen+1; j++) {
			if (j == exprlen || expr[j] == ' ') {
				if (cur == "!") {
					int t = s.top();
					s.pop();
					s.push(!t);
				} else if (cur == "&") {
					int t = s.top();
					s.pop();
					int t2 = s.top();
					s.pop();
					s.push(t && t2);
				} else if (cur == "|") {
					int t = s.top();
					s.pop();
					int t2 = s.top();
					s.pop();
					s.push(t || t2);
				} else if (cur[0] == 'x') {
					int xb = 0;
					for (int k = 1; k < cur.length(); k++) {
						xb *= 10;
						xb += cur[k]-'0';
					}
					s.push(a[xb]);
				}
				
				cur.clear();
			} else cur += expr[j];
		}
		
		printf("%d\n", s.top());
		if (!s.empty()) s.pop();
		a[t] = !a[t];
	}
	return 0;
}

接下来才开始构思第一题，一直摸不着头绪，就随随便便写了一个爆搜，枚举 2 的幂相加。

 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

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
int n;
const int a[23] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608};
int ansn = 0, ans[24]; 
int dfs(int step, int sum) {
	if (sum > n) return 0;
	if (step > 23) return 0;
	
	if (sum == n) {
		return 1;
	}
	
	for (int i = 1; i <= 22; i++) {
		int t1 = dfs(step+i, sum + a[step]);
		if (t1) {
			ans[ansn++] = a[step];
			return 1;
		}
	}
}
int main()
{
	cin >> n;
	
	if (n % 2 != 0) { 
		cout << -1 << endl;
		return 0;
	}
	
	for (int i = 0; i < 23; i++) {
		if (n == a[i]) {
			cout << a[i] << endl;
			return 0;
		}
	}
	
	dfs(0, 0);	
	
	for (int i = 0; i < ansn; i++) {
		cout << ans[i] << ' ';
	}
	
	return 0;
}

第四题直接无脑爆搜，能拿到暴力分就 ok。

 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

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;
long long ans = -99999999999;
int a[1005][1005], n, m;
bool vis[1005][1005];
const int dx[3] = { -1, 1, 0 };
const int dy[3] = { 0,  0, 1 };
void dfs(int x, int y, long long sum) {
	if (x == n && y == m) {            // 终点 
		ans = max(ans, sum+a[x][y]);
		return ;
	}
	for (int i = 0; i < 3; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
		if (vis[nx][ny]) continue ;
		vis[nx][ny] = 1;
		dfs(nx, ny, sum + a[x][y]);
		vis[nx][ny] = 0;
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			vis[i][j] = false;
		}
	}
	
	dfs(1, 1, 0);
	
	printf("%d\n", ans);
	return 0;
}

出了考场之后和 tjl 对答案，才知道第一题考的是二进制，第二题要用桶排序。。。

然后那时竟然还挺乐观的，觉得我的也没问题。。。

甚至还开始讨论有没有 1= 。。。。。。。。。

直到洛谷上了民间数据自测。

100 + 80 + 30 + 15 = 225

还是看看能不能有二等吧。。

总之达到了考前的期望，考后还是太自信了一点点。也没什么遗憾，正常发挥出了自己的水平。

那么就：

CSP-J/S 2021 RP++

UPD: 215 分，2=

#游记 #OI #CSP