本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-12 12:43:06

记录

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$ 点全部单点修改成两个线段树的最大值即可。