2022年四川省大学生程序设计大赛选拔赛
儒烏風亭いおり
  2022-05-04 18:30:00 2022-05-04 18:30   2022-12-28 14:54:36      2.1k 字

比赛前

提前吃了午饭，然后十二点半到了机房

失策了，今儿这个没纸质版题面，允许用三台电脑看题，一台电脑敲代码

比赛时

榜单

A

正序开题，看了眼 ，感觉可做

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() {
	long long n;
	std::cin >> n;
	std::string S,T;
	std::cin >> S >> T;
	long long l,r;
	l = 0;
	r = 0;
	long long ans = 0;
	while(r < n) {
		if(S[r] == T[r]) r++;
		else {
			if(S[r] < T[r])
				ans += 1ll * (r - l + 1) * (n - r);
			l = r + 1;
			r = l;
		}
	}
	std::cout << ans << '\n';
}

WA 了一发long long，不过是全场首 A，虽然也没有加分罢了。。。

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
#include<bits/stdc++.h>
#define LL long long
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	LL n;
	std::cin >> n;
	std::vector<LL> a(n + 1),b(n + 1);
	for(int i = 0; i <= n; i++)
		std::cin >> a[i];
	for(int i = 0; i <= n; i++)
		std::cin >> b[i];
	LL ans = 0;
	for(int i = n; i >= 0; i--) {
		if(b[i] > a[i]) {
			if(i == 0) ans = -1;
			else {
				LL x = (1ll * b[i] - a[i] + 1) / 2;
				ans += x;
				a[i - 1] -= x;
			}
		}
	}
	std::cout << ans << '\n';
}

J

简单贪心

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
#include<bits/stdc++.h>
#define LL long long
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n,pair = 0;
	std::cin >> n;
	std::string S;
	std::cin >> S;
	std::queue<int> B,C;
	for(int i = 0; i < 2 * n; i++) {
		if(S[i] == 'A') pair++;
		if(S[i] == 'B') B.push(i);
		if(S[i] == 'C') C.push(i);
	}
	pair = n - pair;
	int pos;
	std::vector<bool> book(2 * n);
	std::vector<int> ansx,ansy;

	while(pair > 0) {
		if(B.empty()) {
			std::cout << "NO\n";
			return 0;
		}
		
		while(!C.empty() && C.front() < B.front())
			C.pop();

		if(C.empty()) {
			std::cout << "NO\n";
			return 0;
		}	
		pair--;
		ansx.push_back(B.front());book[B.front()] = true;B.pop();
		ansy.push_back(C.front());book[C.front()] = true;C.pop();
	}
	pos = 0;
	while(pos < 2 * n) {
		if(S[pos] == 'A' || book[pos] == true) pos++;
		else break;
	}
	for(int i = 0; i < 2 * n; i++) {
		if(book[i] == false) {
			if(S[i] == 'B' || S[i] == 'C') {
				std::cout << "NO\n";
				return 0;
			}
			if(pos == 2 * n) {
				std::cout << "NO\n";
				return 0;
			}
			ansx.push_back(i);
			ansy.push_back(pos);
			book[i] = book[pos] = true;
			while(pos < 2 * n) {
				if(S[pos] == 'A' || book[pos] == true) pos++;
				else break;
			}
		}
	}
	std::cout << "YES\n";
	for(int i = 0; i < n; i++) 
		std::cout << ansx[i] + 1 << ' ' << ansy[i] + 1 << '\n';
}

F

贪心

细节有点多，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
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
#include<bits/stdc++.h>
#define LL long long
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	LL N,X,R,P,K;
	std::cin >> N >> X >> R >> P >> K;

	std::string S;
	std::cin >> S;

	LL ans = 0;
	ans = N * X;

	LL posi = 0,posj = 0;
	while(posj != N && S[posj] != '1') 
		posj++;
	std::vector<bool> book(N);
	LL POS = 0;
	while(true) {
		// std::cout << posi << ' ' << posj << ' '
		// 	<< K << ' ' << ans << '\n';
		while(posi < N && book[posi])
			posi++;
		while(posj < N &&book[posj])
			posj++;
		if(posj == N && K == 0) break;

		else if(K == 0) {
			ans -= R * (N - posj);
		
			posj++;
			while(posj != N && S[posj] != '1') 
				posj++;
		}
		
		else if(posj == N) {
			while(POS < N && book[POS] == true)
				POS++;
			ans += P * (N - POS);
			K--;
			POS++;
		}
		
		else {
			LL A,B;
			A = P * (N - posi) - R * (N - posj);
			B = P * (N - posj);
			// std::cout << "A = "  << A << "  B = " << B  << 
				// '\n';
		
			if(A > B) {
				ans += P * (N - posi);
				if(posi == posj) {
					posj++;
					while(posj != N && S[posj] != '1') 
						posj++;
				}
				book[posi] = true;
				posi++;
				// std::cout << "posi=" << posi << '\n';
				K--;
			}
		
			else {
				ans += P * (N - posj);
				if(posi == posj) posi++;
								// std::cout << "posj= " << posj << '\n';
				book[posj] = true;
				posj++;
				while(posj != N && S[posj] != '1') 
					posj++;
				K--;
			}
		}
	}
	std::cout << ans << '\n';
	return 0;
}

G

队友太猛了！！！

一发AC

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;
struct node
{
	ll x,y;
}a[maxn];
int cmp(node a,node b)
{
	return a.x+a.y<b.x+b.y;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	ll n,ans=0;
	cin>>n;
	for(int i=1;i<=n*2;i++)
	{
		cin>>a[i].x>>a[i].y;
		if(a[i].x>a[i].y)
			swap(a[i].x,a[i].y);
	}
	sort(a+1,a+n*2+1,cmp);
	for(int i=1;i<=n;i++)
		ans-=a[i].x;
	for(int i=n+1;i<=n*2;i++)
		ans+=a[i].y;
	cout<<ans;
}

L

比 G 题先开始写，然后挂了几个点，中间过了 G 题，L还是卡着

写了写SPJ，跑了几百组数据，还是挂了

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
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
#include<bits/stdc++.h>
#define LL long long
LL n;
LL A,B,C;
LL a,b,c;
LL ca,cb,cc;
LL l,r = -1;
char s[1000000];
void add() {
	r++;
	if(r >= 3 * n) return;
	if(s[r] == 'A') a++;
	if(s[r] == 'B') b++;
	if(s[r] == 'C') c++;
}
void minu() {
	if(l >= 3 * n) return;
	if(s[l] == 'A') a--;
	if(s[l] == 'B') b--;
	if(s[l] == 'C') c--;
	l++;
}
bool check(LL pos) {
	LL AA,BB,CC;
	AA = A - a;
	BB = B - b;
	CC = C - c;
	if(pos == 1) AA += r - l + 1;
	if(pos == 2) BB += r - l + 1;
	if(pos == 3) CC += r - l + 1;
	if(AA == n && BB == n && CC == n)
		return true;
	return false;
}
int main() {
	 // freopen("in.txt","r",stdin);
	 // freopen("out.txt","w",stdout);
	std::cin >> n;
	std::cin >> s;
	// std::cout<<s<<'\n';
	for(LL i = 0; i < 3 * n; i++) {
		if(s[i] == 'A') A++;
		if(s[i] == 'B') B++;
		if(s[i] == 'C') C++;
	}
	if(A == n && B == n && C == n) {
		std::cout << 0 << '\n';
		return 0;
	}

	LL cnt = (A >= n) + (B >= n) + (C >= n);
	if(cnt >= 2) {
		add();
		while(true) {
			if(l >= 3 * n || r >= 3 * n) break;
			if(A < n) {
				if(check(1)) {
					std::cout << 1 << '\n';
					std::cout << l + 1 << ' ' << r + 1 << ' ' << 'A' << '\n';
					return 0;
				}
				if(A - a + (r - l + 1) < n) add();
				else if(B - b > n) add();
				else if(C - c > n) add();
			
				else if(A - a + (r - l + 1) > n) minu();
				else if(B - b < n) minu();
				else if(C - c < n) minu();
			}
			else if(B < n) {
				if(check(2)) {
					std::cout << 1 << '\n';
					std::cout << l + 1 << ' ' << r + 1 << ' ' << 'B' << '\n';
					return 0;
				}
				if(A - a > n) add();
				else if(B - b + (r - l + 1) < n) add();
				else if(C - c > n) add();
			
				else if(A - a < n) minu();
				else if(B - b + (r - l + 1) > n) minu();
				else if(C - c < n) minu();
			}
			else if(C < n) {
				if(check(3)) {
					std::cout << 1 << '\n';
					std::cout << l + 1 << ' ' << r + 1 << ' ' << 'C' << '\n';
					return 0;
				}
				if(A - a > n) add();
				else if(B - b > n) add();
				else if(C - c + (r - l + 1) < n) add();
			
				else if(A - a < n) minu();
				else if(B - b < n) minu();
				else if(C - c + (r - l + 1) > n) minu();
			}
		}
	}


	if(A > n) {
		LL pos = -1;
		while(ca < n) {
			pos++;
			if(s[pos] == 'A') ca++;
			if(s[pos] == 'B') cb++;
			if(s[pos] == 'C') cc++;
		}
		std::cout << 2 << '\n';
		std::cout << pos + 2 << ' ' << 3 * n << ' ' << 'B' << '\n';
		while(cb < n) {
			cb++;
			pos++;
		}
		std::cout << pos + 2 << ' ' << 3 * n << ' ' << 'C' << '\n';
		return 0;
	}
	if(B > n) {
		LL pos = -1;
		while(cb < n) {
			pos++;
			if(s[pos] == 'A') ca++;
			if(s[pos] == 'B') cb++;
			if(s[pos] == 'C') cc++;
		}
		std::cout << 2 << '\n';
		std::cout << pos + 2 << ' ' << 3 * n << ' ' << 'A' << '\n';
		while(ca < n) {
			ca++;
			pos++;
		}
		std::cout << pos + 2 << ' ' << 3 * n << ' ' << 'C' << '\n';
		return 0;
	}
	if(C > n) {
		LL pos = -1;
		while(cc < n) {
			pos++;
			if(s[pos] == 'A') ca++;
			if(s[pos] == 'B') cb++;
			if(s[pos] == 'C') cc++;
		}
		std::cout << 2 << '\n';
		std::cout << pos + 2 << ' ' << 3 * n << ' ' << 'A' << '\n';
		while(ca < n) {
			ca++;
			pos++;
		}
		std::cout << pos + 2 << ' ' << 3 * n << ' ' << 'B' << '\n';
		return 0;
	}
	return 0;
}

比赛后

寄了，过了五道题，第六名

省赛只取前五个队

今年还不一定有机会去打星（公费旅游无了）

没能准备三台电脑真的吃大亏，哪怕另外两台只能看代码也很亏，手机根本没法看代码（正式赛只有一台电脑）

一直在四五六名徘徊，本来以为稳了的，结果有只队伍十五分钟连续 AC 三道题，只能说，他们太厉害了（各种意义上）

本来以为没机会了，队友太 C 了，一发过了 G，又有了曙光（再过一题就进前五）

挣扎了一个小时，以另一只队伍 AC 六道题结束，（我们罚时已经输了，AC第六题也进不了前五）

最后十分钟开摆烂了

今年怎么这么卷啊！！！

这不得拿五个省赛金牌回来，裂开

滚去复习期中了，五一假期没复习，还没进队，烂了。

训练量不够，没撞到原比赛，这套题是欧洲的一次ACM比赛，其他队有训练量超高的大佬练到过这套题

  1. 比赛前
  2. 比赛时
    1. A
    2. N
    3. J
    4. F
    5. G
    6. L
  3. 比赛后