前面放了几天假，这两天主要就是补了一下子前面比赛的题目。
首先是牛客蔚蓝杯最后一场的题目：
这一场是真的太可惜了，真的可惜，有两个题目都是直接想出来的，但是就是想的有的复杂。
Yet Another FFT Problem?
这个一开始直接推出来就是找ai + bj == ai2 + bj2就行了，被题目影响了没有直接去FFT了，然后2e7直接爆内存了。。。其实就是暴力就行了，因为鸽巢原理，最多不会超过2e7+1个，找到就退出就行了，当时SB了。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, inf = 0x3f3f3f3f, M = 1e7 + 5;
int A[N],B[N];
vector<pair<int,int>> a,b,ans;
int n,m,x;
int mp1[2*M], mp2[M];
int main() {
cin >> n >> m;
int fa = -1, fb = -1;
for(int i = 1; i <= n; i ++) {
cin >> x;
A[i] = x;
if(!mp1[x]) mp1[x] = i, a.push_back({x,i});
else if(fa == -1) fa = i;
}
for(int i = 1; i <= m; i ++) {
cin >> x;
B[i] = x;
if(!mp2[x]) mp2[x] = i, b.push_back({x,i});
else if(fb == -1) fb = i;
}
if(fa != -1 && fb != -1) {
cout << mp1[A[fa]] << " " << fa << " " << mp2[B[fb]] << " " << fb << endl;
}else {
for(int i = 0; i <= M; i ++) mp1[i]= 0;
int cnt = 1;
for(auto x : a) {
for(auto y : b) {
if(mp1[x.first + y.first]) {
cout << ans[mp1[x.first+y.first]-1].first << " " << x.second << " " << ans[mp1[x.first+y.first]-1].second << " " << y.second << endl;
return 0;
}
mp1[x.first + y.first] = cnt;
ans.push_back({x.second,y.second});
cnt ++;
}
}
cout << -1 << endl;
}
return 0;
}然后就是这个Shannon Switching Game?也是相当怎么搞，但是细节没有处理好，不应该只往一边涂色的。。。
#include <bits/stdc++.h>
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long int
#define ull unsigned long long int
using namespace std;
int e[105][105];
int vis[105];
int n, m, s, t;
void BFS() {
queue<int> q;
q.push(t);
while (q.size()) {
int now = q.front();
q.pop();
for (int i = 1; i <= n; i ++) {
if (vis[i] == t) continue;
if (vis[i] != t && e[now][i] >= 2) {
vis[i] = t;
q.push(i);
}
int cnt = 0;
for (int j = 1; j <= n; j ++) {
if (vis[j] == t && e[i][j]) {
cnt ++;
}
}
if (cnt >= 2) vis[i] = t, q.push(i);
}
}
}
void BFS2() {
queue<int> q;
q.push(s);
while (q.size()) {
int now = q.front();
q.pop();
for (int i = 1; i <= n; i ++) {
if (vis[i] != s && e[now][i] >= 2) {
vis[i] = s;
q.push(i);
}
}
}
}
void solve() {
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i ++) vis[i] = i;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++) e[i][j] = 0;
for (int i = 1; i <= m; i ++) {
int x, y;
cin >> x >> y;
e[x][y] ++;
e[y][x] ++;
}
BFS();
// for (int i = 1; i <= n; i ++) {
// cout << vis[i] << " ";
// }
if (vis[s] == t) {
cout << "Join Player" << endl;
} else {
BFS2();
for (int i = 1; i <= n; i ++) {
if (vis[i] == s) {
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (vis[i] == t && e[s][i]) {
cnt++;
}
}
if (cnt >= 2) {
cout << "Join Player" << endl;
return;
}
}
}
cout << "Cut Player" << endl;
}
}
int main(int argc, char const *argv[]) {
OST;
int T;
cin >> T;
while (T --) {
solve();
}
return 0;
}还有这个Reviewer Assignment网络流的板子题目，主要是建立边有点复杂，遇到的也少，就压根没有想到。最大流还有最小费用流都可以写。
然后把这个题目补了，顺便重新整理了一下最大流，还有费用流的模板。
然后就是Codeforces Round #816 (Div. 2)的补题：
E题真的巧妙，每一次改变之后跑一遍最短路，然后每次更新最短值，最后面更新K次就行了。
#include <bits/stdc++.h>
#define OST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long int
#define ull unsigned long long int
#define pair pair<ll,int>
using namespace std;
const int N = 1e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
struct node {
int y;
ll v;
};
vector<node> e[N];
vector<ll>dis(N, inf), dis2(N, inf);
void Dij() {
priority_queue<pair, vector<pair>, greater<pair>> q;
for (int i = 1; i <= n; i ++) q.push({dis[i], i});
while (q.size()) {
auto [v, now] = q.top();
q.pop();
for (auto x : e[now]) {
if (dis[x.y] > v + x.v) {
dis[x.y] = v + x.v;
q.push({dis[x.y], x.y});
}
}
}
}
void Fen(int l, int r, int L, int R) {
// cout << l << " " << r << " " << L << " " << R << endl;
if (l > r) return;
int mid = (l + r) / 2;
//找到传送一次到m最小的
int idx = -1;
ll maxn = inf;
for (int i = L; i <= R; i ++) {
ll tmp = dis[i] + 1ll * pow(i - mid, 2);
if (maxn > tmp) {
maxn = tmp;
idx = i;
}
}
dis2[mid] = maxn;
Fen(l, mid - 1, L, idx);
Fen(mid + 1, r, idx, R);
}
int main(int argc, char const *argv[]) {
OST;
cin >> n >> m >> k;
for (int i = 1; i <= m; i ++) {
int x, y, v;
cin >> x >> y >> v;
e[x].push_back({y, v});
e[y].push_back({x, v});
}
dis[1] = 0;
Dij();
// for (int i = 1; i <= n; i ++) cout << dis[i] << " ";
// cout << endl;
for (int i = 1; i <= k; i ++) {
for (int i = 1; i <= n; i ++) dis2[i] = inf;
Fen(1, n, 1, n);
for (int i = 1; i <= n; i ++) dis[i] = dis2[i];
Dij();
}
for (int i = 1; i <= n; i ++) cout << dis[i] << " ";
cout << endl;
return 0;
}然后就是这几天1700分的CF题目：
