CF 550 Div. 3
昨晚的Div. 3
自己开了一场
顺利A完前6题
第6题没有初始化调了好久
A
题目大意：
给你一个字符串，你可以随意打乱，如果它们是一段连续的字串输出 “YES”, 否则输出“NO”
题解：
排个序就行
Code block
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
| #include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int MOD = 1e9+7;
const int Maxn = 200005;
int n;
char s[1005];
int a[35];
int main()
{
cin >> n;
while(n--){
int f = 0;
cin >> s;
int len = strlen(s);
sort(s, s + len);
for(int i = 1; i < len; i++){
if(s[i] != s[i-1] + 1){
cout << "No" << endl;
f = 1;
break;
}
}
if(f == 0) cout << "Yes" << endl;
}
return 0;
}
|
B
题目大意：
删数字。你第一次可以随意删除一个偶数或者奇数，下一次删除不能和上一次一样，就是说如果
上一次是偶数，下一次是奇数。问最后知道删不了，剩下的数总和最小
题解：
奇偶数分开，各自排序。
Code block
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
| #include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
int n;
int a[1000005];
vector <int> V1, V2;
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
if(a[i] % 2 == 1) V1.push_back(a[i]);
else V2.push_back(a[i]);
}
sort(V1.begin(), V1.end());
sort(V2.begin(), V2.end());
ll ans = 0;
if(V1.size() > V2.size()){
int len = V1.size() - V2.size();
for(int i = 0; i < len - 1; i++){
ans += V1[i];
}
}
else{
int len = V2.size() - V1.size();
for(int i = 0; i < len - 1; i++){
ans += V2[i];
}
}
cout << ans << endl;
}
}
|
C
题目大意：
把一个数组分成两个数组，一个严格递增，一个严格递减。
题解：
判断一下里面每个重复的值有多少个。如果大于两个就不行。
Code block
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
| #include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
int n;
int a[200005];
int num[200005];
vector <int> V1, V2;
int main(){
int f = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
num[a[i]]++;
if(num[a[i]] > 2) {
f = 1;
}
if(num[a[i]] == 1){
V1.push_back(a[i]);
}
else V2.push_back(a[i]);
}
if(f) {
cout << "NO" << endl;
return 0;
}
sort(V1.begin(), V1.end());
sort(V2.rbegin(), V2.rend());
cout << "YES" << endl;
cout << V1.size() << endl;
for(int i = 0; i < V1.size(); i++){
cout << V1[i] << " ";
}
cout << endl;
cout << V2.size() << endl;
for(int i = 0; i < V2.size(); i++){
cout << V2[i] << " ";
}
cout << endl;
return 0;
}
|
D
题目大意：
给定一个数组。现在有两种操作，问最少的操作次数使得每个值一样大，输出操作过程
题解：
不难发现，每次操作都可以把一个数变成与其旁边一样的数。
求操作次数最小，只要求出现相同数的次数最多那个就行了。
Code block
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 <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
int n;
int a[200005];
int num[200005];
stack <int> s;
int Max, Maxnum;
int id;
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
num[a[i]]++;
if(num[a[i]] > Max){
Max = num[a[i]];
Maxnum = a[i];
id = i;
}
}
cout << n - Max << endl;
for(int i = id - 1; i >= 0; i--){
if(a[i] > Maxnum){
cout << 2 << " " << i+1 << " " << i+2 << endl;
}
if(a[i] < Maxnum){
cout << 1 << " " << i+1 << " " << i+2 << endl;
}
}
for(int i = id + 1; i < n; i++){
if(a[i] > Maxnum){
cout << 2 << " " << i+1 << " " << i << endl;
}
if(a[i] < Maxnum){
cout << 1 << " " << i+1 << " " << i << endl;
}
}
return 0;
}
|
E
题目大意：
求两个字符串中间的那个字符串
题解：
直接按照进制模拟的思想，先把两个字符串对应的编号相加，然后除以2，再转成字符串就行。
Code block
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
| #include <bits/stdc++.h>
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const int N = 2e5+5;
int k;
string s, t;
int a[N], b[N], c[N], d[N];
int main(){
cin >> k;
cin >> s >> t;
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
for(int i = 0; i < k; i++){
a[i] = s[i] - 'a';
b[i] = t[i] - 'a';
}
int ans = 0;
for(int i = 0; i < k; i++){
c[i] = (a[i] + b[i] + ans) % 26;
if(a[i] + b[i] + ans > 25){
ans = 1;
}
else ans = 0;
}
c[k] = ans;
ans = 0;
for(int i = k; i >= 0; i--){
d[i] = (c[i] + ans) / 2;
if((c[i] + ans) % 2 == 0){
ans = 0;
}
else ans = 26;
}
for(int i = k - 1 ; i >= 0; i--){
cout << char(d[i] + 'a');
}
}
|
F
题目大意：
一张简单的无向图，只有一个连通快。让你构造成有向图，要求最长路劲不能大于等于二。
题解：
判个奇环，二分图判定裸题
Code block
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 FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define alli(n) for(int i = 0; i < n; i++)
#define allj(n) for(int j = 0; j < n; j++)
#define allk(n) for(int k = 0; k < n; k++)
using namespace std;
const int N = 1e6+5;
int head[N], nxt[N], ver[N], cnt;
int n, m, x, y;
int v[N], a[N], b[N];
int f;
void add(int x, int y){
ver[++cnt] = y;
nxt[cnt] = head[x];
head[x] = cnt;
}
void dfs(int x, int c){
v[x] = c;
for(int i = head[x]; i; i = nxt[i]){
int y = ver[i];
if(v[y] == 0){
dfs(y, 3 - c);
}
else if(v[y] == c){
f = 1;
return ;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++){
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
a[i] = x;
b[i] = y;
}
for(int i = 1; i <= n; i++){
if(v[i] == 0) dfs(i, 1);
if(f == 1) {
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
for(int i = 0; i < m; i++){
if(v[a[i]] == 1 && v[b[i]] == 2) {
cout << 1;
}
else cout << 0;
}
return 0;
}
|
