LGR-262 题解

· · 算法·理论

A:

设最后每一行所有数和均为 s ，每一列所有数和均为 t ，则有 s+s=a+b+c+d,t+t=a+b+c+d ，所以 s=t 。

假设最后矩阵为 [x,y],[z,w] ，则有 x+y=s,x+z=t ，又因为 s=t ，所以 y=z ，同理有 x=w 。

所以有解时必然有两对数相等，即 a,a,b,b 的形式，由矩阵 [a,b],[b,a] 得这样的条件下必然有解。

B:

木棍拼成面积严格大于零的多边形，等价于所有木棍总长度严格大于最大长度的两倍。

先将所有木棍按长度从小到大排序，那么有结论：如果某个 k 有解，则只考虑选择连续的 k 根木棍也有解。

证明：如果选择的木棍不是连续的一段，假设选择的木棍最大编号为 d ，则可以调整为选择编号为 d-k+1 到 d 的木棍。可以发现这样最大长度不变，同时不会使得总长度变小，所以如果原来可行则调整后仍然可行。

枚举最长的木棍，然后二分求出最少需要选择多少根木棍才能使得总长度严格大于最大长度的两倍，连续一段木棍总长度可以用前缀和计算。假设最长的木棍是长度从小到大排序后的第 p 根，最少需要选择 m 根木棍，那么对于 [m,p] 之间的所有 k 都有解。

将上述过程求出的所有答案区间取并即为最后的答案。对于计算区间的并，可以使用差分和前缀和求出包含每个位置的区间数量。

C:

首先可以用单调栈求出两个传送门连向的星球，然后有结论：如果对于每一个没有传送门连向自己的星球，都只保留目标星球大小比较小的传送门，那么所有星球能到达的星球集合全部不变。

证明：假设目前处于 i 号星球，该星球上的传送门连向 l_i,r_i 号星球，其中 l_i 号星球大小比较小，那么对于所有 l_i<j<r_i ，都有 p_j<p_{l_i} ，所以 l_i号星球上有一个传送门连向 r_i 号星球。进入 l_i 号星球之后重复上述过程，直到连向 r_i 号星球的传送门被保留为止。这样就可以只通过被保留的传送门从 i 号星球进入 r_i 号星球，于是所有没有被保留的传送门都可以被代替。

考虑被保留且不连向自己的传送门，可以发现除了大小最大的星球以外，每一个星球上都恰好有一个传送门连向大小更大的星球，所以星球和这些传送门构成一颗树。对于每次询问求出所有关键点在树上的最近公共祖先，其深度即为答案。

D:

显然将选择的行和列的所有方格涂黑时不美观度最小，此时不美观度为剩余方格中符合题意的四元组数量。

假设剩余行和列的集合为 S,T ，设数量为 g(S,T) ，若 |S| \leq 1 或者 |T| \leq 1 则 g(S,T)=0 ，否则找到最大的编号 x \in S 和最大的编号 y \in T ，将四元组按是否包括 x,y 分为两类。

首先考虑不包括 (x,y) 的四元组，数量为 g(S-x,T)+g(S,T-y)-g(S-x,T-y) ，所有四元组恰好被统计一次。

然后考虑包括 (x,y) 的四元组，设数量为 h(S,T) ，若 |S| \leq 1 或者 |T| \leq 1 则 h(S,T)=0 ，否则找到最小的编号 a \in S 和最小的编号 b \in T ，将四元组按是否包括 a,b 分为两类。

对于不包括 (a,b) 的四元组，数量为 h(S-a,T)+h(S,T-b)-h(S-a,T-b) ，所有四元组恰好被统计一次。

对于包括 (a,b) 的四元组，直接检查即可。

每个状态只会指向集合大小更小的状态，所以不会成环。

E:

首先判断一个终止状态是否可以被达到：

因为所有点初始颜色不同，所以终止状态下根的颜色对应唯一的来源点，所以必然有从该点开始向上染色直到根的一系列操作。

因为染色会覆盖之前的颜色，所以可以先完成这一系列的操作，然后把根删除后转化为规模较小的子问题。

转化后的子问题中，初始颜色可以相同，但是相同颜色的点全部在一条链上，而取链上深度最小的点作为来源点可以保证所有边的经过次数同时取到最小值。

最后判断每条经过次数和容量的大小关系即可判断单个状态是否可行。

考虑模拟上述过程，每个点都会有一个颜色序列，代表全过程中这个点的颜色变化。每条边也会有一个颜色序列，代表全过程中通过这条边染色的所有染色操作。

点的颜色序列不会存在相邻且相同的元素，但是边的颜色序列有可能会（目标点颜色被反复覆盖，可以手动模拟几次理解）。

每条边的颜色序列可以由起点的颜色序列生成，具体方式为：将每个元素重复一次或多次后按原来的顺序拼接。

注意起点初始颜色和最终颜色可以不出现。

每个点的颜色序列由连向该点的所有边的颜色序列生成，具体方式为：将这些边的颜色序列多路归并。

注意保证点的颜色序列没有相邻且相同的元素。

考虑子树dp，设 dp_{i,j} 为只考虑 i 的子树，点 i 的颜色序列长度为 j 的方案数，子树内任意一点最终颜色不同或颜色序列不同都视为不同方案。

假设有 m 条边连向 i 号点，容量为 c_1,...,c_m ，颜色长度为 b_1,...,b_m ，对应起点颜色序列长度为 a_1,...,a_m 。

则点 i 颜色序列长度（不考虑初始颜色）为：

\sum(a_i+b_i)

钦定归并后相邻且相同的元素后容斥，可得方案数为：

\sum_{t_i \leq b_i} \prod \binom{a_i+b_i-1}{b_i} (-1)^{t_i} \binom{b_i}{t_i} \frac{(\sum (a_i+b_i-t_i))!}{\prod(a_i+b_i-t_i)!}

最后处理点 i 的初始颜色和最终颜色，颜色序列长度为 0 需要特判。

dp过程中维护 a_i+b_i 和 t_i 的和，每个子树中分开枚举 b_i ，复杂度 O(nk^4) ，常数很小可以通过，也可以用二维卷积优化到 O(nk^3) 。

F:

因为 M_1,M_2 是奇数，所以存在逆元，所以整除时可以实现除法操作。任意数减去自己对 M_1 取模后的余数后一定能被 M_1 整除，所以可以实现除以 M_1 下取整。

首先考虑判断 v_0 和 C 的大小关系，当 C-M_1 \leq v_0<C+M_1 时求 \frac{v_0-C+M_1}{M_1} 即可。

然后考虑原题，发现 M_1 和 M_2 很接近，于是可以用类似 v_0=v_0- \lfloor \frac{v_0}{M_1} \rfloor M_2 的运算，每次使 v_0 的取值范围减小约 99\% ，然后加上 M_2 的倍数调整，几次后就能使得 M_2-M_1 \leq v_0<M_2+M_1 ，此时只需判断大小关系。

最后考虑本题，如果 M_1<M_2 ，则可以连续除以多次 M_1 转化为 M_1>M_2 的情况，如果 M_1>M_2 ，则可以将 M_2 放大若干倍使得每次 v_0 至少减半，最后二分 p 判断 v_0 和 pM_2的大小关系。