日记 2023.11.10：2023 syzx 秋季训练 6
*HI
A
拆位，带权并查集 / 二分图判定。
B
按位做差，于是只需要一次 bfs。
bonus：长度 \(\leq 5000\)（单次）或 \(\leq 20\)（多次）
https://codeforces.com/problemset/problem/1852/C？不是同一题。
C
分类讨论。钦定 \(A\leq B\)。
必然有一维，满足两个端点的差 \(\geq A+B\)。那么另一维要么是直接包含，要么有交集，要么分离。然后等差数列求和。
另一种做法，两个东西相交，考虑两维的投影，是 \([0,n]\) 中的两条长为 \(A,B\) 的线段有交，这个东西的方案数的平方。想要求出线段有交的方案数，只需要改成分离之后疯狂分段。
D
分治构造。
改成没有奇环。分治之后，左右两边二分图连边，然后递归下去，同一层同一颜色，这样相同颜色就都是二分图，没有奇环的存在。
__builtin_ctz(u xor v)
E
结论：拥有偶数条边的连通图，线图的最大权匹配是所有边的和。
奇数条边的情况，就是要拆一条边。如果拆这条边之后图连通，那么可以拆；如果拆了之后两个连通块都有偶数条边，也可以拆；否则拆了不好。
F
容斥。有多少完美匹配不包含树边呢？那就钦定有 \(i\) 条树边选上，假设钦定 \(i\) 条树边的方案数是 \(f_i\)（注意不能有公共点），则答案是
\[\sum_{i=1}^n(-1)^if_ig_{2n-2i} \]\(g_i\) 表示 \(i\) 个点的完全图的完美匹配方案数，可以递推。\(f_i\) 可以树形背包。\(O(n^2)\)。
G
答案 \(\leq 200\) 是因为我们可以安排顺序使得最后一个人等待 100s 之后再出发。
二分答案，拆点网络流，将时间分层，还要拆入点和出点使得两个人不在同一个格子。
流量限制全为一，所以方案就是所有有过流量的边。
可以不用二分，每一次增流即可。
H（WIP）
跳 border。维护现在的答案串，每次加入一个字符之后暴跳 border 更新答案和 border。啊？删除的过程实际上是线性。
I
答案串形如 fffeeeeedddcccbaaaa。
考虑暴力这么暴力的，因为答案串第一位取到本质不同字符数，所以如果枚举答案串的每个字符对应是什么，从前往后最大化字符长度。
状压 DP。记录当前用掉的字符串，记录最终的字符串每个字符的出现次数，同时记录这样搞最少需要到那里（就是记录 \(y\)，已经填的最后一个字符最后出现是 \(y\)，要求 \(y\) 尽量小，下一次从 \(y+1\) 开始决策）。\(O(2^kk^2),k=20\)。
J（WIP）
egf
标签：二分,10,字符,2023.11,leq,syzx,答案,条边 From： https://www.cnblogs.com/caijianhong/p/17825161.html