ICPC2024 Hangzhou 补题

· · 个人记录

场上大唐，回来补题。

A. 签子，如果前两串不等长直接挂，如果第三串不等长直接赢；三个都等长的时候对前两个串对应必须相同的字符连边，并查集维护，如果第三串每个位置的字符和第一串对应位置字符都在一个连通块里就寄了，否则就赢了。

K. 签子，枚举取到最终答案的行，掏出填这一行的位置，把后 k 个往前挪即可。

M.

仍记得场上写了一坨不明物质，错错错然后过，赛后发现我真是傻也已矣。

首先条件等价于每个区间 \gcd=\min，对于 \min 固定的情况下每个极长的区间都满足即可。

单调栈求出这些极长的区间，容易发现区间 \gcd 等于这个区间内差分数组的 \gcd（记作 g） 和最小值的 \gcd(g,\min)。此时最小值等于 \gcd 即意味着 \min \mid g。其中 \min =a_i+x，因此 (a_i+x) \mid g。

每个区间的 g 易通过区间 \gcd 技术如 st 表求出。一个 x 要满足条件必然要满足所有的 (a_i+x) \mid g。因此我们随便找一个 g 根号枚举因数可得一个可行的 x 的集合，然后对于每个 x 挨个区间 check 一下即可。

注意 g=0 意味着没有限制，不能用；如果所有 g 都等于 0 意味着序列所有值都相等，因此每个 x 都可以。

E.

电梯题。场上题目分配专业不对口，做的很慢。

考察答案下界，首先每个往上去的人花的能量少不了，其次从初始位置到达 \max r 位置之间（毕竟你总得到达 \max r），没有被任意一个区间覆盖到的位置，从下往上走这些位置的能量，是必须的。

考虑构造使得能取到答案下界。先走到 \max r，找出一个 l,r 分别单调的乘客序列，且这写区间的并仍是所有区间的并（即被包含的区间不算进来）。如果起始位置被区间并包含，则往下掉到最近的一个选中区间；否则上升到第一个选中区间。然后按照选中的序列往上走，容易发现除了运乘客所需要的能量，我们只花费了哪些没有被区间并覆盖到的位置的能量。

现在我们已经到达 \max r，剩余乘客按照右端点从大到小排序依次进行即可。不会花费除了运送乘客之外的能量。

H.

如果最长链只有一条，那么此链头当根，别的链都挂在根上。容易验证是对的。

如果不止一条，那么如果最短链和最长链长度差 <2 就无解，否则：

设某一条最长链链头（左端点）是 u，那么最短链挂在 u+1，其余链挂在 u。

构造题，我不会。留给队友。

F.

场上至死调不出来，补题一遍过。

每个排列从相邻点前往后连有向边，同一个 scc 里的点对是 fuzzy 的。

查询很何意味，但是一个观察是对于同一个排列，其属于某个 scc 的点一定是一个连续段。所以对每个排列预处理连续段和整段贡献（就是 len(len-1)/2）前缀和。查询时二分找出完整段和散段，完整段前缀和查询，散段暴力算。

B.

乐，补题 15min 想出来了。

询问相当于查询最高的，区间中只有一个数该位为 0 的位置，以及这个数的位置。如果没有这样的位，删掉任何数答案都不会变；否则删掉最高的这样的位对应的那个数，能使答案的这一位从 0 变成 1。

怎么做？线段树维护区间的两个值 a,b，其中 a 代表这个区间中，哪些位“每个数在这一位都是 1”（容易发现等价于区间 \operatorname{and}） ，b 代表这个区间中，哪些位“恰有一个数在这一位是 0”。

考察 update 怎么写，容易发现如果对于大区间，恰有一个数在某一位是 0，一定是两个子区间中某一个恰有一个 0，另一个全是 1。因此，我们有：

\begin{cases}fa_a=ls_a \operatorname{and} rs_a\\fa_b=(ls_a \operatorname{and} rs_b)\operatorname{or}(ls_b \operatorname{and} rs_a)\end{cases}

所有修改容易通过 tag 处理，区间长度是 1 的时候要特殊处理。

查询时，找到这个区间的 b 并取出最高位，然后可以借助区间与的信息在线段树上二分 “[l,r] 内第一个在某一位是 0 的数的位置” 。得到位置后把两边区间的区间与 \operatorname{and} 起来即可。

J.

神秘题。设 S 是所有有相关限制的数的集合。

设 S_1 是只在左边出现的数的集合，S_2 是只在右边出现的数的集合，那么有 S\setminus S1 \setminus S2 是同时出现在两边的数的集合（显然应该有 S_1 \bigcap S_2=\varnothing）。设 a=|S_1|,b=|S_2|,c=|S\setminus S1 \setminus S2|,d=m-a-b-c。d 代表了没有施加限制的数的个数，这些数可以任意选择。

考虑此时的方案数，左边的选择是把 n_1 切成 a+c 个不可空和 d 个可空集，预先给这 d 个集合加上 1 后插板可得 \binom{n_1+d-1}{a+c+d-1}=\binom{n_1+d-1}{m-b-1}。同理右边是 \binom{n_2+d-1}{b+c+d-1}=\binom{n_2+d-1}{m-a-1}。因此答案为：

\begin{align}&\sum_{S_1}\sum_{S_1 \bigcap S_2=\varnothing}\binom{n_1+d-1}{m-b-1}\binom{n_2+d-1}{m-a-1}\\&=\sum_{S_1}\binom{n_2+d-1}{m-|S_1|-1}\sum_{S_1 \bigcap S_2=\varnothing}\binom{n_1+d-1}{m-|S_2|-1}\end{align}

其中 S_1,S_2 其实不是随便取的。容易发现在左边和右边一一连边的情况下，没连到的变其实是 S_1 内部的边和 S_2 内部的边。因此如果把 k 条限制建图，我们不能要求有一条边的两个端点同时出现在同一边。换言之，S_1 和 S_2 都是独立集。

求出独立集集合是简单的，记一个数组 f，对于每条边 (u,v)，将 f_{2^{u-1} \operatorname{or}2^{v-1}} 加 1，然后做高维前缀和，最终 f=0 的那些状态就是独立集。这是好理解的，因为这相当所有 (2^{u-1} \operatorname{or}2^{v-1}) 的超集（同时出现 u 和 v 的点集）都不合法。

额外的，那些没有施加限制的点也不能进入 S_1,S_2，因此还要对每个没有施加限制的点 x，对 2^{x-1} 的超集加 1。

现在求出了 S_1,S_2 的取值范围，我们先预处理对于每个 S_2 的贡献 \binom{n_1+d-1}{m-|S_2|-1}，然后枚举 S_1，发现后面那个 \sum 就是 S_1 的补集子集和。对 S_2 贡献再做一个高维前缀和即可。