因为疫情推迟返校，在家上网课。
在家的话，自律非常重要，开启自律模式
周四
F. Subsequences of Length Two（dp）
一开始想的是贪心，然后发现不太对。
突然醒悟到dp，显然状态和前i个，用了多少此有关
当前是t[1]的话，还和前面有多少个t[0]有关
于是把有多少个t[0]也加入状态
最后就是一个n^3的dp
一开始给200的数据量，就提示时间复杂度了，做了那么多题，一般没有不拉满的
注意特判一下t的两个字母一样的情况
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 200 + 10;
int dp[N][N][N], n, k, ans;
string s, T;int main()
{cin >> n >> k >> s >> T;s = " " + s;if(T[0] == T[1]){int cnt = 0, len = s.size();_for(i, 1, len) cnt += (s[i] == T[0]);cnt = min(cnt + k, n);printf("%d\n", cnt * (cnt - 1) / 2);return 0;}memset(dp, -0x3f, sizeof dp);dp[0][0][0] = 0;_for(i, 1, n)_for(j, 0, k)_for(t, 0, i){if(s[i] == T[0]){if(t > 0) dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j][t - 1]);if(j > 0) dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t] + t);}else if(s[i] == T[1]){dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j][t] + t);if(j > 0 && t > 0) dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t - 1]);}else{dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j][t]);if(j > 0) dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t] + t);if(j > 0 && t > 0) dp[i][j][t] = max(dp[i][j][t], dp[i - 1][j - 1][t - 1]);}ans = max(ans, dp[i][j][t]);}printf("%d\n", ans);return 0;
}
周五
keep going 不要停止提升自己
B. Present（异或）
这道题自己想没什么思路，只知道每一位拆开来考虑，然后看最后这一位的奇偶，只能想到这
其实比较靠近了，正解是直接考虑答案的某一位是否为1
比如当前看第k位，那么显然要考虑哪些数对加起来第k位有1，要统计这个个数。
如果两个数加起来第k位有1，那么起码是大于2^k的 但是上限很大，而且大于也不一定这一位为1
那么我们加一个限制条件，每一个数模2 ^ (k + 1) 这样子第一不会影响答案，更高位不影响低位，第二限制了上限
这样处理了之后，两个数加起来第k位有1的话，可以写出取值的区间。
所以枚举每一个数，看谁和它加起来在这个区间里面，这个可以用二分来求，因为要二分所以要先排序。最后要注意去掉自己和自己，以及重复统计。
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 4e5 + 10;
int a[N], b[N], n, ans;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);_for(k, 0, 25){_for(i, 1, n) b[i] = a[i] % (1 << (k + 1));int cnt = 0;sort(b + 1, b + n + 1);_for(i, 1, n){int l = lower_bound(b + 1, b + n + 1, (1 << k) - b[i]) - b;int r = upper_bound(b + 1, b + n + 1, (1 << (k + 1)) - 1 - b[i]) - b - 1;cnt += r - l + 1;l = lower_bound(b + 1, b + n + 1, (1 << (k + 1)) + (1 << k) - b[i]) - b;r = upper_bound(b + 1, b + n + 1, (1 << (k + 2)) - 2 - b[i]) - b - 1;cnt += r - l + 1;if((b[i] + b[i]) & (1 << k)) cnt--;}if((cnt / 2) & 1) ans += 1 << k;}printf("%d\n", ans);return 0;
}
D. Segment Tree（set+暴力优化）
核心思想是暴力建边，但边数小于等于n - 1的，所以可以保证复杂度。
那么怎么优化呢，先排序，对于当前区间，要看前面区间有多少个右端点在当前区间的
我自己想的时候想到了暴力遍历，树状数组统计个数，但应该用set存右端点二分来找。
提前预处理一下每个右端点对应的标号。用并查集维护一下成不成环。
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 5e5 + 10;
pair<int, int> a[N];
unordered_map<int, int> mp;
int f[N], n, cnt;
set<int> s;int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void Union(int x, int y) { f[find(x)] = find(y); }int main()
{scanf("%d", &n);_for(i, 1, n){int l, r;scanf("%d%d", &l, &r);a[i] = {l, r};}sort(a + 1, a + n + 1);_for(i, 1, n) mp[a[i].second] = i, f[i] = i;s.insert(a[1].second);_for(i, 2, n){auto itl = s.lower_bound(a[i].first);auto itr = s.lower_bound(a[i].second);for(auto it = itl; it != itr; it++){if(++cnt >= n || find(i) == find(mp[*it])){puts("NO");return 0;}Union(i, mp[*it]);}s.insert(a[i].second);}puts(cnt == n - 1 ? "YES" : "NO");return 0;
}
E. Soldier and Traveling（最大流+输出方案）
最大流题的数据范围只有几百，而且这道题很明显一个士兵看作一股流，也就是最大流问题。
分两个部分，建图和输出方案
建图的话，一个点拆成两个点，源点给入点ai的流量，出点给汇点bi的流量。
然后，有连边以及自己对自己就入点向出点连容量为无限的边。
满流了就符合条件，输出的时候遍历每一条边。
记住有正向边和反向边，因为正向边流了多少，反向边就加多少，所以遍历反向边就可以知道流了多少。
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int N = 210;
struct Edge { int from, to, flow; };
vector<Edge> edge;
vector<int> g[N];
int d[N], cur[N], ans[N][N];
int a[N], b[N], n, m, s, t, suma, sumb;void add(int from, int to, int flow)
{edge.push_back(Edge{from, to, flow});g[from].push_back(edge.size() - 1);edge.push_back(Edge{to, from, 0});g[to].push_back(edge.size() - 1);
}bool bfs()
{memset(d, 0, sizeof(d));queue<int> q;q.push(s);d[s] = 1;while(!q.empty()){int u = q.front(); q.pop();for(auto x: g[u]){Edge e = edge[x];if(!d[e.to] && e.flow){d[e.to] = d[u] + 1;q.push(e.to);}}}return d[t];
}ll dfs(int u, ll in)
{if(u == t) return in;ll out = 0;for(int& i = cur[u]; i < g[u].size(); i++){Edge& e = edge[g[u][i]];if(d[u] + 1 == d[e.to] && e.flow){ll f = dfs(e.to, min((ll)e.flow, in));e.flow -= f;edge[g[u][i] ^ 1].flow += f;out += f; in -= f;if(in == 0) break;}}return out;
}void build()
{scanf("%d%d", &n, &m);s = 0; t = 201;_for(i, 1, n) scanf("%d", &a[i]), add(s, i, a[i]), add(i, i + n, 1e9), suma += a[i];_for(i, 1, n) scanf("%d", &b[i]), add(i + n, t, b[i]), sumb += b[i];while(m--){int u, v;scanf("%d%d", &u, &v);add(u, v + n, 1e9);add(v, u + n, 1e9);}
}int main()
{build();ll maxflow = 0;while(bfs()){memset(cur, 0, sizeof(cur));maxflow += dfs(s, 1e18);}if(suma != sumb || suma != maxflow){puts("NO");return 0;}puts("YES");for(auto e: edge)if(e.to < e.from && e.from > n)ans[e.to][e.from - n] = e.flow;_for(i, 1, n){_for(j, 1, n)printf("%d ", ans[i][j]);puts("");}return 0;
}
周六
B. Destroying Roads（最短路+分类讨论）
这道题受之前一道题的起发，之前那道题是暴力枚举相交点。
这题类似，暴力枚举路径重叠的部分。
注意重叠的时候是有方向性的，也是有两种情况，我开始WA了一发。
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int N = 3000 + 10;
int s1, t1, s2, t2, l1, l2, n, m;
vector<int> g[N];
int dis[N][N];void bfs(int s, int d[])
{_for(i, 1, n) d[i] = 1e9;d[s] = 0;queue<int> q;q.push(s);while(!q.empty()){int u = q.front(); q.pop();for(int v: g[u])if(d[u] + 1 < d[v]){d[v] = d[u] + 1;q.push(v);}}
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, m){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);_for(i, 1, n) bfs(i, dis[i]);int ans = -1;if(dis[s1][t1] <= l1 && dis[s2][t2] <= l2) ans = max(ans, m - dis[s1][t1] - dis[s2][t2]);_for(i, 1, n)_for(j, 1, n)if(dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)ans = max(ans, m - (dis[s1][i] + dis[i][j] + dis[j][t1] + dis[s2][i] + dis[j][t2]));swap(s1, t1);_for(i, 1, n)_for(j, 1, n)if(dis[s1][i] + dis[i][j] + dis[j][t1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][t2] <= l2)ans = max(ans, m - (dis[s1][i] + dis[i][j] + dis[j][t1] + dis[s2][i] + dis[j][t2]));printf("%d\n", ans);return 0;
}
Golf Bot（FFT）
FFT就是多项式乘积优化成nlogn
这类题一般是构造多项式相乘
这道题就是给两个序列a，b
求b序列中有多少个数可以表示为a序列中的一个数，或者两个数之和（可以相同）
可以构造两个一样的多项式，a序列有相应的数的项的系数为1，否则为0
因为还有1个数的情况，所以看作a中有一个0。
这样用多项式乘法，就可以得出所有的和。
注意数据
此题代码可用作模板
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 8e5 + 10; //最高次数4倍
const double pi = acos(-1.0);struct Complex
{double x, y;
}a[N], b[N], c[N];
int ans[N], r[N], n, m, l, limit;Complex operator + (Complex a, Complex b) { return Complex{a.x + b.x, a.y + b.y}; }
Complex operator - (Complex a, Complex b) { return Complex{a.x - b.x, a.y - b.y}; }
Complex operator * (Complex a, Complex b) { return Complex{a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }void FFT(Complex *A, int type)
{rep(i, 0, limit)if(i < r[i])swap(A[i], A[r[i]]);for(int mid = 1; mid < limit; mid <<= 1){Complex Wn{cos(pi / mid), type * sin(pi / mid)};for(int R = mid << 1, j = 0; j < limit; j += R){Complex w{1, 0};for(int k = 0; k < mid; k++, w = w * Wn){Complex x = A[j + k], y = w * A[j + mid + k];A[j + k] = x + y;A[j + mid + k] = x - y;}}}
}void solve()
{for(limit = 1, l = 0; limit <= n + m; limit <<= 1, l++);rep(i, 0, limit) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));FFT(a, 1); FFT(b, 1);_for(i, 0, limit) c[i] = a[i] * b[i];FFT(c, -1);_for(i, 0, n + m) ans[i] = (int)(c[i].x / limit + 0.5);
}int main()
{while(~scanf("%d", &n)){memset(a, 0, sizeof a);memset(b, 0, sizeof b);a[0].x = b[0].x = 1;_for(i, 1, n){int x; scanf("%d", &x);a[x].x = b[x].x = 1;}m = n = 2e5;solve();int cnt = 0;scanf("%d", &m);while(m--){int x; scanf("%d", &x);cnt += (ans[x] > 0);}printf("%d\n", cnt);}return 0;
}
FFT模板
整理模板
/*
FFT模板 以此题为例
这道题就是给两个序列a，b求b序列中有多少个数可以表示为a序列中的一个数，或者两个数之和（可以同一个数）可以构造两个一样的多项式，a序列有相应的数的项的系数为1，否则为0因为还有1个数的情况，所以看作a中有一个0。这样用多项式乘法，就可以得出所有的和。*/#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 8e5 + 10; //答案多项式次数的两倍 也是limit的理论最大值
const double pi = acos(-1.0);struct Complex
{double x, y;
}a[N], b[N], c[N];
int ans[N], r[N], n, m, l, limit;Complex operator + (Complex a, Complex b) { return Complex{a.x + b.x, a.y + b.y}; }
Complex operator - (Complex a, Complex b) { return Complex{a.x - b.x, a.y - b.y}; }
Complex operator * (Complex a, Complex b) { return Complex{a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }void FFT(Complex *A, int type)
{rep(i, 0, limit)if(i < r[i])swap(A[i], A[r[i]]);for(int mid = 1; mid < limit; mid <<= 1){Complex Wn{cos(pi / mid), type * sin(pi / mid)};for(int R = mid << 1, j = 0; j < limit; j += R){Complex w{1, 0};for(int k = 0; k < mid; k++, w = w * Wn){Complex x = A[j + k], y = w * A[j + mid + k];A[j + k] = x + y;A[j + mid + k] = x - y;}}}
}void solve()
{for(limit = 1, l = 0; limit <= n + m; limit <<= 1, l++); //FFT只能处理2^t的多项式 limit表示最高次数 n + m即答案多项式次数rep(i, 0, limit) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));FFT(a, 1); FFT(b, 1); //FFT 系数表示法转化为点值表示法_for(i, 0, limit) c[i] = a[i] * b[i]; //点值表示法直接相乘FFT(c, -1); //逆FFT 点值表示法转化为系数表示法 最后要多除个limit（下一行）_for(i, 0, n + m) ans[i] = (int)(c[i].x / limit + 0.5);
}int main()
{while(~scanf("%d", &n)){memset(a, 0, sizeof a); //多组数据只用清空a b两个多项式的数组memset(b, 0, sizeof b);a[0].x = b[0].x = 1;_for(i, 1, n){int x; scanf("%d", &x);a[x].x = b[x].x = 1; //a[i].x表示x^i项的系数}m = n = 2e5; //n表示a多项式的次数 m是b多项式的次数solve();int cnt = 0;scanf("%d", &m);while(m--){int x; scanf("%d", &x);cnt += (ans[x] > 0);}printf("%d\n", cnt);}return 0;
}
周日
B. Connecting Universities（贪心）
这题秒啊
我只能想到配对时要尽可能两端的配对，然后就没什么想法了
其实直接想点的配对很难想，考虑配对方案很难想
换一种想法，考虑一条边对答案的贡献。
贪心来讲，一条边左边有x个大学，右边有y个大学，那么它的最大贡献显然是min(x, y)
每条边都这么贪心，就是正确答案，很妙。
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
int a[N], n, k;
vector<int> g[N];
ll ans;void dfs(int u, int fa)
{for(int v: g[u]){if(v == fa) continue;dfs(v, u);a[u] += a[v];ans += min(a[v], 2 * k - a[v]);}
}int main()
{scanf("%d%d", &n, &k);_for(i, 1, 2 * k){int x; scanf("%d", &x);a[x] = 1;}_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);printf("%lld\n", ans);return 0;
}