• 一句话题解
  • 2024.10.29
    • AT_abc290_f
    • AT_arc156_c
  • 2024.10.30
    • P5749 [IOI2019] 排列鞋子
    • AT_abc285_e

一句话题解

不能什么题都随便写写就过了，留点印象好一点。一直更新。

2024.10.29

AT_abc290_f

组合数数。满足树的形态要有 \(\sum deg_i=2n-2\)。考虑目前有 \(k\) 个儿子节点，直径最大肯定是 \(n-k\) 个非儿子点串一条长度为 \(n-k+1\) 的链，然后再挂儿子节点。总度数 \(2n-2\)，给 \(n-k\) 个非儿子节点支配的还剩 \(2n-2-k\)，易得插板：\(\binom{(2n-2-k)-2(n-k)+(n-k)-1}{(2n-2-k)-2(n-k)}=\binom{n-3}{k-2}\)。答案即为：\(\sum\limits_{k=1}^n \binom{n}{k}\binom{n-3}{k-2}(n-k+1)\)。

根据吸收恒等式（\(k\binom{n}{k}=n\binom{n-1}{k-1}\)）和范德蒙德卷积（\(\sum\limits_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\)）可以化简成 \(O(1)\)：\(Ans=(n-1)\binom{2n-3}{n-1}-(n-3)\binom{2n-4}{n-1}\)。

AT_arc156_c

构造。观察可得价值最小无论如何都是 \(1\)。方向转为构造排列。观察树是链的情况，排列直接为序号翻转过来。考虑树普通情况，每次取两个叶子节点交换序号即可。类似拓扑地，可以处理至原树变成一条链。

正确性证明：一条 \(u\to v\) 的简单路径，路上的编号大概形如 \(v\to u\) 的路径的编号。刚好是完全相反的，满足了 LCS 为 \(1\)。

2024.10.30

P5749 [IOI2019] 排列鞋子

贪心。对于每种大小用 vector 存鞋的位置，从后往前遍历，每次可配对鞋一定在 vector 最后一个最优。贪心显然成立。可以用树状数组优化求区间 \(1\)（交换次数）操作。

AT_abc285_e

DP。可设 \(S_i\) 表示一周 \(i+1\) 天只有一天休息日的贡献。易得 \(S_i=2\sum\limits_{j=1}^{\lfloor\frac{i}{2}\rfloor}a_j+[i\bmod 2=1]a_{\lceil\frac{i}{2}\rceil}\)。设 \(F_i\) 表示一周有 \(i\) 天的贡献，初始状态有 \(F_i=S_{i-1}\)。可以枚举休息日的个数：\(F_i=\max\limits_{j=2}^{i-2} F_j+F_{i-j}\)。答案为 \(F_n\)。