CF补题(9.8-9.13)

CF1405C Balanced Bitstring

首先能发现一个显然的性质(s[i] = s[i+k])，这样我们就能确定一些能确定的数字，再检查 $\max{(n_0,n_1)} \le \frac{k}{2}$ 是否满足就好了

CF1391C Cyclic Permutations

首先这题一看就知道是那种组合数学题。。。然后想了想发现不会做。。。只能先小范围暴力建图，再用并查集判断是否存在环。。。再到OEIS上找找就好了。。。最后可以发现答案是 $n! - 2^{n-1}$

CF1407C Chocolate Bunny

注意到一个性质： $a\mod{b} > b\mod{a}$ 与 $a<b$ 是充要条件，于是对于任意两个位置 $a,b$ ，询问 $（a,b)$ 和 $(b,a)$ 就好了，进而可以确定较小的值及其所在的位置

CF1401D Maximum Distributed Tree

显然是看边的贡献，而且这个边的贡献非常显然，DFS一次，定义 $siz[x]$ 为x的子树的节点数目，显然对于一个边的贡献就是 $(n-siz[x])siz[x]$ ，接下来就直接排序就好了，同时还要注意判断n和m之间的大小关系，原则上都是大的与大的相乘，但是如果n更大，显然后面有一部分都是1，但是m更大的话，就把前m-n+1个值相乘凑成n个，显然这样相乘更大。

CF1405D Tree Tag

这题首先先看几种显然的情况：

$dist(a,b) \le a$ ，这种情况下Alice可以直接一步找到Bob，Alice胜
$tree \space diameter \le 2a$ ，这种情况下Alice可以直接先走到中心，这样不管Bob往哪里走Alice都可以一步到达
$2da < db$ ，考虑极限情况，Alice仅和Bob相差da了，倘若 $db \le 2da$ ，Bob跳完后，不管怎样Alice都能追上。
$db \le 2da$ ，此时Alice胜。

至于求 $dist(a,b)$ 和树的直径这两个东西，显然两次dfs就够了

CF1399E1 Weights Division (easy version)

首先一个看起来很对的做法是直接把每条边在 $\sum_{v\in leaves}w(root,v)$ 中的贡献(也就是叶子到根经过这条边的次数乘以这条边的边权)放到堆里，同时在求贡献的DFS里顺带统计一下要求的式子，然后动态维护一下堆，每次取最大边/2直到小于S就好了。

但是我们容易忽略的是边/2这个条件是向下取整的，这样就导致直接对贡献除2造成了很多的误差，于是我们只能重载一下运算符，记录每条边当前的权值和经过的次数，然后考虑最大化每条边权除2后的差值，也就是最大化 $(e.w-\lfloor \frac{e.w}{2}\rfloor)\times e.t$ 这个值，按上面那个方法维护直到整个值小于S就好了

CF1407D Discrete Centrifugal Jumps

对于：

\begin{array}{l}\max \left(h_{i+1}, \ldots, h_{j-1}\right)<\min \left(h_{i}, h_{j}\right) \\\max \left(h_{i}, h_{j}\right)<\min \left(h_{i+1}, \ldots, h_{j-1}\right)\end{array}

这样的式子我们可以用一个单增和一个单减的单调栈去维护，然后就是一个简单的单调栈优化DP了。。。

init0xyz的自留地