2024 年 syzx 春季训练 6

phtniit · 2024-05-15 17:21:18 · 个人记录

A: cf348d

简单容斥。

一个非常经典的套路了，答案等于 f(1,2,n-1,m) \times f(2,1,n,m-1) - f(1,2,n,m-1) \times f(2,1,n-1,m)。
其中 f(i,j,x,y) 表示从 (i,j) 到 (x,y) 的方案数。

B: cf1406d

贪心。

等价于最小化 b_1 和 c_n：

• 当 b_1 固定时，则 c_1 也固定了；
• 为了最小化 c_n，考虑当 d = a_{i+1} - a_i 的正负关系：
  • 当 d<0 时，我们让 b_{i+1} 变小，而 c_{i+1} 不变；
  • 当 d>0 时，我们让 c_{i+1} 变大，而 d_{i+1} 不变；
• 故 c_n 关于 b_1 可以表示为 a[] 的某个差分式子，而区间加法，只相当于差分的单点变化，故不难计算出 b_1，c_n 的最优值。

  C: arc123d

  贪心。

不妨令 d_i = -c_i，则有 b_i - d_i = a_i 且 b 和 d 都是上升的。 对于任意一组解 \{b\} 和 \{d\}，我们显然可以整体上下平移，使得答案发生变化，为了使得答案尽量小，我们其实希望平移后图像尽量接近 Y=0 的轴线。

并且我们会希望极差尽量小，所以 b_i 和 d_i 不会同时发生变化。

那么变化情况同 B 种讨论一样，我们三分一下 b_1 即可。

D: arc138c

贪心。

我们假设小于中位数的某个 A_i 上面有个 +1，大于中位数的上面有个 -1，那么所有的循环位移里面必然有个 k 满足任意的前缀都不小于 0，接下来的事情就容易了：

• 先手总是取最近的一个 -1；
• 后手总是取顶端的一个 +1。

E: cf1685c

贪心。

首先有结论，一定可以通过 2 次操作使得括号平衡：

• 选择一个前缀 [1,k] 反转；
• 选择一个后缀 [k+1,n] 反转。

这样的效果相当于整串反转以后，循环右移了恰好 k 个单位的效果。
而根据前一题，我们已经知道一定有一个循环右移是满足括号匹配的。

所以只需要检查是否可以通过少于 2 次完成。
0 的情况是容易的，考虑 1 的情况：

• 设前缀和第一次出现 -1 的位置是 i；
• 设 [1,i] 中前缀和取得最大的位置是 j；
• 那么反转的子区间左端点必然是 j+1；
• 那么 O(n) 枚举一下右端点就可以了。

F: P6672

计数。

经过前 2 题我们已经知道了：恰好有 n 个 +1 和 n 个 -1 的序列里，必定存在某个循环排列是满足（括号匹配）前缀和均大于等于 0 的。

事实上，这个结论还可以更强：\sum{a_i}=1的序列 a[] 满足恰好仅有一个循环排列是满足前缀和均是大于 0 的。

包括最后一张卡牌在内，我们令 a_i = w_i-1，则现在 (\sum_{1<=i<=m+1}{a_i})=-1。
我们发现只要对于 i <= m 的任意时候前缀和大于等于 0，则表示可以往后至少抽一张卡。
前缀和大于等于 0，显然等价于后缀和小于 0。
根据最前面的结论，我们知道这样的组合数等于圆排列的个数（因为任意一个排列都仅有一个循环排列满足）：m!。
由于最后一张卡牌必须是所有 a_i=-1 的牌里面的某（特定）一张，所以 ans = \frac{m!}{m-n+1}，其中 n 是有特殊过牌能力的卡牌。

G: qoj7632

计数。

记 s_i 表示合法的一组结果。
我们增加 s_0=m 和 s_{n+1}=m 的头尾两个元素。
则 s_i 应该满足 \sum{|s_i-s_{i-1}| <= 2m}。
考虑这样一个 +1/-1 序列 a[]：

• 若 s_i-s_{i-1}=k>0，则 append k 个 +1 到 a[]；
• 若 s_i-s_{i-1}=k<0，则 append k 个 -1 到 a[]。

则 a[] 的长度应当小于 2m。
考虑某个位置 a_i = +1 而 a_{i+1} = -1，我们说这里发生了一个转折，每一个转折位置的左右两个元素必然属于两个不同的 s_x（但是其他相邻位置同样可能属于不同的 s_y），我们其实是要用 n+1 个元素对其插板。
不妨假设 a[] 的长度是 2L（恰好有 L 个 +1 和 L 个 -1 ），且发生了 i 次转折。
则对任意满足这种转折的的 a[] 序列插板到 n+1 个元素的方案数是 \binom{n+1+2L-2i}{2L}。
而给定 L,i 的合法 a[] 序列一共是 \binom{L-1}{i-1}\binom{L}{i-1}\frac{1}{i} 种，这个可以通过 Ranney 引理推导出来。

故 ans = 1 + \sum_{1<=L<=m}{\sum_i{\frac{1}{i}\binom{L-1}{i-1}\binom{L}{i-1}\binom{n+1+2L-2i}{2L}}}，可以拆项后使用 FFT 加速。

H: qoj7632

计数。

记 s_i 表示合法的一组结果。
我们增加 s_0=m 和 s_{n+1}=m 的头尾两个元素。
考虑把 s[] 应当可以拆成 s_i = a_i + b_i 的形式，满足：

• 且 |a_i-a_{i-1}| 和 |b_i - b_{i-1}| 不会同时发生变化；
• 且 s_i = a_i+b_i <= m；

由于第 4 个条件的存在，不妨设 c_i = m-a_i >= b_i，则等价于统计：

如果不考虑第 3 个条件，原问题等价于统计 (0,0) 走到 (n,m) 的两条不穿越路径的方案数。
也等价于统计点 P 从 (-1,1) 走到 (n-1,m+1) 和点 Q 从 (0,0) 走到 (n,m) 的两条不接触路径的方案数，记作 f(n,m) = {\binom{n+m}{m}}^2-\binom{n+m}{m-1} \times \binom{n+m}{m+1}。

考虑使用容斥原理，钦定中间有某 i 个下标恰好是同时变化的（此时可以看作终点变成了 (n,m-i)），则：

I: qoj8542

贪心。

记 s_i 表示某个最终的一组结果。
我们增加 s_0=\inf 和 s_{n+1}=\inf 的头尾两个元素。
则 s_i 应该满足 \sum{|s_i-s_{i-1}| <= 2\inf}。

最终付出的代价就是 \sum{s_i}=\sum(s_i-b_i)+\sum{b_i}。

需要考虑的是怎么用最小的\sum{(s_i-b_i)}把 b[] 变作一个合法的 s[]。

受到约束的是最终 \sum{|b_i-b_{i-1}|} 需要不超过 2\inf，考虑最小的一段连续的 b_i：

• 单独调整任意一个对约束的收敛都没有帮助；
• 只有整体向上调整一个单位，方可以把 \sum{|b_i-b_{i-1}|} 减少 2。

但选择最小的 b_i 未必最优，我们希望 b_i 向上调整的面积尽量小，故每次贪心选择满足 b_L < b_{L-1} \land b_R < b_{R+1} 的最短的一段连续相等的 [L,R]，让其区间 +1，花费代价 R-L+1。