杂题笔记

Ice Baby

• 首先需要掌握最长不降子序列的二分做法：定义 $f_i$ 表示：长度为 $i$，末尾最小值。
• 研究一下会发现，每次我们需要进行一个平移操作：设题目给的区间为 $[L, R]$，设 $l$ 为最后一个满足 $f_i \le L$ 的 $i$，$r$ 为最后一个满足 $f_i \le R$ 的 $i$。要把 $f_{[l+1, r]}$ 平移到 $f_{[l+2, r+1]}$，并把 $f_l$ 设置为 $L$。
• 注意到：一，f 数组是满足单调不减的；二，我们需要维护的只是最大的长度（即 f 数组有值的范围）。因此，维护 f 数组的下标变得不重要了。 可以用 multiset 来代替 f 数组，储存数组内的值即可。
• 这么做的好处是，平移操作只需要考虑对 $l$ 和 $r$ 附近的影响即可，不需要处理下标变化。恰好，multiset 也是支持 lower/upper_bound 操作的。
• 结合提交代码。
• 经验总结：平移操作，要看看下标是否重要，如果不重要，想想可不可以用 multiset 代替。

We're teapots

• 区间 $[l, r]$ 内（设长度为 $r - l + 1 = n$）取 $c$ 个点，且不能相邻，方法数：$C_{n - c + 1}^c$。证明：要取 $c$ 个点，就有 $n - c$ 个空位，现在要在这些空位之间插入 $c$ 个选择的点（插板法），且不能插在同样的间隙中，因此方案数为 $C_{n - c + 1}^c$。
• 矩阵乘法：$n \times m$ 矩阵 A 乘以 $m \times k$ 矩阵 B 得到 $n \times k$ 矩阵 C：$C_{i,j}$ 就是 A 的第 i 行和 B 的第 j 列都是 m 个数，让它们一对一乘起来再加起来。

Triangle Toggle

• 性质题。对于这类性质题，不妨考虑每次操作中某些量的变化。
• 这道题，定义与某个点相连的黑边数为 $f(u)$。每次操作可以使得选中的三个点的 f 分别增加 0，0，2 或者 0，0，-2 或者 2，2，2 或者 -2，-2，-2。故每个点的 f 可以在奇偶性不变的条件下任意变化。
• 这个证明不是特别严谨，因为增加的值是原本三条边的颜色决定的。可以这么想：如果需要给（且可以给）某个点 u 的 f 加 2，那么它就必定连着两条白边 $(u, x)$ 和 $(u, y)$。如果 $(x, y)$ 是黑的，那么就是给 $f(u)$ 加 2，其他不变；如果 $(x, y)$ 是白的，那么就给 $f(u)$，$f(x)$，$f(y)$ 都加 2，这样更好。总之就是能把所有点的 f 都尽可能不断加 2。

Sliding Tree

• 答案：n - 树的直径。
• 每次操作（最优情况下）可以使树的直径加一。把直径作为主链，只要每次选择直径上一个有分支的点 u，假设分支的第一个点为 v，那么把直径的某一半从 u 接到 v 上即可。
• 这同样是观察操作过程中某个量的变化。

Non-Ancestor Matching

• 树形 dp。
• 每一步，我们遇到的是这样的局面：对于点 u，它有 k 个子树，这些子树中不能内部消化的点的数量分别为 $a_1, a_2, ..., a_k$，现在要尽可能地进行配对，并处理出以 u 为根的子树中不能内部消化的点的数量。
• 如果 a 中最大的数大于其他所有数之和，那么总的不能内部消化的点的数量就是（a 中最大的数 - 其他所有数之和）。否则，可以证明一定可以配对使得落单的点的数量是 0 或 1（依奇偶而定）。最后还要加上 u 这个点。

Subset Product Problem

• 折半查找。
• 枚举超集（其中 f[st] 表示对于 st 的所有子集 x，【x 的【出现次数】次方】之积）： CPP

  for i in [1, n]:
    for st in [0, 1 << 20):
      if a[i] | st == st:
        f[st] *= a[i]
  ans[i] = f[a[i]]
  

• 枚举子集（其中 g[st] 表示 st 的【出现次数】次方）： CPP

  for i in [1, n]:
    for st in [0, 1 << 20):
      if st | a[i] == a[i]:
        ans[i] *= g[st]
  g[a[i]] *= a[i]
  

• 折半（其中 F[x][y] 表示对于所有【前十位包含于 x，后十位等于 y】的二进制数，【它们的【出现次数】次方】之积）： CPP

  for i in [1, n]:
    for st in [0, 1 << 10):
      if a[i].前十位 | st == st:
        F[st][a[i].后十位] *= a[i]
  
    for st in [0, 1 << 10):
      if st | a[i].后十位 == a[i].后十位:
        ans[i] *= F[a[i].前十位][st]  
  

• 枚举超集是修改 $O(2^{20})$，求值 $O(1)$；枚举子集是修改 $O(1)$，求值 $O(2^{20})$；折半查找是修改 $O(2^{10})$，求值 $O(2^{10})$，就匀了。总的复杂度就是 $O(n \times 2^{10})$。

Antiamuny Wants to Learn Swap

• 从逆序对角度考虑。交换邻项可以让逆序对数量减一。“完美”的意思就是，交换“邻邻项”也只能让逆序对数量减一。
• 实际就是：询问区间内是否存在递减三元组。
• 用单调栈预处理出【前面最近的更大的数】和【后面最近的更小的数】，然后对于每个 r 处理出使得 [l, r] 内不存在递减三元组的最大的 l。这样询问就是 $O(1)$ 了。

Maple and Tree Beauty (Hard Version)

• 概述：把树分成一层一层，做优化的背包。
• 下面称 0 为黑点，1 为白点。
• 注意到最优的方案一定是使叶子节点的最长前缀子序列最长。因为如果不是前缀，下面的层节点数量会更多，就不好完成任务，不优。
• 定义 f[i][j]：前 i 层（从上往下），每一层的点都只能染同种颜色，共染了 j 个黑点，可不可行？假设前 i 层共有 S[i] 个点，那么我们要判断，是否存在一个 j，使得 f[i][j] 为真，且 S[i] - i < N - K（白点数也不能超出限制）。如果不存在，就代表不可行，输出 i - 1。
• 问题是，极端情况下树是一条链，这样层数（物品数）就是 n。这样背包就是 $O(n^2)$ 的。
• 一种方法是用滚动数组 + bitset 优化。由于是可达性 dp，所以可以把 f[i][] 用 bitset 表示出来。时间复杂度 $O(n^2/W)$，其中 W 为计算机的位数（64）。
• 另一种方法是：容量优化不了，考虑优化物品数。考虑多重背包优化。每一层的节点数是递增的。把节点数相同的层合并为一个物品。
• 这样，每一个物品的重量（节点数）是递增的。一个严格递增数列和为 n，那么数列长度是 $O(\sqrt n)$ 的。因此，物品数是 $O(\sqrt n)$ 的。
• 跑单调队列优化的多重背包，复杂度 $O(n \sqrt n)$（虽然我不会 qwq）。

A Cruel Segment's Thesis

• 反悔贪心。每个线段产生 R 或 -L 的贡献。假设所有的线段一开始都产生 R 的贡献，现在要选出一些线段，把它们的贡献从 R 改成 -L，也就是使总答案减少 L+R。把所有线段按照 L+R 排序，选择 L+R 最小的 n/2 个数，把它们的贡献从 R 改成 -L。

Price Tags

• 设价格的值域为 V，f(v) 表示 v 这个价格的出现次数。以下是伪代码，遍历边界不一定准确。

for x in [2, V]: // 折扣倍数
  cnt = 0 // 有多少个牌子能重复使用
  for v in [1, V / x]: // 折扣后的价格
    get l, r // 要使得折扣后的价格为 v，原价的范围
    cnt += min(f(v), f(l ~ r))
  get tmp_ans // 折扣倍数为 x 时的收益
  ans = min(ans, tmp_ans)
output ans

• $V/1 + V/2 + V/3 + ... + V/V$ 是调和级数，复杂度 $O(V \log V)$。

Almost Sorted 2

• 对于某个数组重排的方案数问题：考虑从小到大（或按一定顺序）插入数字。
• 求组合数：预处理出阶乘及其逆元。
  CPP

  fac[0] = 1;
  cfor (i, 1, n)
    fac[i] = (fac[i - 1] * i) % mod;
  inv_fac[n] = inv(fac[n]);
  bfor (i, n - 1, 0)
    inv_fac[i] = (inv_fac[i + 1] * (i + 1)) % mod;
  

• 题解。