Atcoder ABC 398
compaq
·
·
题解
D - Bonfire
思路：
坐标动，人和原点不动
记录偏移量dx和dy。此时原点即为（0 - dx, 0 - dy）,人的坐标为(r - dx, c - dy)。
可用map或set记录是否存在。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, r, c;
string s;
int main(){
cin >> n >> r >> c >> s;
int dx = 0, dy = 0; // 偏移
set< pair<int, int> >st;
st.insert({0, 0});
for(int i = 0; i < n; i++){
if(s[i] == 'N') dx--;
else if(s[i] == 'S') dx++;
else if(s[i] == 'W') dy--;
else dy++;
if(!st.count({-dx, -dy})) st.insert({-dx, -dy});
if(st.count({r - dx, c - dy})) cout << 1;
else cout << 0;
}
return 0;
}
E - Tree Game
一道交互图
如果任意两点的距离为奇数, 那么这两点之间就是偶数环.
记录偶数环的数量，如果奇数个，我方先手，否则对方先手。
输出一个消灭一个，直到输入$-1 \ -1$ 结束程序
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int d[N][N];
void floyd(){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <=n; j++){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main(){
memset(d, 0x3f, sizeof d);
cin >> n;
for(int i = 1; i <= n; i++) d[i][i] = 0;
for(int i = 1; i < n; i++){
int u,v;
cin >> u >> v;
d[u][v] = d[v][u] = 1;
}
floyd();
set<pair<int, int>> ans;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(d[i][j] > 1 && d[i][j] % 2) // 偶数环
ans.insert({i, j});
}
}
if(ans.size() % 2){ // 则 "我”先手
cout << "First" << endl;
auto x = *ans.begin();
cout << x.first << ' ' << x.second << endl;
ans.erase(ans.begin());
}
else cout << "Second" << endl;
int x, y;
while(1){
cin >> x >> y;
if(x == -1 && y == -1) break;
if(x > y) swap(x, y);
ans.erase({x, y}); // 存在则删除， 不存在则没有删除操作
auto x = *ans.begin();
cout << x.first << ' ' << x.second << endl;
ans.erase(ans.begin());
}
return 0;
}
```
[F - ABCBA](https://atcoder.jp/contests/abc398/tasks/abc398_f)
给你一个字符串s，需要输出一个最短的回文串，要求回文串以s为前缀.
若将s翻转后得到字符串t，将t接在s的后面，显然就是一个回文。
比如说`ABC` $\rightarrow$ `ABCCBA`，这是最短的以s为前缀的字符串。
但是形如`ABCCC`,翻转后拼接为`ABCCCCCCBA`,显然不是最短的，最短的为`ABCCCBA`,可以得出，需要求出最长的后缀回文。
寻找最长的后缀回文，可以用kmp，字符串哈希，马拉车等算法。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int B = 13;
const int mod = 1e9 + 7;
string s, r;
int ans, n;
long long h, t, p = 1;
int main(){
cin >> s;
r = s;
reverse(r.begin(), r.end());
n = r.size();
for(int i = 0; i < n; i++){
h = h + (r[i] - 'A' + 1) * p; h %= mod;
t = t * B + (r[i] - 'A' + 1); t %= mod;
p *= B; p %= mod;
if(h == t) ans = i + 1;
}
cout << s;
for(int i = ans; i < n; i++) cout << r[i];
return 0;
}
```