传送门
tricks from
- \(10^9+9=149*671141\)。
- 求长度为 \(2n\) 的括号序列个数：只许使用 \((0,1)\) 和 \((1,-1)\) 两种移动，从 \((0,0)\) 移到 \((n,0)\) 且不许走到 \(y\) 轴下方的移动方案数。
- 函数凸性的贪心。
- 浮点二分限制迭代次数优于判断 \(r-l\) 和 eps 大小关系。
B
发现若 \(a_i=j\)，则 \([i,j-1]\) 必须升序放在 \([i+1,j]\) 上。显然有递推式 \(f_i=\sum_{j=0}^{i-1}{f_j}\)，按字典序从高位到低位求即可。code
简解：倒序扫描后 \(63\) 位，若 \(k-1\) 的第 \(n-i\) 位是 \(1\) 则交换 \(a_i\) 和 \(a_{i-1}\)。
证明考虑归纳法，设 \(k-1\) 最低位 \(0\) 的位为 \(i\)，则 \(k-1\) 的答案相当于循环移位 \([i,n]\)，此时 \([i,n]\) 已无法再前进。故此时字典序增加 \(1\)，最优为将 \(a_i\) 与 \(a_{i-1}\) 交换，然后将后面的排升序，这恰为 \(k\) 的二进制表示。
C（构造双射，括号序列）
限制等价于不存在长度 \(\le k-1\) 的链，使链上所有非链头节点都是其父亲的左儿子。若节点是其父亲的左儿子令其权值为 \(0\)，否则为 \(1\)。（根节点不算）先序遍历整棵树，得到的点权序列与树的形态形成双射。由于每个非叶子节点都有 \(2\) 个儿子，此时序列显然是括号序列。
问题转化为长度为 \(2n-2\)，不存在连续 \(k-1\) 个 \(0\) 的括号序列个数。设 \(0\) 为向量 \((0,1)\)，\(1\) 为向量 \((1,-1)\)，等价于求从 \((0,0)\) 到 \((n-1,0)\)，只允许使用上面两种位移，全程 \(y\) 坐标必须在 \([0,k-2]\) 间的方案数。定义 \(f_{i,j}\) 表示当前在 \((i,j)\) 的方案数 DP 即可。code
D
可以 \(4^{10}\) 枚举所有可能的放置方案。对每个方案求出格子的 delay 值，先处理 Rocket，再处理 Gun，Gun 优先打来的早且没被打爆的怪物。code
E（结合凸性的贪心）
题意相当于给定一组浮点数 \(b_i\)，和为 \(s\)。求一组和为 \(s\) 的整数 \(p_i \in [L,R]\) 使 \(\sum_{i=1}^{n}{(b_i-p_i)^2}\) 最小。
先令 \(p_i=L\)，每次选择一个 \(i\) 提升 \(1\)，提升若干次，最小化一个二次函数的值。根据二次函数的凸性，显然每次选差最小的（注意和绝对值没有关系！！）提升更优，但这样会炸。
我们发现，提升时一定是整体提升 + 个别点提升的形式。可以把每个 \(p_i\) 提到 \(x+b_i\)，不妨二分这个 \(x\)，找到最接近 \(s\) 的 \(x\) 之后再做局部提升。时间复杂度 \(O(n \log V)\)。code
I
注意到最优分组一定是值域连续的分到一起。排序后 DP，定义 \(f_i\) 表示 \(a_i\) 为最后一段结尾的方案数。可以斜率优化做到 \(O(n)\)，没写。code
J
构造。把所有环上的边染成 \(3\)，菊花边按节点奇偶性染 \(1\) 或 \(2\) 一定可行。注意 \(n \le 6\) 可以把 \([1,\lfloor \frac{n}{2} \rfloor]\) 的菊花边染 \(1\)，剩余菊花边染 \(2\)，环上存在构造可以只用两种颜色。具体见代码。code
K
破环成链。对某个点 \(x\) 考虑 \(i\in [x+1,x+n-1]\) 这些点，一定存在一个分界点使得两端 \(i\) 的 \(\vec{p_xA} \times \vec{p_xp_i}\) 符号不同。这个可以二分求，同理可二分出一个 \(B\) 的分界点，直线 \(\boldsymbol{p_xp_i}\) 满足条件当且仅当 \(i\) 在这两个分界点间。最后答案要除以 \(2\)。 code
L
相当于线段树合并，但只有左子树完全合并上才能合并右子树。注意不存在只有一个儿子的节点。 code