今天睡着了。发了只是为了完整性。
[CF1672E] notepad.exe
先二分得到总长度 \(\sum l_i+n-1\) 记为 \(w_1\)，然后考虑其它行数 \(h\)，最优的情况只能是每一行都用换行顶替一个空格，此时面积为 \(w_h\cdot h=w_1-h+1\)，所以 \(w_h=\left\lfloor w_1/h\right\rfloor\) 为唯一可能更新答案的取值。
[CF1354G] Find a Gift
\(k\leq n/2\implies\) 随机。
随机 \(25\) 个，找其中最大的，有高概率是一块石头。再看看 \(1\)，如果 \(1\) 是石头，那么可以倍增解决。
[QOJ7637] Exactly Three Neighbors
\(\leq 2/3\) 的一定有解：.##. 循环，可以多加几个白列。
\(>4/5\) 的一定无解：以下图案密铺平面。
#
#.#
#
就是想象中的平铺。
\(3/4\)：
##
#..#
##
\(4/7\)：
##
#..#
#..#
####
#..#
##
就是多个基本图形拼接。还有两个。
[HDU7393] Werewolves
思考过程：
- 考虑 \(n=m\) 的情况和原问题一样难。
- 由于期望正确率为 \(1/m\)，期望 \(1\) 个人对，所以至多只能有 \(1\) 个人对。
- 所以每个人猜对的事件是两两互斥的。每个人的决策在全局是两两互斥的。
结论：第 \(i\) 个人声称全场颜色总和 \(\equiv i\pmod m\) 即可。
[AGC004F] Namori
树：随机定根，对奇数深度的点颜色反转，操作变为交换一条边两端的颜色，对每条边统计一下可能的经过次数即可。可以统计每棵子树中黑点个数与白点个数的差 \(v_i\)，\(ans=\sum v_i\)。
偶环基环树：讨论每条环上的边对答案会增加什么，设有 \(x\) 的流量流过去。那么环上其它边的新流量都可以计算，子树不会变化。\(ans'=\sum|\lambda_iv_i+x|\)，求中位数即可。
奇环基环树：有一条不在二分图中的边，它的流量必是 \(v_{rt}/2\)。其它就不用管了。
[CF1450C2] Errich-Tac-Toe (Hard Version)
C1：按照 \((i+j)\bmod 3\) 分类，选一类全部翻转。
C2：按照 \((i+j)\bmod 3\) 分类，选一个 \(k\) 将 \(\equiv k\pmod 3\) 的 X 翻转，\(\equiv k+1\pmod 3\) 的 O 翻转。一共三种 \(k\)，总有一个 \(k\) 满足要求。
[Topcoder13366] Closest Rabbit
环只有二元环。那么枚举这个环及它形成的概率。连通块个数即为环的个数。
[CF1909H] Parallel Swaps Sort
看官方题解
- 缩小值域
- 特殊情况
[AtCoder-codefestival_2016_final_g] Zigzag MST
所有形如圆周角的边可以打到圆弧上，没有区别，这样只有一开始的边和环上的边有用。
[HDU6664] Andy and Maze
HDU #6664. Andy and Maze 题解--zhengjun - A_zjzj - 博客园 (cnblogs.com) 讲的好啊
[AGC006D] Median Pyramid Hard
缩小值域为 \(0/1\)。只需要轻微分讨即可。
[QOJ141] 8 染色
- 传四染色方案，Bob 自己做二分图染色
- 度数 \(\leq 7\) 的点不用管
[CF1372F] Omkar and Modes
若已知 \(a_i=v\) 且 \(v\) 出现了 \(k\) 次，那么两次操作即可确定 \(v\) 的出现位置：往左询问长度 \(k\) 的区间，往右询问长度 \(k\) 的区间，总有一侧是众数。
后面看不懂
[CF1887E] Good Colorings
行向列连边，出现一个基环树，有个环，可以逐渐折半拆开这个环，直到环长为 \(4\) 就找到了解。
[AGC044D] Guess the Password
可以求出每个字符的出现次数。考虑怎么合并，因为都是子序列，而编辑距离可以判断是否是子序列。于是直接做归并排序。按照哈夫曼树顺序合并。
[清华集训2014] 文学
？
[HDU6804] Contest of Rope Pulling
random_shuffle 后值域变成原来的根号。背包。
[CF1896G] Pepe Racing
。
[AGC019F] Yes or No
都不会
标签：题选,环上,leq,2024.8,##,非传统,#..#,基环树,equiv From： https://www.cnblogs.com/caijianhong/p/18343894