10.14-10.20 总结

联考题解：https://www.cnblogs.com/british-union/p/liankao.html

如果忽略挂分，这周打的还可以。但是问题是挂了不少分导致实际得分远不如期望得分。

做题：

做了几道 Project Euler，有一道没想出来：588，638，457，307。

P10353：群论题

AGC012F 尝试枚举一下前几个的限制，发现限制就是在 \([i,2n-i]\) 范围内；同时不能有一个 \(b_j\) 夹在 \(b_i,b_{i+1}\) 中间。证明应该容易。最终直接 dp 即可。

P6773 先列出 dp 式子（由于支配性），然后线段树合并优化 dp（被尼特评为板子题）

P5419 这个题面结论就是答案。所以我进行分组，一组是一个完美匹配，边权相等即可。

CF1738G dilworth 的构造题目。

考虑强定的点开始的最长链 \(f_u\)。那么 \(f_u\) 相等的位置必然在一条反链上。根据这一点构造。

我构造 \(k-1\) 条从 \((n,i)\) 走到 \((1,n-i+1)\) 的路线并使其不相交，第 \(i\) 条经过 \(f=k-i\) 的点。就完成了任务。每条反链的策略是能向上走就向上走。正确性未知。

CF643F 我知道的：每头熊有没有在哪天睡觉或者没睡觉。

重量级结论：信息量可以达到上界，即信息数 = 辨认酒桶数。

神秘构造：把第 \(k\) 个方案对应 \(k\) 个是酒。每头熊的方案是没睡觉就不喝 \(k\) 桶，否则在睡觉的那天喝 \(k\) 桶，前面不喝。

CF1699E 我以为是什么赵行知，然后是 dp。扫描限制的 \(\min\)，设 \(f_i\) 为在当前限制下 \(i\) 分解的最大值的最小值。减小 \(\min\) 的时候只有 min 的倍数得到更新，转移是 \(f_{i\times \min}=\min_j f_{ij\times min}\)

CF1016G 相当于是 \(x_i\) 在每个质数分解必须靠着 \(X\) 或者 \(y_i\) 靠着 \(Y\)（除非 \(x_i=y_i\)）。这就是一个或卷积。

CF1446F（无代码）二分。然后结论：两个点连成线段和圆有交（判掉特殊情况），当两点到圆切线两端的弧相交。

然后处理一下（即越过分割点的把他取反，这样不影响答案）即可。