2024.2

1.gym103260H Excluded Min

先思考怎么转化原问题，如何 check \(F(S)\geq x\) 呢。如果 \(S\) 中 \(<x\) 的数 \(\geq x\) ，显然就合法了；否则的话，我们操作过程肯定会出现一个 \(x\) ，而根据题目的过程，出现一个 \(x\) 后 \(x\) 就不会消失了，所以说相当于是 check \(F(S)\geq x+1\) 了。

于是我们找到最大的 \(t\) ，使得 \(S\) 中 \(<t\) 的数 \(\geq t\) ，则 \(F(S)=t\) 。

思考怎么计算答案，我们离线下来，把每个询问看成一个二维平面上的点 \((l,r)\) 。从大到小枚举 \(t\) ，动态修改这些点对应的 \(F\) ，修改相当于是对所有 \(a_x=t\) ，把 \(l\le x\le r\) 的部分的 \(F\) 减去 \(1\) ，然后再找到所有 \(F\) 值 \(\geq t\) 的点，计入答案并删掉。直接做是困难的，因为问题形如对矩阵修改，查最值。

怎么办呢？你注意到一个显然的性质：若一个区间 \([l_1,r_1]\) 被区间 \([l2,r2]\) 包含，那么 \(F([l_1,r_1])\le F([l_2,r_2])\) 。如果询问区间两两没有包含关系，那问题就是容易的了：这些区间一定是 \(l,r\) 同时递增的，于是问题就形如对序列修改，查最值了，容易线段树解决。

回到原问题，我们就尝试只维护这些没有被其它区间所包含的区间，我们称这些区间是好区间。等到一个区间得到答案，被删掉以后，再把新的好区间加进去即可。具体实现时，我们一开始就把所有区间以 \(l\) 从小到大排序，若 \(l\) 相同再按 \(r\) 从大到小排序，我们维护的线段树就都以区间的编号为下标进行维护。维护两棵线段树，一个是当前的好区间对应的 \(F\) ，一个是剩下的区间的 \(r\)。寻找新的好区间时，我们记删掉的区间编号为 \(x\) ，下一个好区间编号为 \(R\) ，上一个好区间的右端点是 \(lim\) 。利用第二棵线段树，找到 \([x,R]\) 中 \(r\) 最大的记为 \(y\) ，若 \(r_y>lim\) ，说明这是一个新的好区间，令 \(R:=y\) ，否则结束这个过程。

加入新的好区间时要算它此时的 \(F\) ，可以 BIT 解决。总复杂度 \(O(n\log n)\) 。

2.gym103329I Typing Contest

先让 \(t_i\) 乘上 \(100\) ，令 \(X=\sum t_i\) ，把权值写成 \(\sum s_i(10000-t_i(X-t_i))\) 。尝试枚举 \(X\) ，就变成了经典的 01 背包问题。复杂度大概是 \(O(5000n^3)\) 的，不能通过。

乍一看是不能优化的，因为权值的计算中 \(X\) 是关键的，无法进行有效的变换。于是我们尝试寻找 \(X\) 的上界。有结论：\(X\le 100\sqrt{n+2}\) 。

原因是，你考虑选取的物品一定有 \(t_i(X-t_i)< 10000\) ，否则的话，它本身权值是非正的，还让 \(X\) 更大了，删去它是更优的。对这些不等式求和，我们有 \(X^2-\sum t_i^2<10000k\) ，其中 \(k\) 是选取的物品个数。 再对 \(t_i^2X-t_i^3<10000t_i\) 求和，我们有 \(\sum t_i^2<10000+\frac{\sum t_i^3}{X}\le 10000+(\max t_i)^2\le 20000\) 。

于是 \(X^2<10000k+\sum t_i^2\le 10000(k+2)\le 10000(n+2)\) ，\(X\le 100\sqrt{n+2}\) 。

最后复杂度是 \(O(5000n^2)\) 的。

3.gym102978F Find the LCA

考虑枚举集合 \(S\) ，如何计算 \(lca(n-1,n)\) 的子树内点集为 \(S\) 的方案数。先算掉 \(|S|=n\) 的情况，之后 \(n-1\) 和 \(n\) 必须在 \(S\) 里，\(1\) 不能在 \(S\) 里。

发现方案数是只和 \(|S|,\min\limits_{x\in S}x\) 有关的：子树外的点选取 \(p_i\) 的方案数就是 \((n-|S|-1)!\) ，子树内的连边方案数通过找规律发现是 \(\frac{\max(2,(|S|-1)!)}{2}\) 。最后子树的根需要往外连边，方案数便是 \(\min\limits_{x\in S}x-1\) 。

于是如果没有 \(\min\limits_{x\in S} x\) ，直接计算 \(\prod ([i\le n-2]+A_ix)\) 即可，可以分治 NTT 解决；而现在考虑把这个 $\min $ 融合进我们的过程：在分治的每个节点维护两个多项式，一个代表上面的连乘式子 \(A_i\)，一个是最后想要的式子 \(B_i\) ，显然 \(A_p=A_{l}A_{r},B_p=B_{l}A_{r}+B_{r}\) 。复杂度 \(O(n\log ^2n)\) 。

4.gym102443E Hide-and-Seek for Robots

首先可以观察到，\(U/D\) 和 \(L/R\) 是不会同时攻击到对方的。所以我们可以分开看 \(U/D,L/R\) 的性质，以 \(U/D\) 为例。把所有 \(U\) 的攻击范围画出来，构成了一个轮廓线把图分成两部分，然后你发现在这个轮廓线上 \(U/D\) 皆可，上面只能 \(U\) ，下面只能 \(D\) 。设轮廓线在第 \(i\) 列时的处于的行数为 \(d_i\) ，则 \(|d_i-d_{i+1}|\le 1\) 。对这个轮廓线做 dp 即可，不合法的 \(U/D\) 一定能通过一次旋转变成合法的 \(L/R\) 。复杂度 \(O(n^2)\) 。

5.gym102341F Flaaffy

首先有一个区间 dp 的思路，就是记 \(f_{i,j}\) 表示当前显示的是 \(i\) ，结果在 \((i,j]\) 的最小费用，\(g_{i,j}\) 同理。但这个 dp 显然是不优的， 注意到需要的费用是很小的，有一个上界是 \(5\log N\) (\(N=10^5\)) ，实际测试中可以发现费用都在 \(K=42\) 以内。 于是我们转而记 \(l_{i,c}\) 表示最大的 \(j\) 使得 \(f_{i,j}\le c\) ，\(r_{i,j}\) 同理。

如何转移呢，以 \(l_{i,c}\) 为例，考虑枚举 check 的点 \(t\) ，令 \(d=dis(i,t)+1\) ，我们需要 \(r_{t,c-d}\le i+1\) ，然后用 \(l_{t,c-d}\) 去更新 \(l_{i,c}\)。这样直接做是 \(O(KN^2)\) 的，但我们可以优化。首先注意这里我们不需要保证 \(t>i\) ，因为 \(t\le i\) 的时候 \(l_{t,d}\) 一定不优。

先枚举 \(c\) 。枚举 \(t\) 以及 \(d\) ，把 \((d,t)\) 这个三元组存进 \(r_{t,c-d}-1\) 这个位置的 vector 中，表示从这个位置开始就能产生贡献。存完了之后就开始从左往右扫，设 \(q_{i,S}\) 表示 \(i\) 这个数在 \(S\) 中的位全变成 \(0\) 得到的数。对于扫到的二元组，枚举 \(S\) 满足 \(popcount(S)=d-1\) ，用 \(l_{t,d-c}\) 更新 \(w_{q_{t,s},s}\) 即可。再更新当前的 \(l_{i,c}\) ，就是枚举 \(S\) ，用 \(w_{q_{i,S},S}\) 更新即可。

6.P10064 [SNOI2024] 公交线路

设 \(S_i\) 表示叶子 \(i\) 一步到达的点集，则 \(S_i\) 需要两两有交。不难发现这是充要的。

由于 \(S_i\) 都是树上的某个联通块，则所有 \(S_i\) 的交一定非空，且构成了一个联通块。考虑点-边容斥，以点为例，我们要计算所有 \(S_i\) 都包含一个点 \(x\) 的方案数。首先两端都是非叶子的路径，以及不跨过 \(x\) 的路径可以任意取，不影响结果。然后考虑进行容斥，钦定一些叶子的 \(S_i\) 不包含 \(x\) ，设第 \(i\) 棵子树内共有 \(s_i\) 个叶子，其中有 \(p_i\) 个可取叶子， 第 \(i\) 棵子树外有 \(c_i\) 个非叶子，则剩下的路径有 \(\sum p_ic_i+\sum\limits_{i\neq j}p_ip_j\) 个路径是能取的。

用背包来算这个东西，枚举每个子树，有 \(f_x(-1)^{s_i-y}\tbinom{s_i}{y}2^{y(c_i+x)}\rightarrow f'_{x+y}\) 。

但直接做是 \(O(n^3)\) 的，考虑优化。取 \(1\) 为根后，若只考虑 \(x\) 除了其父亲外的子树进行转移，容易发现是 \(O(n^2)\) 的。而我们可以不对最后这棵子树做容斥，直接计算答案：\(\sum f_i(2^{i+c}-1)^s\) 。

边也是类似的，其实还要简单一些，相当于只有两个子树。

7.uoj goodbye

A 直接树形 dp 即可。

B 考虑一个 \(O(n^2)\) 的做法(先当成 \(n,m,L\) 同阶) 。看到字典序最大，尝试逐位确定，变成 check 一个终止序列 \(b\) 是否合法。如果一个操作 \(j\) 涉及的所有位置 \(l_j\le i\le r_j\) 都满足 \(x_{j,i}\geq b_i\) /已被覆盖，那就让它做最后一个操作，并覆盖 \([l_j,r_j]\) 。循环地找下去。最后如果所有位置都有 \(a_i\geq b_i\) /已被覆盖，说明 \(b\) 是合法的。

发现这个是可以直接优化的。我们确定 \(b_i\) 时， 首先 \(i<l_j\) 的操作是不需要管的；我们优先去选 \(r_j<i\) 的操作，直到不得不选满足 \(l_j\le i\le r_j\) 的操作。在剩下这些操作中找合法前提下 \(b_i\) 最大的即可。可以发现 \(r_j<i\) 部分的操作结果基本不会改变，只可能是加入一些 \(r_j=i-1\) 的区间时产生了连锁反应，类似于 bfs 找到新的能取的操作即可。复杂度线性。

C 思考怎么 check 一个状态是否合法。把偏序关系形成的树画出来。观察 \(S\) 中 \(c_i=0\) 的部分一定满足 \(p_i\) 单调递增，否则直接调整即可。

思考 \(c_i=1\) 的部分会带来什么限制。令 \(q_i\) 是子树中除 \(i\) 自身外 \(p_v\) 的最大值，那么若有一个 \(c_j=0\) 且在 \(S\) 中的 \(j\) 满足 \(q_i<p_j< p_i\) ，那交换 \(p_i,p_j\) 是更优的。

感觉后面的 dp 就不难了阿。复杂度 \(O(n\log n)\) 。

D 咕一下。

8.2.9T2

题意就是，每次询问给出 \(d,k\) ，令 \(c_i=(a_i+d)\mod m\) ，求 \(c\) 这个串 \(k\) 小后缀的位置。

考虑建出 height 数组的广义笛卡尔树。把询问按 \(d\) 排序，思考随着 \(d\) 变化，我们的 SA 数组如何变化，你发现相当于是在建出的树上把某些点的最后一个儿子换到了第一个。而这个换位操作的总次数是 \(O(n)\) 的。每次相当于是把 SA 数组相邻的两段区间进行交换，使用文艺平衡树维护即可。一个问题是每次操作时如何在 SA 中定位，我们维护一个序列 \(rk_i\) 表示一开始 rank=i 的后缀现在的排名是多少，每次操作时 rk 的变化就是两次区间加，于是用线段树维护即可，算出 rk 就能进行定位了。

9.qoj2563 Curly Racetrack

首先注意到，若只是看是否闭合，横向的水管是和竖向独立的。

只是在判断是否为好格子的时候横竖会有联系。一个格子是特殊格子，等同于它两个方向都只接了一条水管。

于是现在以横向的为例，我们会尽量让所有格子都只接一条水管。但有时候是无法实现的。

我们枚举每一行，已出现的水管把这一行划分成若干段，两段之间是独立的。设只往右边连的是状态 \(1\) ，只往左边连的是状态 \(0\) 。不确定的为状态 \(2\) ，直接把状态 \(2\) 的看做坏格子。那不能出现相邻的 \(0\) /相邻的 \(1\) ，否则就不闭合了。状态 \(2\) 是一定合法的，因为它一定能根据左右两边的接法调整成合法的状态。

如果左边的状态为 \(X\) ，右边的状态为 \(Y\) ，两端的列数之差为 \(c\) 。那如果 \(c\) 和 \(X\oplus Y\) 的奇偶不同，则说明这一段中间一定有至少一个 \(2\) ，否则直接 \(0,1\) 交替的填即可。观察题意给出的三类限制，A类是不能产生贡献的格子，B类是必须当好格子，C类无所谓。一开始我们认为所有 B,C 类格子都是好的。当前段中若有 A 类的话直接让其为状态 2 即可；否则就得选择一个 C 类格子降级为坏格子，让答案减 1。

竖着类似的再做一遍。但是你发现这样会算小答案。原因是有些 C 类格子的贡献被扣了两次，但实际上只用扣一次，要加回来。所以要让扣两次的 C 类格子尽量多，这就是经典的二分图最大匹配，直接计算即可。复杂度 \(O(nm\sqrt{nm})\) 。

10.qoj8240 Card Game

可以把问题转化成：从 \(l\) 跳到 \(r\) ，若当前 \(f_u\le r\) 就跳到 \(f_u\) 否则跳到 \(u+1\) 。

考虑直接用主席树维护答案，从大往小计算，先让 \(T_i\) 复制 \(T_{fa_i}\) 的信息，然后把 \(T_{i+1}\) 中 \((i,fa_i)\) 这一段加 \(1\) 并复制到 \(T_i\) 上。

区间加可以用标记永久化实现，于是复杂度 \(O(n\log n)\) 。

可以写的很帅的。

int cop(int l,int r,int z){int u=++cn;ls[u]=l,rs[u]=r,tg[u]=z;return u;}
int ko(int p1,int p2,int l,int r,int x,int y,int z1=1,int z2=0){
    z1+=tg[p1],z2+=tg[p2];
    if(x<=l&&r<=y)return cop(ls[p1],rs[p1],z1);
    if(y<l||x>r)return cop(ls[p2],rs[p2],z2);
    int mid=(l+r)>>1;
    int L=ko(ls[p1],ls[p2],l,mid,x,y,z1,z2),R=ko(rs[p1],rs[p2],mid+1,r,x,y,z1,z2);
    return cop(L,R,0);
}

11.qoj8232 Yet Another Shortest Path Query

神了。考虑平面图的性质：\(m\le 3n-6\) 。所以度数最小的点度数不超过 \(5\) 。我们每次删掉这个度数最小的点，直到把图删空。然后把每条边定向： 若 \(u\) 比 \(v\) 先删则连 \(u\rightarrow v\) 。

\(u\) 走向 \(v\) 时，若方向是 \(u\rightarrow v\) 则写下 \(R\) ，否则写下 \(L\) 。你发现从 \(s\) 到 \(t\) ，第一条是 R 的情况可以直接处理掉：枚举 \(s\) 的出边，即可转化成只能走两条边的询问。同理，最后一条是 L 又能处理掉。只需要考虑 LLR 和 LRR，而 LLR 看成是从 \(t\) 出发就成了 LRR，所以只用考虑 LRR。把询问离线下来，把 \(s\) 相同的询问一起处理。枚举 \(s\) 的一条入边，再枚举两个 R 的走法，用桶记下来答案，询问就好处理了。这部分复杂度是 \(O(5^2m)\) 的。但我们还需要快速的弄 \(10q\) 个两条边的询问。还是同样的处理掉第一个为 R/最后一个为 L，来考虑 LR ，离线即可。

复杂度大概就是 \(O(5^2(m+q))\) 的。

12.CF786D

一开始的想法是换根的同时直接维护 \(s(rt,x)\) 的大小关系，但发现这是困难的。

树上的数点问题，尝试点/边分治，这里边分治要方便一些。对于当前取的这条中心边，我们统计一端的点 \(z\) 对另一端的询问 \((x,y)\) 的贡献。你发现这个时候，\(s(x,z_1)\) 和 \(s(x,z_2)\) 的大小关系是和 \(x\) 无关的：因为 \(s(x,z)\) 可以拆成 \(s(x,t)\) 和 \(s(t,z)\) ，其中 \(t\) 是中心边的端点。 \(s(x,t)\) 是固定的，所以只和 \(s(t,z)\) 有关。 按 \(s(t,z)\) 对 \(z\) 排序可以直接建 trie 树实现。

排序完之后，处理询问就是直接二分，转化成快速对 \(s(x,z)\) 和 \(s(x,y)\) 进行比较，利用哈希+二分算 lcp ，由于需要求 k 级祖先，这是单次 \(O(\log^2n)\) 的。总复杂度 \(O(n\log^4 n)\) 。

做得有点直接，还有优化空间。对于询问我们先比较 \(s(x,t)\) 和 \(s(x,y)\) ，如果它们 \(lcp<|s(x,t)|\) ，说明大小关系已经固定了；否则， \((x,y)\) 这条路径删掉前 \(|s(x,t)|\) 这一段，（也就是 \(x\) 往前跳），只要找到它和 trie 树的 lcp，就容易计算答案了。

还是二分，可以 \(O(\log n)\) 算出路径前 \(mid\) 条边的哈希值，然后看这个哈希值是否在 trie 的某个节点存在即可。可以 unordered_map 实现。复杂度 \(O(n\log^3n)\) 。

13.P10062 [SNOI2024] 拉丁方

先思考 \(C=n\) ，建立二分图，左边代表列，右边代表值，若值 \(j\) 没有在列 \(i\) 中出现就连边 \((i,j)\) ，跑最小边染色即可，第 \(i\) 种颜色代表第 \(R+i\) 行。显然此时左右两边的点度数都是 \(n-R\) ，所以合法。

进一步思考 \(C<n\) 。尝试先把右边 \(R*(n-C)\) 的区域填了，从而转化成 \(C=n\) 的问题。你发现是类似的，建立二分图，左边代表前 \(R\) 行，右边代表值即可。需要用 \(n-C\) 种颜色给这个二分图边染色，所以若有点度数 \(>n-C\) 就不合法了。第 \(i\) 种颜色代表第 \(C+i\) 列。

复杂度 \(O(Tn^3)\) 。