Atcoder Grand 22 ABC 题解

算了 做出来一道A不亏了.jpg

A Diverse Word

如果N > 26,直接输出-1

如果N < 26,在后面加一个没有用过的最小的字母即可。

如果N = 26,从后往前扫,直到遇到第一个可以换的。这个直接看代码吧,注意特判zyxwvutsrqponmlkjihgfedcba 我才没有滚键盘!

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 <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define LL long long

set<char> vis;

int main() {
string s;
cin>>s;
if(s == "zyxwvutsrqponmlkjihgfedcba") return puts("-1"), 0;
else if(s.size() > 26) return puts("-1"), 0;
else if(s.size() < 26) {
for(int i = 0; i < s.size(); ++i) vis.insert(s[i]);
char i = 'a';
for(; i <= 'z'; ++i) if(!vis.count(i)) break;
cout<<s + i<<endl;
return 0;
}else {
char t; int j;
for(j = s.size() - 1; j >= 0; --j) {
vis.clear();
for(int i = 0; i < j; ++i) vis.insert(s[i]);
t = s[j] + 1;
for(; t <= 'z'; ++t) {
if(!vis.count(t)) goto label;
}
}
label: string ans(s, 0, j);
ans += t;
cout<<ans<<endl;
return 0;
}
}

B GCD Sequence

昨天构出来的玩意是2 3 25 30k…,不过只能过19个点。

构造题。首先题干中要求在3w中输出2w的范围,这就意味着我们必须把间隔控制在1/3左右,显然一组数字2、3、6就会自然而然的引发我们的遐想。那怎么搞呢?

考虑到$gcd(x_0, S - x_0) = gcd(x_0, S)$,我们就必须满足$S = 6k$。还要是2和3的倍数,所以就从$6k, 6k + 2, 6k + 3, 6k + 4$中选择。

接下来是怎么构造的问题。对于$n \leq 5$的情况,直接特判掉。对于N > 6的时候,我们按照上面的顺序从小到大构造。不过和有可能不是6的倍数,需要一些调整。考虑到我们的选择范围是$6k, 6k + 2, 6k + 3, 6k + 4$,所以有且只有以下几种情况:

  • $S \equiv 0\ (\mod 6)$,无需处理
  • $S \equiv 2\ (\mod 6)$,删一个8再入一个6的倍数
  • $S \equiv 3\ (\mod 6)$,删一个9再入一个6的倍数
  • $S \equiv 5\ (\mod 6)$,删一个9再入一个$6k+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
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

set<int> s;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
if(n == 3) return puts("2 3 25"), 0;
if(n == 4) return puts("2 3 25 30"), 0;
if(n == 5) return puts("2 3 25 30 60"), 0;
long long sum = 0; int k;
for(int i = 1; i <= n; ++i) {
if(i % 4 == 1) k = 6 * (i / 4) + 2, s.insert(k), sum += k;
else if(i % 4 == 2) k = 6 * (i / 4) + 3, s.insert(k), sum += k;
else if(i % 4 == 3) k = 6 * (i / 4) + 4, s.insert(k), sum += k;
else k = 6 * (i / 4), s.insert(k), sum += k;
}
if(sum % 6 == 2) {
s.erase(8);
s.insert(6 * (n / 4 + 1));
} else if(sum % 6 == 3) {
s.erase(9);
s.insert(6 * (n / 4 + 1));
} else if(sum % 6 == 5){
s.erase(9);
s.insert(6 * (n / 4) + 4);
}
for(set<int>::iterator sit = s.begin(); sit != s.end(); ++sit)
cout<<*sit<<" ";
return 0;
}

C Remainder Game

图论建模…太神了

首先考虑到$0 \leq a_i, b_i \leq 50$,那么每次取模的k一定不会超过50.否则,这个操作就是没有意义的。

再思考一下设问的意义。设问要求$\sum 2^k$,我们知道$2^{i} > \sum^{i-1}_{t = 0}2^t$,所以原问题等价于最小的字典序集合。

于是我们可以考虑建图。然后请看代码吧。真的神。

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
#include <bits/stdc++.h>

using namespace std;

int A[53], B[53], n;
bool graph[53][53][53], connected[53][53];

namespace Margatroid{
void AK() {
puts("");
}
}

namespace Kririae{
void AK(long long x) {
cout<<x;
}
}

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &A[i]);
for(int i = 1; i <= n; ++i) scanf("%d", &B[i]);
for(int i = 0; i <= 50; ++i) graph[0][i][i] = 1;
//graph预处理一张图,描述使用第k个质数前的情况
for(int k = 1; k <= 50; ++k) {
for(int i = 0; i <= 50; ++i)
for(int j = 0; j <= 50; ++j)
graph[k][i][j] = graph[k - 1][i % k][j] | graph[k - 1][i][j];
}
//建边,预处理。使用前转移到使用后。
for(int i = 1; i <= n; ++i) {
if(!graph[50][A[i]][B[i]])
return puts("-1"), 0;
}
//判断合法性,如果50个质数都用了还不可达说明不可达。
for(int i = 1; i <= n; ++i) {
connected[i][A[i]] = 1;
}
//connected维护第i个节点能否到达数j
long long ans = 0;
for(int k = 50; k > 0; --k) {
bool flag = 0;
for(int i = 1; i <= n; ++i) {
bool is_connected = 0;
for(int j = 0; j <= 50; ++j)
is_connected |= connected[i][j] && graph[k - 1][j][B[i]];
if(!is_connected) {flag = 1; break;}
}
//Floyd.如果该质数使用之前存在点j到达B[i]并且与i联通,就表明一定能找到更小的质数。否则,就说明这个质数是必要的。
if(flag) {
ans += 1LL << k;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= 50; ++j)
connected[i][j % k] |= connected[i][j];
}
//更新得到的connected数组
}
}
Kririae::AK(ans);
Margatroid::AK();
}
Share