24.10.10

非常好双十模拟赛，使我的分数任意旋转都不变（〇），爱来自 CDQZ。

话说怎么双十模拟赛题面都是双十一啊（

A

数据范围弱化版：P2592。

\(n, m \le 10^7\)。

把一个看作 \(+1\) 另一个 \(-1\)，那么合法序列即为前缀和的最大值与最小值的差 \(\le k\)。在一维上不好写，上二维平面。

把向右走一步看作 \(-1\)，向上走一步看作 \(+1\)，那么每个格点代表的前缀和为 \(y - x\)，也就是要求路径上 \(\max(y - x) - \min(y - x) \le k\)。也就是划定两条直线 \(y = x + i,y = x + i + k\) 使路径不穿过这两条直线。

芝士反射容斥，可以看集训队论文再谈格路计数。也可以拜谢反射容斥 & exLucas 大蛇 NT。

令 \(n,m\) 是非负整数，\(l, r\) 是整数，满足 \(l < 0 < r, n + l < m < n + r\)，从 \((0, 0)\) 到 \((n, m)\)，始终不与 \(y = x + l\) 和 \(y = x + r\) 相交的格路数量为

\[|L((0, 0) \to (n, m) | x + l < y < x + r)| = \sum_{k \in \mathbb Z}\left(\binom{n + m}{n - k(r - l)} - \binom{n + m}{n - k(r - l) + r}\right) \]

使得组合数有意义的 \(k\) 是一个区间。只需要计算 \(O(\frac{n + m}{r - l})\) 个 \(O(n + m)\) 量级的组合数。

然后这个题里没有规定上下边界，只要求上下边界距离为 \(k\)，所以枚举上下边界，但是枚举之后发现每个上下边界距离为 \(\Delta\) 的路径被算了 \(k - \Delta + 1\) 次。那么记枚举上下边界距离为 \(k\) 算出的答案是 \(calc(k)\)，最终答案为 \(calc(k) - calc(k - 1)\)

这样复杂度是 \(O(\frac{n + m}{k} \times k ) = O(n + m)\) 的。

B

令 \(f_i\) 表示面值为 \(i\) 的方案数，记 \(cnt_i\) 表示面值为 \(i\) 的优惠卷数量，那么转移：\(\displaystyle f_i = \sum_{d = 1}^{100} f_{i - d} \times cnt_d\)。

最终答案为 \(\displaystyle\sum_{i = 1}^k f_i\)。

长得矩阵模矩阵样的。

C

交互题，不会配交互库所以没写（

鳶一折紙：怎么 std 只有 37pts。还是我交互库配错了？

D

这里区间端点是隔板，所以活动范围是开区间。

考虑对每个区间 \((l, r)\) 增加两维 \(l', r'\)，表示拆了板子后的区间是 \((l',r)\) 和 \((l, r')\)，那么两个区间 \((l_1, r_1, l_1',r_1'),(l_2,r_2,l_2', r_2')\) （不妨设 1 在 2 左侧）同时选的条件为 \(r_1' \le l_2 \wedge r_1 \le l_2'\)。

找区间可以从下往上扫描线 + set，当一个线段被加入就向左找 \(3\) 个点向右找 \(3\) 个点统计区间。

将所有区间按 \(r'\) 排序。

设 \(f_i\) 表示考虑完最右端点（就是 \(r'\)）在 \(i\) 之前的区间后，最多能选多少区间，\(g_i\) 表示在 \(f_i\) 最大的情况下，最后一个区间的右端点（\(r\)）最小是多少。

那么考虑第 \(i\) 个区间时，先让 \(f_{r_i'}\) 继承前面的状态，再用 \(f_{l_i}\) 去更新 \(f_{r_i'}\)，更新条件是 \(l_i' \ge g_{l_i}\)。