2021.09.10模拟赛

渔舟唱晚，响穷彭蠡之滨；雁阵惊寒，声断衡阳之浦。

2021.09.10模拟赛

T2没细想，T3大失误 -84 pts

A.Strange

Strange

考虑只相交的线段 = 所有线段 - 包含的线段 - 不交的线段

不交的线段找询问左端点左边的线段树右端点个数，右边同理

包含的线段先离线下来，按右端点排序，加入线段树区间的左端点，直接在树状数组上查询区间的端点数量即可

code

B.加冕

加冕

考虑大力 dp

设 $dp_{S}$ 是达成质因子状态的最小代价

转移 $dp_{S} = \min\limits_{T \sub S}dp_{T}+f(S-T)$

计算 $f(S)$ 可以用同于最短路的方法

以 $p$ 为模数，在模 $p$ 意义下操作 $q\times x$ 和 $q+1$

$dis_0$ 即最小值

code

C.交错的字符串

交错的字符串

处理出前一半的哈希值然后和后一半的配对即可

因为 $A+B = A'+B' \Rightarrow A-A' =B'-B$

所以记录下哈希值的差值即可

code

D.爬

爬就爬，我最会爬了

爬

叉人神题

大概的思路是贪心的按照 $a_i-b_i$ 排序，然后再不被淹的过程中答案具有单调性（显然 $x$ 天能出去 $x+1$ 也能）

所以二分时间，确定时间后考虑最优策略要么是把前面的一个 $b$ 很大的值最后吃，或者是把后面的一个 $a$ 很大的最后吃

分别特判一下

在找 $b$ 最大的值需要特判一下拿掉了这个值会不会导致中间被淹，而且因为 $a_i-b_i$ 单调递减，所以拿掉就不合法的一定是一个前缀

code

Extra.

A.防线

防线

看起来就很线段树合并

让线段树的节点代表填满最左端的 $1$ 和最右端的 $1$ 中间的最小代价

考虑向上 pushup 的过程

考虑左区间最右的 $1$ 和右区间最左的 $1$

中间的 $r-l-1$ 个 $0$ 一定要他们填满，所以 $r-l-1$ 和当前的答案取 $\max$ 合并

最终最外围的 $m-(r-l+1)$ 个点一定需要这么多次操作，取 $\max$

code

B.钦定

钦定

先把没用的点区间，让操作序列单增

反向考虑贡献

当前区间长度如果为 $x$

那么他会用到长度为 $y$ 的区间 $\lfloor\dfrac{x}{y}\rfloor$ 次，和 $x \bmod y$ 的区间一次

如果 $x$ 区间被用过了 $t$ 次

相应的 $y$ 区间会加上 $\lfloor\dfrac{x}{y}\rfloor t$ 次， $x \bmod y$ 用到了 $t$ 次

所以先加入大的区间，反向更新贡献，然后区间长度 $\le n$ 的做一下后缀和就是答案

code