【VP 记录】EDU092
KSCD_
·
·
个人记录
记录
ABC 切了，D 进行了大分讨，讨到一半去吃饭了，回来打完又改了小错误过了，EFG 没看。
题解
A. LCM Problem
发现要求即为两不等的数 x,y 以及它们的 lcm 在同一区间 [l,r] 内，考虑让这三个数之间的差尽可能小，且让大的尽可能大。所以发现让 lcm 与较大的数 y 相等一定最优，考虑怎么让 x 尽量大，发现 y 为偶数时 \frac{y}{2} 最大，所以取最大的偶数作为 y，看 x=\frac{y}{2} 是否不小于 l 即可。
B. Array Walk
发现向左回退的操作一定会在同一个位置操作完，不然肯定不优，因此枚举所有可能的位置作为向左回退的位置，取可能的最大答案即可。预处理前缀和可以实现每次 O(1) 查询结果。
C. Good String
发现好串定义可以转化为 t_i=t_{i-2}，这里 t_0=t_n,t_{-1}=t_{n-1}，所以分奇偶讨论，若长度为奇数则所有位必须相同，若为偶数则必为两位数循环出现，分别枚举 10 个数和 90 种两位数的情况，暴力判断需要删掉多少即可。
D. Segment Intersections
对所有贡献到最终答案中的部分分类，可以分成本来就有的交集，本来在 a,b 中其中一个有的部分，代价为 1。这两中一定是会先贡献的，分讨一下贡献到哪一部分时满足条件。
这两部分用完后，每组区间一定会相等或无交集，相等的话每次都需要 2 的代价使答案增加 1。无交集的话需要扩展至两个区间有共同端点，之后会有一部分代价为 1 的直到两区间相同，剩下的同样代价为 2。可以枚举处理的区间数量 x，取最小代价即可。
E. Calendar Ambiguity
数学题，直接写出式子，即为找 x,y 的组数使得：
-
x<y\le \min(m,d)
-
(x-1)d+y\equiv(y-1)d+x\mod w
第一个式子很简单，为了方便先设 \min(m,d)=c，需要化简的是第二个式子。首先移项合并得到 (y-x)(d-1)\equiv 0 \mod w，即 w | (y-x)(d-1)，考虑将 w 和 (d-1) 约掉公因数 g，得到 w' | (y-x)d'，由于 w' 与 d' 互质，问题转化为求 x,y 数量使得 y-x 是 w' 的倍数。
直接设 y-x=kw'，如果直接枚举 k 复杂度不对，考虑 k 的最大范围，由于 y\le c,x\ge1，所以 k\le\lfloor \frac{c-1}{w'}\rfloor，设 z=\lfloor \frac{c-1}{w'}\rfloor。再考虑 k=i 时的方案数，发现 y-x=iw'，又因为 [x,y] 闭区间一定在 [1,c] 闭区间里，所以方案数为 c-iw'
综上，答案为 \sum_{i=1}^z c-iw'，拆开得 zc-\sum_{i=1}^ziw'，等差数列求和得到 zc-\frac{(z+1)z}{2}w'，其中 w'=\frac{w}{\gcd(w,d-1)},c=\min(d,m),z=\lfloor \frac{c-1}{w'}\rfloor
F. Bicolored Segments
首先区间题能够考虑到每个区间在右端点处处理，最近刚接触到这个思想。
考虑朴素 dp，先把所有端点离散化下来，设 f_{i,j,k} 表示考虑到第 i 个位置，且 [j+1,i] 全为 k 的最大答案。转移如下：
-
f_{i,i,k}=\max(\max_{j=0}^{i-1}f_{i-1,j,0},\max_{j=0}^{i-1}f_{i-1,j,1})
-
f_{i,j,k}=f_{i-1,j,k}+\sum_{x=1}^n[l_x>j][r_x=i][t_x=k]
首先 i 维可以滚掉，主要考虑 j 维的处理，把 j 维的 k=0/1 分别拍到两颗线段树上，然后从左到右枚举 i，把所有 r_x=i 的区间在 t_x 的线段树上进行 [0,l_x-1] 区间加一，也就是把上述第二个式子中所有的 r_x=i 全部加上了，最后再把两颗线段树的 i 点全部单点修改成两个线段树的最大值即可。