不懂
04.21
最小生成树
考虑 krustal 最小生成树的过程，先把边排序，再做一个依次选边的过程。如果我们有了最后的排序结果，就可以轻易求出最小生成树的边权；如果没有的话，就应该想办法记录
先排序，如何限制每条边只能被贡献到一边呢？把反边记录下来，如果考虑到反边时
我在场上一直在想贪心或性质，或反悔贪心。不过似乎连通性不是什么很强的条件，
操作
先套路性取
场上在试图优化
先把问题转化为，把
另一个做法是认为操作很快就会有循环节，所以按
前一个做法似乎又是可想的，但是敢去写二分下一个不一致还是需要勇气啊。或许又不那么可想，毕竟过的人也没那么多。
04.22
P8386
有人笨笨的，想先枚举最左的那个匹配
但这是错误的，因为
所以还是来看看怎么判定吧。设
判定改 dp 最重要的是压缩，即把对答案贡献相同的放进同一个等价类内一起转移，转移时，维护判定用的信息，以及到达终点时区分不同类的信息（这道题不需要）。也可以看成，任意一个合法解顺着唯一的路径到达计数终点（有点自动机的感觉了）。
桂花树
晚点再写。
04.23
树
离场切最近的一次。
操作相当于删点，最后的树形态为留下点的虚树，因此找到最大同时存在于两棵树内的树即可。
做一个 dp，
记录一下最大权独立集的做法：
考虑基础的暴力，
前面
std::function<int(LL)> dfs = [&](LL st) {
if (st < lim && dp[st] != -1) return dp[st];
if ((st & res) == st) return 0;
int x = std::__lg(st);
LL r = st & (all ^ ban[x]);
int ans = std::max(dfs(st ^ (1ll << x)), dfs(r) + g[x]);
if (st < lim) dp[st] = ans;
return ans;
};CF1336E1 证明复杂度的方法也是这样。
场上想了半天最大权独立集用网络流怎么做，哈哈。
序列
https://www.luogu.com.cn/problem/AT_arc066_d
对于单点不保存修改，分类讨论强制不选和强制选就可以了。
那么设
区间问题考虑分治，想办法把
考虑跨越
真没怎么做过这样的题，区间对内部所有点做贡献。不过可以理解的，
有空再写，感觉没空。
04.24
图上的游戏
先拆贡献，把边的贡献拆到点上，发现是出度减入度，再乘一个可以自己挑选的系数。那么把点按出度减入度的绝对值排序，双方一定依次选最前面的。也可以发现确定数值的点的贡献一定为
dp，按
写不动了，理解了一下 hz 的代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 55, mod = 1e9 + 7, iv2 = (mod + 1) / 2;
int n, m, c[N];
void add(auto &x, auto y) {x = (x + y) % mod; }
struct node{
int ind, oud;
}a[N * N];
int tot;
int power(int x, int y) {
int ret = 1;
while (y) {
if (y & 1) ret = 1ll * ret * x % mod;
x = 1ll * x * x % mod, y >>= 1;
}
return ret;
}
int get_inv(int x) {return power(x, mod - 2); }
int fac[N], inv[N], C[N][N];
int p[N][N], f[2][N][N][N], g[2][N][N][N];
void init() {
fac[0] = inv[0] = 1;
for (int i=1; i<=m; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[m] = get_inv(fac[m]);
for (int i=m-1; i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
for (int i=0; i<=n; ++i) {
C[i][0] = 1;
for (int j=1; j<=i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
p[0][0] = 1;
for (int i=1; i<=n; ++i)
for (int j=0; j<=m; ++j)
for (int k=0; j+k<=m; ++k)
add(p[i][j + k], 1ll * p[i - 1][j] * inv[k]);
for (int i=0; i<=m; ++i)
for (int j=0; j<=m; ++j) a[++tot] = (node) {i, j};
sort(a + 1, a + tot + 1, [](node x, node y) {
return abs(x.ind - x.oud) > abs(y.ind - y.oud);
});
g[0][0][0][0] = 1;
for (int i=1; i<=tot; ++i) {
int l = (i & 1), r = (l ^ 1);
int mul = 1ll * inv[a[i].ind] * inv[a[i].oud] % mod;
for (int k=0; k<=n; ++k)
for (int in=0; in<=m; ++in)
for (int out=0; out<=m; ++out) {
if (!g[r][k][in][out]) continue;
for (int x=0,pw=1; k+x<=n&&in+x*a[i].ind<=m&&out+x*a[i].oud<=m; ++x,pw=1ll*pw*mul%mod) {
add(g[l][k + x][in + x * a[i].ind][out + x * a[i].oud], 1ll * pw * g[r][k][in][out] % mod * C[k + x][x]);
add(f[l][k + x][in + x * a[i].ind][out + x * a[i].oud], 1ll * pw * f[r][k][in][out] % mod * C[k + x][x]);
if (x & 1) {
int tmp = std::abs(a[i].ind - a[i].oud);
if ((k + x) % 2 == 0) tmp = mod - tmp;
add(f[l][k + x][in + x * a[i].ind][out + x * a[i].oud], 1ll * pw * g[r][k][in][out] % mod * C[k + x][x] % mod * tmp);
}
}
g[r][k][in][out] = f[r][k][in][out] = 0;
}
}
}
int main() {
cin >> n >> m;
for (int i=1; i<=n; ++i) cin >> c[i];
init();
for (int i=1,cnt=0; i<=n; ++i) {
cnt += c[i] == 2;
for (int j=1; j<=m; ++j) {
//printf("calc %d %d\n", i, j);
int ans = 0;
for (int in=0; in<=j; ++in)
for (int out=0; out<=j; ++out) {
add(ans, 1ll * f[tot & 1][cnt][in][out] * p[i - cnt][j - in] % mod * p[i - cnt][j - out]);
//printf("add in %d out %d f %d p %d * %d\n", in, out, f[tot & 1][cnt][in][out], p[i - cnt][j - in], p[i - cnt][j - out]);
}
ans = 1ll * ans * fac[j] % mod * fac[j] % mod;
cout << 1ll * ans * iv2 % mod << " ";
}
cout << "\n";
}
return 0;
}04.25
P11915
首先答案有单调性，可以二分也可以从高到低扫，一边扫一边排除不合法的
那么假设希望
要省掉一维，对
感觉得紫。
CF1774F2
考虑到操作
设
04.30
怎么感觉大家都什么都会。
这是第一题
从后往前倒推 sg 函数值，同行有障碍物是好做的，如果没有的话，注意到只能一直往一个方向走，且 sg 值不会超过
v3 f(n, v2(m, v1(3, -1)));
std::function<int(int, int, int)> dfs = [&](int u, int v, int op) {
if (u >= n || a[u][v]) return 100;
if (f[u][v][op] != -1) return f[u][v][op];
int p = (v - 1 + m) % m;
int s1 = op != 1 ? dfs(u, p, 0) : 100;
p = (v + 1) % m;
int s2 = op != 0 ? dfs(u, p, 1) : 100;
int s3 = dfs(u + 1, v, 2);
return f[u][v][op] = mex(s1, s2, s3);
};就是考虑到，当 op 确定后，相当于是一个确定的数跟另一个要去 dfs 的值求 mex，把这视为函数复合，则做做前后缀和就可以了。
确实不可以回头走，所以，当手动确定方向之后，就最多只能走一圈了。不能回头反而让问题变简单了啊，你怎么搞反了。
经验好像是要把式子展开看看，或者看看你是不是想复杂了。就像事实上是二元而不是三元。
#include <bits/stdc++.h>
int mex(int a, int b = 3, int c = 3) {
if (a != 0 && b != 0 && c != 0) return 0;
else if (a != 1 && b != 1 && c != 1) return 1;
else if (a != 2 && b != 2 && c != 2) return 2;
else return 3;
}
struct tp {
int a[4];
tp() { for (int i = 0; i < 4; i++) a[i] = i; }
tp operator + (const tp &t) const {
tp res;
for (int i = 0; i < 4; i++) res.a[i] = t.a[a[i]];
return res;
}
};
int main() {
#ifndef LOCAL
freopen("first.in", "r", stdin);
freopen("first.out", "w", stdout);
#endif
int n, m; scanf("%d %d", &n, &m);
std::vector<std::vector<int>> c(n, std::vector<int>(m + 1));
std::vector<std::pair<int, int>> p;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= m; j++) {
char t; scanf(" %c", &t);
if (t == '#') c[i][j] = 1;
else if (t == 'B') c[i][j] = 2;
}
}
std::vector<std::vector<int>> f(n + 1, std::vector<int>(m + 1));
f[n].assign(m + 1, 100);
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
std::vector<tp> a(m + 2), pl(m + 2), pr(m + 2), sl(m + 2), sr(m + 2);
for (int j = 1; j <= m; j++)
for (int k = 0; k < 4; k++)
if (c[i][j] == 1) a[j].a[k] = 3;
else a[j].a[k] = mex(f[i + 1][j], k);
for (int j = 1; j <= m; j++)
pl[j] = a[j] + pl[j - 1], pr[j] = pr[j - 1] + a[j];
for (int j = m; j >= 1; j--)
sl[j] = sl[j + 1] + a[j], sr[j] = a[j] + sr[j + 1];
for (int j = 1; j <= m; j++) {
if (c[i][j] == 1) f[i][j] = 3;
else
f[i][j] = mex(f[i + 1][j], (pl[j - 1] + sl[j + 1]).a[3], (sr[j + 1] + pr[j - 1]).a[3]);
if (c[i][j] == 2) ans ^= f[i][j];
}
}
puts(ans ? "Alice" : "Bob");
}loj2732
等价于求只保留
拆贡献。若
05.01
T1
我从下往上贪心做的。有一些奇怪的神秘维护划分树也过了呀。为什么别人那么能把自己不确定正确性的东西写出来呢。
T2
先把题意等价到，在
容易发现两维独立，求出来卷起来就好了。
那么怎么求从
枚举
当