Day1

Prophesy_One · 2024-11-24 19:50:47 · 个人记录

T1 dict

不是这什么b玩意我一遍还写不对的，考虑将每个串排成合法的最小字典序即可。

T2 tree

感觉好好构造不如随机化。记使根的度数不为 1，记叶子个数为 lf，首先观察到答案下界为 \lceil \frac{lf}{2} \rceil，考虑对着下界构造。

考虑对于一个节点，它子树内还未匹配的叶子至少有一个会被上传到父节点，并记录来源；否则考虑消除还未匹配的叶子，注意不能消除同一来源的叶子，否则不合法。

最后还不能匹配的直接到根即可，可以发现这样的点不超过 1 个。

T3 match

arc087f。

首先转化题意为：找到一个排列 p，使 \sum dis(i,p_i) 最大。

考虑答案的上界，对于每条边左右两侧的两个连通块，记其大小分别为 s_1,s_2，那么这条边最多产生的贡献为 2 \min(s_1,s_2)，即子树内点都向外连。

考虑让重心作为根，定义一个点合法当且仅当 (i,p_i) 不在根下同一子树内。问题转换为有多少个排列 p，能使所有点都合法。对于这个问题，我们套路的考虑容斥，令 f_i 表示子树内至少有 i 个点不合法的方案数，那么对于一个大小为 x 的子树有 f_i=(C_x^i)^2 i!，背包合并得到整个树的 f，最后容斥计算答案即可。

link

T4 game

首先根据后手的策略扫描线，按照 b_i 从大到小排序。直接考虑贡献太麻烦，先假设所有牌都贡献了 -b_i，那么一张牌被取就会产生 a_i+b_i 的贡献。

考虑记一张牌被取了为 1，否则为 0，那么一个合法状态应为：对于所有前缀，有前缀和 \leq \lceil \frac{len}{2} \rceil。

基础的贪心策略是，去找当前 a_i+b_i 最大的位置，如果加上这个位置后所有前缀都合法，那就加入，可以发现这样一定不劣。

每次都暴力去扫太劣，考虑每一轮修改后会产生哪些影响：首先删去这个元素，如果它本身不计入答案则无影响，否则考虑将它从答案中剔除，找到剩余未选项中 a_i+b_i 最大的位置，将它计入答案。

然后考虑加入新的元素，考虑先将它加入答案，然后找到第一个不合法的前缀，找到其中 a_i+b_i 最小的位置将其删去，可以证明这样操作后所有前缀都合法且一定不劣。

以上过程均可以使用线段树上二分维护，时间复杂度 \text{O}((n+m) \log n)。