2022年团体程序设计天梯赛
儒烏風亭いおり
  2022-04-23 17:00:00 2022-04-23 17:00   2024-04-01 21:30:06      2.3k 字

比赛前

上午《军事理论》考试

考完后去东园吃了个午饭，十二点前到了集训教室

玩了会 ，大乱斗对线九级电脑终于胜率有八成了(╥╯^╰╥)

线上比赛登录挺麻烦的

比赛时

打算晚个几分钟开题的，最后还是在一点半开题。。。

L1-1

签到题

1
2
3
4
5
6
#include<bits/stdc++.h>
int main() {
	std::cout << "I'm gonna win! Today!\n";
	std::cout << "2022-04-23\n";
	return 0;
}

L1-2

小学数学题

1
2
3
4
5
6
7
8
#include<bits/stdc++.h>
int main() {
	int N,v;
	std::cin >> N >> v;
	int ans = N / v;
	std::cout << ans << '\n';
	return 0;
}

L1-3

小模拟题，因为没想那么多，所以代码稍微有点长，不过都是复制粘贴也没花多长时间

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<bits/stdc++.h>
int main() {
	int a,b,c,d;
	std::cin >> a >> b >> c >> d;
	if(c >= a && d >= a) {
		std::cout << c << "-Y " << d << "-Y\n";
		std::cout << "huan ying ru guan\n";
	}
	else if(c >= b || d >= b) {
		std::cout << c << "-Y " << d << "-Y\n";
		if(c >= b) std::cout << "qing 1 zhao gu hao 2\n";
		else std::cout << "qing 2 zhao gu hao 1\n";
	}
	else {
		if(c > a) {
			std::cout << c << "-Y " << d << "-N\n";
			std::cout << "1: huan ying ru guan\n";
		}
		else if(d > a) {	
			std::cout << c << "-N " << d << "-Y\n";
			std::cout << "2: huan ying ru guan\n";
		}
		else {
			std::cout << c << "-N " << d << "-N\n";
			std::cout << "zhang da zai lai ba\n";
		}
	}
	return 0;
}

L1-4

小学数学题

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
int main() {
	int a,b;
	std::cin >> a >> b;
	int ans = 1;
	for(int i = 1; i <= a + b; i++)
		ans = ans * i;
	std::cout << ans <<'\n';
	return 0;
}

L1-5

小模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
int main() {
	std::vector<int> a(6);
	int n;
	for(int i = 0; i < 6; i++) 
		std::cin >> a[i];
	std::cin >> n;
	for(int i = 0; i < 6; i++) {
		int pos = 6,k = n;
		while(true) {
			if(a[i] == pos) k++;
			if(k == 1) break;
			k--;
			pos--;
		}
		std::cout << pos;
		if(i != 5) std::cout << ' ';
	}
	return 0;
}

L1-6

小模拟

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
#include<bits/stdc++.h>
int main() {
	std::string a,b;
	std::cin >> a >> b;
	std::string ansA = "";
	std::string ansB = "";
	int lena = a.length();
	int lenb = b.length();
	for (int i = 1; i < lena; i++) {
		if((int)a[i] % 2 == (int)a[i-1] % 2) {
			if((int) a[i] > (int) a[i - 1])
				ansA += a[i];
		  	else ansA += a[i - 1];
	 	}
	}
	for (int i = 1; i < lenb; i++) {
		if((int)b[i] % 2 == (int)b[i-1] % 2) {
			if((int) b[i] > (int) b[i - 1])
				ansB += b[i];
		  	else ansB += b[i - 1];
	 	}
	}
	if(ansA == ansB) std::cout << ansA << '\n';
	else std::cout << ansA << '\n' << ansB << '\n';
	return 0;
}

L1-7

小学数学题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
int main() {
	int N,M,Q;
	std::cin >> N >> M >> Q;
	std::vector<int> a(N + 1),b(M + 1);
	for(int i = 0; i < Q; i++) {
		int t,c;
		std::cin >> t >> c;
		if(t == 0) a[c] = true;
		else b[c] = true;
	}
	int ans = 0;
	for(int i = 1; i <= N; i++)
		for(int j = 1; j <= M; j++)
			if(a[i] != true && b[j] != true)
				ans++;
	std::cout << ans << '\n';
	return 0;
}

L1-8

贪心题

能选就选

开始还在想暴力会不会被卡掉，想着不罚时就直接交了，结果能过。。

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<bits/stdc++.h>
int N,K,S,ans;
std::vector<std::pair<int,int>> a;
std::vector<int> b;
void solve(int x) {
	if(a[x].first < 175) return;
	for(int i = 0; i < K; i++) {
		if(a[x].first > b[i]) {
			b[i] = a[x].first;
			ans++;
			return;
		}
		if(a[x].first == b[i] && a[x].second >= S) {
			ans++;
			return;
		}
	}
}
int main() {
	std::cin >> N >> K >> S;
	a.resize(N);b.resize(K);
	for(int i = 0; i < N; i++) 
		std::cin >> a[i].first >> a[i].second;
	std::sort(a.begin(), a.end());
	for(int i = 0; i < N; i++)
		solve(i);
	std::cout << ans << '\n';
	return 0;
}

L2-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
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
#include<bits/stdc++.h>
int main() {
	int n,m,k;
	std::cin >> n >> m >> k;
	std::queue<int> a;
	for(int i = 0; i < n; i++) {
		int x;
		std::cin >> x;
		a.push(x);
	}
	std::stack<int> b;
	std::vector<std::vector<int>> ans;
	while(true) {
		if(a.empty() && b.empty())
			break;
		std::vector<int> pos;
		pos.clear();
		pos.push_back(150);
		int cnt = 0;
		while(true) {
			if(cnt == k) break;
			if(!b.empty() && pos[cnt] >= b.top()) {
					pos.push_back(b.top());
					b.pop();
					cnt++;
			}
			else if(!a.empty()) {
				if(pos[cnt] >= a.front()) {
					pos.push_back(a.front());
					a.pop();
					cnt++;
				}
				else {
					if((int)b.size() == m) break;
					b.push(a.front());
					a.pop();
				}
			}
			else {
				break;
			}
		}
		ans.push_back(pos);
	}
	bool flag = false;
	for(auto v : ans) {
		if(flag) std::cout << '\n';
		bool Flag = false;
		for(int x : v) {
			if(x != 150) {
				if(Flag) std::cout << ' ';
				Flag= true;
				std::cout << x;
			}
		}
		flag = true;
	}
	return 0;
}

L2-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
#include<bits/stdc++.h>
int main() {
	int n;
	std::cin >> n;
	std::vector<std::pair<std::string,std::string>> s(n);
	for(int i = 0; i < n; i++) {
		std::string x;
		std::cin >> s[i].first >> x >> s[i].second;
	}
	std::sort(s.begin(), s.end());
	std::string x = "00:00:00";
	bool flag = false;
	for(int i = 0; i < n; i++) {
		if(s[i].first != x) {
			if(flag) std::cout << '\n';
			flag = true;
			std::cout << x << " - " << s[i].first;
		}
		x = s[i].second;
	}
	if(x != "23:59:59") {
		if(flag) std::cout << '\n';
		std::cout << x << " - " << "23:59:59";
	}
	return 0;
}

L2-3

感觉我想复杂了，而且还没过。。。

考虑 序将树变成数组

然后最小代价是 序相邻的两个点之间的距离之和 深度最大的点

离线倒序处理

找到原因了，根节点可能不是 ，懒得改了，摆烂

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
#include<bits/stdc++.h>
const int MAXN = 2e5;
int n,m,tim;
std::vector<std::vector<int>> To,Fa;
std::vector<int> Deep,dfn,id;
void init() {
	To.resize(MAXN + 1);
	Fa.resize(MAXN + 1,std::vector<int> (21));
	Deep.resize(MAXN + 1);
	dfn.resize(MAXN + 1);
	id.resize(MAXN + 1);
}
void dfs(int u) {
	dfn[u] = ++tim;
	id[tim] = u;
	Deep[u] = Deep[Fa[u][0]] + 1;
	for(int v : To[u]) {
		Fa[v][0] = u;
		dfs(v);
	}
}
int Lca(int x,int y) {
	if(Deep[x] < Deep[y]) std::swap(x,y);
	for(int i = 20; i >= 0; i--)
		if(Deep[Fa[x][i]] >= Deep[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];
}
int dist(int x,int y) {
	int lca = Lca(x,y);
	return Deep[x] + Deep[y] - 2 * Deep[lca];
}
int main() {
	std::cin >> n >> m;
	init();
	for(int i = 1; i <= n; i++) {
		int x;
		std::cin >> x;
		if(x == -1) continue;
		To[x].push_back(i);
	}
	dfs(1);
	for(int k = 1; k <= 20; k++)
		for(int i = 1; i <= n; i++)
			Fa[i][k] = Fa[Fa[i][k - 1]][k - 1];
	std::vector<int> ans(MAXN + 1),add(MAXN + 1),cnt(MAXN + 1);
	for(int i = 1; i <= m; i++) {
		std::cin >> add[i];
		cnt[add[i]]++;
	}
	std::vector<int> nxt(MAXN + 1),pre(MAXN + 1);
	std::priority_queue<int> A,B;
	A.push(1);
	int pos = 1;
	for(int i = 2; i <= n; i++) {
		if(cnt[id[i]]) {
			A.push(Deep[id[i]]);
			nxt[pos] = id[i];
			pre[id[i]] = pos;
			pos = id[i];
		}
	}
	nxt[pos] = 1;pre[1] = pos;
	
	int ANS = 0;
	pos = 1;
	while(true) {
		ANS += dist(pos,nxt[pos]);
		if(nxt[pos] == 1) break;
		pos = nxt[pos];
	}

	for(int i = m; i >= 1; i--) {
		ans[i] = ANS - (A.top() - 1);
		cnt[add[i]]--;
		if(cnt[add[i]] == 0) {
			int x = add[i];
			int l = pre[x];
			int r = nxt[x];
			ANS = ANS - dist(l,x) - dist(x,r) + dist(l,r);
			B.push(Deep[x]);
			nxt[l] = r;
			pre[r] = l;
		}
		while(!B.empty() && B.top() == A.top()) {
			B.pop();
			A.pop();
		}
	}

	for(int i = 1; i <= m; i++) {
		std::cout << ans[i] << '\n';
	}
	return 0;
}

L2-4

板子题目

不知道哪里挂了，拿了部分分

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
#include<bits/stdc++.h>
int main() {
	int n;
	std::cin >> n;
	std::vector<std::string> a(n + 1);
	std::vector<std::vector<int>> dist(n + 1,std::vector<int> (n + 1,1e8));
	for(int i = 1; i <= n; i++) {
		std::cin >> a[i];
		int k;
		std::cin >> k;
		for(int j = 1; j <= k; j++) {
			int v,w;
			char c;
			std::cin >> v >> c >> w;
			dist[i][v] = w;
		}
	}
	for(int k = 1; k <= n; k++) 
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)	
				if(i != k && j != k && i != j && dist[i][k] + dist[k][j] < dist[i][j])
					dist[i][j] = dist[i][k] + dist[k][j];
	std::vector<int> D(n + 1);
	D[0] = 2e8;
	int pos = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] == "M") continue;
		for(int j = 1; j <= n; j++) {
			if(a[j] == "F") continue;
			D[i] = std::max(D[i],dist[j][i]);
		}
		if(D[i] < D[pos]) pos = i;
	}
	bool flag = false;
	for(int i = 1; i <= n; i++) {
		if(a[i] == "M") continue;
		if(D[i] == D[pos]) {
			if(flag) std::cout << ' ';
			flag = true;
			std::cout << i;
		}
	}
	std::cout << '\n';

	pos = 0;
	for(int i = 1; i <= n; i++) {
		if(a[i] == "F") continue;
		for(int j = 1; j <= n; j++) {
			if(a[j] == "M") continue;
			D[i] = std::max(D[i],dist[j][i]);
		}
		if(D[i] < D[pos]) pos = i;
	}
	flag = false;
	for(int i = 1; i <= n; i++) {
		if(a[i] == "F") continue;
		if(D[i] == D[pos]) {
			if(flag) std::cout << ' ';
			flag = true;
			std::cout << i;
		}
	}
	return 0;
}

L3-1

模拟了大半天，最后还没写完就结束了

赛后想了一下，只需要比较两个相邻的，搞一个拓扑排序就行。比赛时想复杂了。。。

比赛后

感觉这次题目比以前难（错觉？

只有 分

虽然前几年参加的那次打得更撇

稍微看了下，如果没理解错评奖规则的话，那应该是个人国三，团队国三，团队省二，学校省一

明天再加油

赛后去团建干饭了

好久没出校吃饭了，感觉被学校封了两个月。。。

22天梯赛_01

UPD:2022.5.18

一堆证书，虽然没一个有用的。。。

22天梯赛_02

22天梯赛_03

22天梯赛_04

22天梯赛_05

22天梯赛_06

22天梯赛_07

  1. 比赛前
  2. 比赛时
    1. L1-1
    2. L1-2
    3. L1-3
    4. L1-4
    5. L1-5
    6. L1-6
    7. L1-7
    8. L1-8
    9. L2-1
    10. L2-2
    11. L2-3
    12. L2-4
    13. L3-1
  3. 比赛后
    1. UPD:2022.5.18