ABC422题解A-F

省流：20:50~22:00 短时场

A

暴力模拟即可

B

每个点暴力判断即可，写挂了 1 次

C

没脑子写二分，有脑子猜结论，上界显然是$\min\{n_{a},n_{b}\}$，下界不太好，因为下界和这个能够分配的数量有关，设数量为$x$，那么显然答案必定为$n_{a}-x+n_{b}+n_{c}-x\ge x$，那么显然$n_{a}+n_{b}+n_{c}-2x\ge x$。显然有$x\ge \dfrac{n_{A}+n_{B}+n_{C}}{3}$。上下界有了知道咋做了吧。

D

你猜为什么给你$2^n$？

你倒着操作，每次操作肯定是$\dfrac{2^n}{2}=2^{n-1}$ 啊，这些部分相当于子问题分治的结构，再翻译一下就是完全二叉树的结构，根节点点权为$k$，你要在遍历每一层的时候通过合理均分当前点点权到两个孩子，使得分配到两个孩子的权值之间差值最小，什么时候最小？直接除二平均分不就做完了，时间复杂度$O(n)$。因为我是唐我写了个$O(n 2^n)$ 判断不平衡度。

E

要求$> \lfloor \dfrac{n}{2} \rfloor$？而且题目没说无解？

直接随机化，每次取 2 个点求直线即可，时间复杂度$O(\text{能过})$。

F

Dijkstra 能解决的好吧，但是论文级别。动态权这玩意除非你学过论文级别的东西否则这玩意是没法做的。

注意到时间复杂度是宽裕的$O(nm)$，同时注意到我们可以通过拆分法将路径点权贡献拆分到每个点上，这些点的贡献只和当前路径长度有关。也就是说我们可以考虑 DP 求解，设$f(i,j)$ 表示目前到$i$ 点路径长度为$j$ 的最小花费，枚举每一个点和路径长度求解即可，时间复杂度$O(n^2+nm)$。

其实有更好的性质就是每一个点不会经过两次，所以这个图必定是一个 DAG，DAG上 DP 即可，时间复杂度$O(n+m)$。