2021年四川省大学生程序设计大赛
儒烏風亭いおり
  2022-04-16 21:06:04 2022-04-16 21:06   2024-04-01 21:30:57      1.6k 字

比赛前

五点多去了机房，打算在机房训练

然后发现，他们在打热身赛（明天有区域赛）

所以又回了寝室

最后七点才开始

比赛时

网页卡顿， 日常了

A - Chuanpai

签到题，因为读题不仔细，测样例时挂了好几次。。。

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
void solve() {
	int k,ans = 0;
	std::cin >> k;
	for(int i = 1; i <= 6;i++)
		for(int j = i; j <= 6; j++)
		if(i + j == k)
			ans++;
	std::cout << ans << '\n';
}
int main() {
}

K - K-skip Permutation

签到题，稍微贪心一下就行

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

D - Rock Paper Scissors

贪心题，先手的选择无所谓，只需要考虑后手的对策

显然是先把所有能赢的局赢了，再是能平局的，最后不得已输掉的

WA 了一次，因为没开 long long 

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
#include<bits/stdc++.h>
void solve() {
	std::vector<int> b(3),d(3);
	for(int i = 0; i < 3; i++) std::cin >> b[i];
	for(int i = 0; i < 3; i++) std::cin >> d[i];
	long long ans = 0;
	for(int i = 0; i < 3; i++) {
		int k = std::min(b[(i + 2) % 3],d[i]);
		ans += k;
		b[(i + 2) % 3] -= k;
		d[i] -= k;
	}
	for(int i = 0; i < 3; i++) {
		int k = std::min(b[i],d[i]);
		b[i] -= k;
		d[i] -= k;
	}
	for(int i = 0; i < 3; i++) {
		int k = std::min(b[i],d[(i + 2) % 3]);
		ans -= k;
		b[i] -= k;
		d[(i + 2) % 3] -= k;
	}
	std::cout << ans << '\n';
}
int main() {
}

B - Hotpot

把每种食材的人分类

如果这类人是偶数，那么奇数位置的人永远吃不到

如果是奇数，那么轮流吃

再考虑最后一轮（或两轮，奇数情况）

直接暴力

WA 了一次，输入时的 含义搞混了

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
#include<bits/stdc++.h>
void solve() {
	int n,k,m;
	std::cin >> n >> k >> m;
	std::vector<std::vector<int>> F(k + 1);
	std::vector<int> ans(n + 1);
	for(int i = 1; i <= n; i++) {
		int x;
		std::cin >> x;
		F[x].push_back(i);
	}
	int A,B;
	A = m / n;
	B = m % n;
	for(int i = 1; i <= k; i++) {
		int size = F[i].size();
		if(size & 1) {
			int C,D;
			C = A / 2;
			D = (A % 2) * n + B;
			int flag = 0;
			for(int x : F[i]) {
				ans[x] += C;
			}
			for(int x : F[i]) {				
				if(x > D) break;
				ans[x] += flag;
				flag ^= 1;
			}
			for(int x : F[i]) {				
				if(x + n > D) break;
				ans[x] += flag;
				flag ^= 1;
			}
		}
		else {
			int flag = 0;
			for(int x : F[i]) {
				ans[x] += A * flag;
				flag ^=  1;
			}
			for(int x : F[i]) {				
				if(x > B) break;
				ans[x] += flag;
				flag ^= 1;
			}
		}
	}
	for(int i = 1; i <= n; i++) 
		std::cout << ans[i] << " \n"[i == n];
}
int main() {
}

M - True Story

之前看了一会这题，没啥思路就换了其他题

做完 之后发现挺多人过这道题的

然后想了下，发现只要最长的那个时间段能让一个人动起来，那么这个人就能到机场

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
int main() {
	int n,k,x,p;
	std::cin >> n >> k >> x >> p;
	std::vector<int> s(n + 1);
	std::vector<int> t(k + 1);
	std::vector<int> P(k + 1);
	for(int i = 1; i <= n; i++)
		std::cin >> s[i];
	int Max = p;
	for(int i = 1; i <= k; i++)
		std::cin >> t[i];
	for(int i = 1; i <= k; i++)
		std::cin >> P[i];
	for(int i = 1; i <= k; i++)
		Max = std::max(Max,P[i] - t[i]);
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		long long dis = 1ll * Max * s[i];
		if(dis >= x) ans++;
	}
	std::cout << ans;
	return 0;
}

H - Nihongo wa Muzukashii Desu

模拟题

但我真的没想到，我做着【计算机程序设计的竞赛题】，看着【英文题面】，学着【日语词性变换】

image

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
#include<bits/stdc++.h>
std::string solve() {
	std::string s,ans;
	std::cin >> s;
	int len = s.length();
	int pos = len - 4;
	std::string x;
	if(s == "ikimasu") {
		ans = "itte";
		return ans;
	}
	if(len >= 7) {
		x = s.substr(len - 7,3);		
		ans = s.substr(0,len - 7);
		if(x == "chi") {
			ans += "tte";
			return ans;
		}
		if(x == "shi") {
			ans += "shite";
			return ans;
		}
	}
	x = s.substr(len - 6,2);		
	ans = s.substr(0,len - 6);
	if(x == "ri") {
		ans += "tte";
		return ans;
	}
	if(x == "mi" || x == "bi" || x == "ni") {
		ans += "nde";
		return ans;
	}
	if(x == "ki") {
		ans += "ite";
		return ans;
	}
	if(x == "gi") {
		ans += "ide";
		return ans;
	}
	return ans;
}
int main() {
}

L - Spicy Restaurant

一百层的分层图，简单跑个多起点的

因为输入比较大，得把 cin cout 的流关掉

TLE 了一次

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
#include<bits/stdc++.h>
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n,m,q;
	std::cin >> n >> m >> q;
	std::vector<std::vector<int>> To(n + 1),w(101);
	std::vector<std::vector<int>> F(n + 1,std::vector<int> (101,1e6));
	for(int i = 1; i <= n; i++) {
		int x;
		std::cin >> x;
		w[x].push_back(i);
	}
	for(int i = 1; i <= m; i++) {
		int a,b;
		std::cin >> a >> b;
		To[a].push_back(b);
		To[b].push_back(a);
	}
	for(int i = 1; i <= 100; i++) {
		std::queue<int> q;
		for(int x : w[i]) {
			q.push(x);
			F[x][i] = 0;
		}
		while(!q.empty()) {
			int x = q.front();q.pop();
			for(int v : To[x]) {
				if(F[v][i] == 1e6) {
					F[v][i] = F[x][i] + 1;
					q.push(v);
				}
			}
		}
	}
	for(int k = 1; k <= 100; k++)
		for(int i = 1; i <= n; i++) 
				F[i][k] = std::min(F[i][k - 1],F[i][k]);
	for(int i = 1; i <= q; i++) {
		int a,b;
		std::cin >> a >> b;
		if(F[a][b] == 1e6) std::cout << -1 << '\n';
		else std::cout << F[a][b] << '\n';
	}
	return 0;
}

赛后

因为比赛是 个小时，三人一队，一台电脑

而这周时间冲突了，所以选择了 一局

想着做下去年的省赛题，感受一下，于是 了这场比赛

总体感觉不错，一个半小时的时候差不多是前十名（包含三四个高中生队伍）的样子（成都七中yyds

而去年金牌有十八个（高中生不参与评奖），咱学校去的三支队伍都是金牌

如果有队友的话，应该能轻松拿省赛金牌。听说隔壁计算机学院拿省金+三点几的绩点（均分80+）就有国一奖学金，软件学院呢？？？？！！！！似乎啥也没有。

所以问题就是，怎么才能从学校里边被选去参赛，估计得校赛排位靠前吧

至于后面的三个半小时。。。有点累了，大晚上的。。。

一个人九十分钟切了七道题也还挺不错了，换算成比赛的最终排名应该是第 41 名，稳拿银牌了

就这样吧，休息会明天上课了，话说明天不应该是星期天么TvT

  1. 比赛前
  2. 比赛时
    1. A - Chuanpai
    2. K - K-skip Permutation
    3. D - Rock Paper Scissors
    4. B - Hotpot
    5. M - True Story
    6. H - Nihongo wa Muzukashii Desu
    7. L - Spicy Restaurant
  3. 赛后