ABC 398，A ~ F。
A. Doors in the Center
分奇偶模拟。
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>
#define int long long
using namespace std;
void solve(){
int n; cin >> n;
if(n & 1){
string s(n, '-');
s[n >> 1] = '=';
cout << s << '\n';
}
else{
string s(n, '-');
s[n / 2] = s[n / 2 - 1] = '=';
cout << s << '\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
B. Full House 3
题意：找三带二。
将计次降序排序，第一项大于等于 3，第二项大于等于 2，即满足，否则不满足。
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>
#define int long long
using namespace std;
void solve(){
vector<int>a(13);
for(int i = 0; i < 7; i++){
int x; cin >> x;
a[x - 1] ++;
}
sort(a.begin(), a.end(), greater());
if(a[0] >= 3 && a[1] >= 2){
cout << "Yes" << '\n';
}
else{
cout << "No" << '\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
C. Uniqueness
题意：找出最大的只出现过一次的数。模拟即可。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
int n; cin >> n;
vector<int>a(n);
for(auto &i : a) cin >> i;
map<int, int>mp;
for(auto &i : a) mp[i] ++;
int maxx = -1, lable = -1;
for(int i = 0; i < n; i++){
if(mp[a[i]] == 1 && a[i] > maxx){
maxx = a[i];
lable = i + 1;
}
}
cout << lable << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
D. Bonfire
维护 smoke 所在的位置不方便，考虑相对运动，每次吹风的时候，将产生的效果等效为：人朝反方向运动一格，campfire 也运动一格，同时在新位置产生一格 smoke。
这样直接模拟，人站在有烟的位置上时，答案为 1，否则为 0。
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>
#define int long long
using namespace std;
void solve(){
int n, r, c; cin >> n >> r >> c;
r = -r, c = -c;
string s; cin >> s;
string res;
map<int, map<int, int>>mp;
mp[0][0] = 1;
int x = 0, y = 0;
for(int i = 0; i < n; i++){
if(s[i] == 'N') r--, mp[x][--y] = 1;
if(s[i] == 'S') r++, mp[x][++y] = 1;
if(s[i] == 'W') c--, mp[--x][y] = 1;
if(s[i] == 'E') c++, mp[++x][y] = 1;
res += mp[c][r] + '0';
}
cout << res << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
E. Tree Game
事实上，不难发现，我们能够加的边是有限的：即所有 (i, j) 对，使得 dist[i, j] 为奇数，且不相邻。
因此，如果能够加上的边有奇数个，我们就选 First，否则，选择 Second，这样一定是必胜的。
利用二分图染色找出所有满足条件的 (i, j) 对：记二分图的两个集合为 A 和 B，那么满足条件的 (i, j) 对一定位于不同集合中（路径长为奇数），又不相邻，容易得到，符合条件的总数为 cntA * cntB - (n - 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
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
| #include<bits/stdc++.h>
using namespace std;
void solve(){
int n; cin >> n;
vector<vector<int>> adj(n);
vector g(n, vector<bool>(n));
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
g[u][v] = g[v][u] = true;
}
vector<int> f(n, -1);
queue<int> q;
f[0] = 0;
q.push(0);
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto y : adj[x]) {
if (f[y] == -1) {
f[y] = f[x] ^ 1;
q.push(y);
}
}
}
int cnt1 = accumulate(f.begin(), f.end(), 0);
int cnt0 = n - cnt1;
int cur = 0;
if ((cnt0 * cnt1 - (n - 1)) % 2 == 0) {
cout << "Second" << endl;
cur = 1;
} else {
cout << "First" << endl;
cur = 0;
}
int x = 1, y = 0;
while (true) {
if (cur == 0) {
while (g[x][y] || f[x] == f[y]) {
y++;
if (y == x) {
x++;
y = 0;
}
}
g[x][y] = g[y][x] = true;
cout << y + 1 << " " << x + 1 << endl;
} else {
int u, v;
cin >> u >> v;
if (u == -1) {
break;
}
u--;
v--;
g[u][v] = g[v][u] = true;
}
cur ^= 1;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|
F. ABCBA
Manacher 算法处理以每个位置为中心的最长回文串半径，找出最长回文后缀，扩充原串。
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
| #include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> manacher(string s) {
string t = "#";
for (auto c : s) {
t += c;
t += '#';
}
int n = t.size();
vector<int> r(n);
for (int i = 0, j = 0; i < n; i++) {
if (2 * j - i >= 0 && j + r[j] > i) {
r[i] = min(r[2 * j - i], j + r[j] - i);
}
while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
r[i] += 1;
}
if (i + r[i] > j + r[j]) {
j = i;
}
}
return r;
}
void solve(){
string s; cin >> s;
int n = s.size();
auto r = manacher(s);
int l = 0;
while(r[l + n] < n - l + 1){
l++;
}
for(int i = 0; i < l; i++){
s += s[l - 1 - i];
}
cout << s << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
|