CF1672E
有显然的 \(n \log n\) 次做法，对每种行数二分最短列数，但这样求出的信息太多了。
那么一个初步的想法是想办法淘汰掉不优的选择。
少二分几次，二分什么的信息量最大呢？把总长度二分出来即全部放在同一行，对于放 \(h\) 行，它能更新答案当且仅当 \(w_h \cdot h < S + n -1\)，其中 \(S\) 为总长度。这个限制很严，不能让 \(h\) 更大因为此时每个单次后面都会有一个空格，但又最少会放 \((S+n-h)/h\) 行，因此唯一一种方法是 \((S+n-1)/h\)，问 \(O(n)\) 次即可。
询问次数 \(\log n + n\)。
CF1354G
先找一块石头。因为 \(k \leq n/2\)，随机 \(25\) 次，将当前最大的物品和它比较，留下的东西不是石头的概率是 \((1/2)^{25}\)。
接着倍增跳前缀以找到第一个有礼物的区间。找到后在里面二分。总复杂度是 \(2 \log n - \log_2(C)\)，其中 \(C\) 是错误率。
HDU7393
把人分成 \(n/m\) 组，每组 \(m\) 人，想办法让每组有一个人猜对就行了。想办法让一组人猜一整个剩余系。设其他人的和为 \(S\)，第 \(i\) 个人猜 \(S+i\) 即可。\(S + a_i\) 的和为定值，每个人猜这个数 \(\bmod m\) 的值，一定恰一人是对的。
agc004F
图是树或基环树。
相邻点处理容易想到二分图，树就是二分图。
黑白染色，则同时变色等价于交换异色点位置。这顺带说明了黑白点个数必须相同。对于一条树边，若其子树内黑白点的差距为 \(t\)，则这条边必须至少被经过 \(|t|\)，答案下限为 \(\sum |t|\)。
接着是基环树。如果环是偶环，枚举断边，相当于
CF1450C2
经典题。
把图三染色，一定有一种方法的目标次数不超过 \(k/3\)。
TopCoder13366
不存在四元环。如果存在的话根据连边方式可以证矛盾。
环的期望数量是每两个点形成环的概率的和。算一下就行了。
AtCoder-codefestival_2016_final_g
Krustal 的过程中，边被排序，从小到大试图勾通两个连通块。
当考虑到 \((A, B+1, C+1)\) 时 \((A, B, C)\) 一定被考虑过，转而考虑 \((B, B+1, C+1)\) 是不劣的。
因此现在有两种边，一种边只有 \(O(m)\) 条，另一种边只出现在相邻两个点间，边权递增。
Krustal 时，若考虑到 \((A, A+1, C)\) 时已连通，可以放弃所有 \((A+i, A+i+1, C+i)\)，因为使 \((A, A+1, C)\) 连通的方案整体右移就可以得到不劣的 \(A+i \to A+i+1\) 的方案。
另一个方法是跑两圈 dp 更新相邻两条边的最小值。复杂度瓶颈并不在此。