8.17 小线下赛（小 l 到小 n）

• T1：数据结构优化 DP、最短路都可过，最短路可以用“前（后）缀优化建图的方式”。
• T2：哈夫曼树。
• T3：可以发现，对于两个弓箭手 \(i,j\)，如果 \(r_i\leq r_j\)，只要 \(x_i-r_i\leq x_j\leq xi+r_i\)，则这两个弓箭手能互相在对方的攻击范围，所以 \(i,j\) 能互相掩护的条件是 \(r_i\leq r_j,q_j-k\leq q_i\leq q_j+k,x_i-r_i\leq x_j\leq xi+r_i\)。对第一维排序，第二维分治，用双指针维护当前的 \(j\) 符合要求的 \(i\) 的区间，第三维树状数组维护。另一种方法，设 \([L_i,R_i]\) 表示第 \(i\) 个弓箭手能攻击的范围，则互相在对方的攻击范围的条件是 \(R_i\geq x_j\geq x_i\geq L_j\)，看似三维偏序关系，实际上 \(R_i\geq x_j\geq x_i\) 只是一个限制，可以通过差分转化成二维偏序。对大小关系需要灵活转化。

8.19 线下赛（小 o 到小 r）

• T1：根号分治。
• T2：构造，可以用长度为 \(9\) 的周期，也可以用哥德巴赫猜想。
• T3：CDQ 分治，左右维护单调栈。
• T4：树的方法简单。实际上，原图可能存在奇环，可以通过走奇环改变路径长度的奇偶性。考试没考虑到奇环，与图论路径的奇偶性，需要考虑不是二分图的情况，走一次奇环可以改变奇偶性。

8.24 日组队赛（小 s 到圈 B）

• s：简单前缀和优化 DP。
• 圈 B：二分第一问，第二问前缀和优化 DP。
• z：一个转换是每个数何老板取和你取是一样的，所以可以变成取 \(2n\) 个数。可以前缀和优化 DP，也可以用组合数学。
• u：树上 DP。
• w：考虑计算每条边的贡献，跑树上背包即可。size 优化的树上背包时间复杂度 \(O(n^2)\)，理解：以 size 为上界枚举体积相当于枚举子树内当前加入的点，所以相当于 DFS 小的点向 DFS 序大的点转移，一共有 \(O(n^2)\) 组这样的关系。
• y：01 分数规划加树上背包。
• v：对于商店 \(i\)，设 \(g_j\) 表示在前面的商店买 \(j\) 箱可乐最小费用，\(f_j\) 表示在这个商店之后有 \(j\) 相可乐并运送到下一个商店的费用，\(x\) 表示这个商店与下一个商店距离，则 \(f_j=\min\{g_k+C_i(j-k)+j^2x\}(j-F_i\leq k\leq j)\)，把只与 \(j\) 有关的项提出，\(f_j=\min\{g_k-C_ik\}+C_ij+j^2x(j-F_i\leq k\leq j)\)，可以用单调队列优化。
• t：设 \(f_{i,j}\) 表示左手写完 \(i\) 右手写完 \(j\) 的最小时间，可以发现当 \(A_i\neq B_j\) 时，相当从前面最近的 \(i-j\) 相同且 \(A_i=B_j\) 的状态转移而来，所以只需要从左往右算 \(f_{i,p_i}\) 即可，其中 \(p_i\) 表示 \(A_i\) 在 \(B\) 中出现的位置。
• x：\(f_{l,r,k,0/1}\) 表示考虑完区间 \([l,r]\) 的顾客，还要服务 \(k\) 个顾客，当前在 \(l/r\) 的最小费用。
• 圈 A。

8.26 日线下赛（A 到 D）

• A：设 \(f_{i,j}\) 表示用 \(i\) 个数凑出 \(j\) 的方案，有两种情况，有 \(1\)，则是 \(f_{i-1,j-1}\)，没有 \(1\)，则是凑出 \(2j\) 后除以 \(2\)，是 \(f_{i,2j}\)。

• B：求的是 \(\frac{1}{2}\sum_{i=0}^n\sum_{j=0}^n\operatorname{popcnt}(i)+\operatorname{popcnt}(j)-2\operatorname{LCP}(i,j)\)，\(\operatorname{popcnt}(i)\) 表示二进制 \(1\) 的个数，\(\operatorname{LCP}(i,j)\) 表示二进制的最长公共前缀，分别数位 DP 即可。

• C：一次的步长最大为 \(9\) 则必须经过连续长度为 \(9\) 的区间中的一个。对每组询问找到分界点 \(mid\)，在 \([mid-4,mid+4]\) 中枚举中转点，分治实现，类似猫树，分治的区间长度过小则直接暴力。为了保证复杂度和正确性，可能需要在当前分治的区间和左右的一些点中做 BFS。

• D：一定有一种最优方案满足：每班身高由小到大排序，相邻的人用同一张桌子。此时，将桌子按左端点由小到大排序并去掉被包含的桌子，则使用的桌子具有决策单调性，分治即可。一个优化是把所有需要用一张桌子的人排序，用双指针求用一张桌子的不舒适度的和。