ABC217 总结

__vector__ · 2024-03-06 13:42:57 · 题解

被 lxn 用来当模拟赛了。
打得稀烂。
赛后用了不少时间推完除了 Ex 所有题做法。

• D 题连值域范围不看，就整了个很长的线段树上去，WA 样例了才知道做法假了，然后改成 deque 实现的一个类似启发式合并的东西。最后数组开小爆零了，不开小就能过。
• F 题最后时间不够用，想出了区间 dp ，但是赛时傻逼，顺序处理搞错了，而且忘写记忆化了（然而过了所有样例！！！！！），最后甚至还不如骗分的得分多。
• G 题，赛时没做，但感觉还是一个比较简单的容斥板子，赛后自己推导做法 AC 了。

最后垫底了。

C

模拟

D

我会两种做法

• 第一种：
  离散化，然后对于每个线段维护一个 deque，每次分裂优先把较小的段分裂出去，这样类似于启发式合并，复杂度 O(n \log n) ，但是 deque 的空间占用巨大，我开了 1e5 个 deque，用了 700+ MB，还是手写链表更保险。
• 第二种：
  本质上，只需要知道 x 左右两边最近的端点。
  用 set 维护所有的断点就可以了。

  E

  观察发现，新插入的元素可能破坏原来元素的有序性，所以干脆分成两个集合，将会破坏有序性的元素单独放。

维护两个集合：按照从小到大排序的集合 s，按照插入时间排序的集合 t。

显然 s 中的元素比 t 中插入时间早，查询第一个元素优先查 s，再查 t。

如果进行排序，那么将 t 所有元素插入 s，再清空 t 就可以了。

F

一眼区间 dp，设 dp_{l,r} 代表区间 l,r 全部消除的方案数。

然后想想怎么拆成子任务。

显然只需要枚举 l 与哪个点一起出去就可以了。

假设 l,rg 一起出去，那么如果不考虑顺序，答案就是 dp_{l+1,rg-1} \cdot dp_{rg+1,r}。

但现在，[l+1,rg-1] 区间和 [rg+1,r] 区间可以交替执行操作，那么只需要求出有多少种交替执行的顺序就可以了。

可以这么想：左边的区间有 \lfloor \frac{rg-l+1}{2} \rfloor 次操作，也就是说有 \lfloor \frac{rg-l+1}{2} \rfloor+1 个空（包括左右两端以外），而右边有 \lfloor \frac{r-rg}{2}\rfloor 次操作，现在需要将它们插入到这些空，或者说把这 \lfloor \frac{r-rg}{2}\rfloor 个操作分到 \lfloor \frac{rg-l+1}{2} \rfloor+1 个可空集合里面，求方案数，这个 OI-wiki 组合数基础上有。

然后没了。

G

下面是我一步步推导出本题的草稿：

mod M= 0:
mod M= 1:
mod M= 2:
mod M= ...:
注意到，由于两个模 M 结果相同的数不能放在同一个组，也就是对于每个同余组合，都要进行排列，选择前往的组。
设模 M 同余 i 的，有 siz_i 个，总共 k 个组，则有 C(k,siz_i) 的方案数选择组，再乘上 siz_i! 代表排列数。
但是，现在要求 k 个组都不能空，也就是说，不合法方案为：存在至少一个组，满足任意模 M 同余集合都不选择它。
具体如何计算呢？
先不考虑集合不能为空，计算出总方案数，然后减去 （满足限制 1，但是有组为空 的方案数）
注意到，假设有 i 个组是空的，那么 C(k,i) 种选择组的方案数，然后呢，对于每个同余集合，只剩下 C(k-i,siz) siz! 种合法的方案，然后每种集合方案数乘起来
也就是说，如果分组数量确定为 k，那么枚举空的数量 i，但是每枚举一个 i，每个同余集合的答案就变了，还得重新计算。
显然不可接受，考虑如何 O(1) 从 k,i-1 继承到 k,i，设 n=k-i，m=siz 则 继承后，n-=1，原来是 fact[n]/fact[m]/fact[n-m]，现在是 $fact[n-1]/fact[m]/fact[n-1-m] = (fact[n]/n)/(fact[m])/(fact[n-m]/(n-m)) = fact[n]/fact[m]/fact[n-m]/n (n-m) = C(n,m)(n-m)/n= C(k-i,siz)(k-i-siz)/(k-i) 感觉上面不太好处理，所以是否可以枚举预处理对于任意 n,m，C(n,m) 的值？ 然后，注意到，对于每个集合的组合数，其选择 必然等于 siz，所以可以仅枚举 k-i 的值，预处理出对应的方案数总和。 接下来就好办了，这样做应该就可以了： 枚举分组 k，先计算出允许空组但模 M 意义下相同的两个数不能在同组的情况下的总方案数（记为 sum_1），然后通过容斥计算出必须有空组，且模 M 意义下相同的两个数不能同组的方案数（记为 sum_2），则答案是 sum_1 - sum_2 但是注意题目说两种情况不同，当且仅当两个数在第一种情况同组，第二种情况不同组，也就说分成的所有组没有编号，易知，sum_1 - sum_2 统计的情况数是按组有编号计算的，题目的每种不同情况都会被统计 k! 次，所以最后真正的答案是 \frac{sum_1-sum_2}{k!}$

Ex

没看题。