好久没打cf了，因为疫情困宿舍没事干，老年选手出来活动下筋骨。只写了ABC，困了就睡了。也懒得复盘补题了。
先放题目
Codeforces Round #761 (Div. 2)
A
题目大意
给俩字符串S，T，其中T为字符串"abc"的排列。求S的排列S'，使得T不是S'的字串且S'字典序最小。
思路
- 如果
S中包含了a，b，c三个字母，且T =="abc"，将S排序后交换b和c的位置，即为答案S'。
- 否则则
S'就是S的最小字典序。将S排序输出即可。
代码
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>
using namespace std;
int main() {
int n;
scanf("%d", &n);
while(n--) {
string s, t;
cin>>s>>t;
int lens = s.length();
sort(s.begin(), s.end());
if(t == "abc") {
int bBegin = lower_bound(s.begin(), s.end(), 'b') - s.begin();
int cEnd = upper_bound(s.begin(), s.end(), 'c') - s.begin() - 1;
if(bBegin < lens - 1 && s[cEnd] == 'c' && bBegin > 0) {
while(bBegin < cEnd) {
if(s[bBegin] == s[cEnd]) {
break;
}
swap(s[bBegin], s[cEnd]);
bBegin++;
cEnd--;
}
}
}
cout<<s<<"\n";
}
}
|
B
题目大意
给定一个数n，求三个数a，b，c，使得$a+b+c=n$，且 $gcd(a,b)=c$， 且$a \neq b \neq c$。
思路
- 直接暴力令$c=1$
- 如果
n为偶数，$a=n/2 , b=n/2 + 1 , c=1$
- 如果
n为奇数，
- 如果 $n/2$ 为偶数，$a=n/2 - 1 , b=n/2 + 1, c=1$
- 如果 $n/2$ 为奇数，$a=n/2 - 2 , b=n/2 + 2, c=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
| #include<bits/stdc++.h>
using namespace std;
inline int gcd(int a, int b) {
return b > 0 ? gcd(b, a%b) : a;
}
int main() {
int n;
cin>>n;
while(n--) {
int number;
cin >> number;
if(number % 2 == 1) {
int gap = 1;
while(gcd(number/2-gap, number/2+gap) != 1) {
gap++;
}
cout<<number/2-gap<<" "<<number/2+gap<<" "<<1<<endl;
}
else {
cout<<number/2 - 1<<" "<<number/2<<" "<<1<<endl;
}
}
}
|
C
题目大意
给定一个n，以及一个长度为n的数组。每次操作，选择其中一个数字a，以及任取一个正整数x，让$a = a % x$。问能不能将数组通过若干次操作后变成1 ~ n的一个排列，如果不能，输出-1，能的话输出最少操作次数。
思路
注意到，一个数模另一个小于它的数，肯定是变小的，a → a % x。并且$2 * (a \% x) \leq a$。
首先为了最优性，那些刚好能填补1 ~ n的位置的数，先填补上，这部分肯定是不变的。
我们贪心，从小到大，查找空缺的位置，如果存在空缺k，则需要在剩下的数中取大于2k的一个数a，通过操作后，填补k的位置。为了最优，肯定是取最小的，且没有被使用过的数。
可以通过优先队列来维护每次最小值。遇到一个空缺位置k，如果当前最小值 < 2k，则无解，否则将这个数使用来填补k。
代码
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 <bits/stdc++.h>
using namespace std;
int a[100003], vis[100003];
int main() {
int t;
cin>>t;
while (t--) {
int n;
cin>>n;
memset(vis, 0, sizeof(vis));
priority_queue<int, vector<int>, greater<int> > que;
for(int i = 0; i < n; i++) {
cin>>a[i];
if (a[i] <= n && a[i] >= 1) {
if (++vis[a[i]] > 1) {
que.push(a[i]);
}
}
else {
que.push(a[i]);
}
}
int ans = 0;
for(int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
if (que.top() <= 2 * i) {
ans = -1;
break;
}
que.pop();
++ans;
}
printf("%d\n", ans);
}
return 0;
}
|