SWERC 2021-2022 部分简要题解

比赛链接：https://codeforc.es/contest/1662。

前言

「部分」「简要」题解。

A - Organizing SWERC

直接判断。

C - European Trip

如果不考虑限制，我们可以直接矩乘。

考虑加入限制后怎么做。

设 \(F_{i,j}^{(k)}\) 为 \(i\to j\) 走 \(k\) 步且满足题目限制的方案数，\(I\) 为单位矩阵，\(D\) 为度数矩阵，\(G\) 为图的邻接矩阵。

那么有：

• \(F_{i,j}^{(0)}=[i=j],F_{i,j}^{(1)}=G\)；
• \(F_{i,j}^{(2)}=\sum G_{i,k}G_{k,j}(i\ne j),F_{i,i}^{(2)}=0\)；
• \(\forall k\ge 2,F_{i,j}^{(k)}=\sum F_{i,l}^{(k-1)}G_{l,j}-F_{i,j}^{(k-2)}(deg_j-1)\)。

前两条应该都很好理解。

对于第三条，前面一部分可以理解为枚举 \(j\) 前面的一个点，后面就相当于减去 \(j\) 前面的第二个点也是 \(j\) 的情况，这时候 \(j\) 前面的一个点不能等于 \(j\) 前面的第三个点。也就是说，设走过的序列是 \(i\to\cdots\to l\to j\to k\to j\)，那么只有当 \(k\ne l\) 时才能被统计进去。而 \(l\) 可以是 \(j\) 连接的任意一条边的另一个顶点，而 \(k\) 此时就有 \(deg_j-1\) 种选择。

把式子写成矩阵相乘的形式，就变成了 \(F_k=F_{k-1}\times G-F_{k-2}\times(D-I)\)。

可以像广义斐波那契数列那样矩乘，不过矩阵内部还套了一层矩阵。

代码：https://pastebin.ubuntu.com/p/88fjTW9HGN/。

D - Evolution of Weasels

手玩可以发现 AB 与 BA、BC 与 AC 之间都可以相互转换。

那么我们可以把所有的 B 放到字符串的最后面，判断它们的奇偶性是否相等。

对于前面的只需要用栈模拟删除的过程，最后判断是否相等就行了。

代码：https://pastebin.ubuntu.com/p/zFhghTB4Mp/。

F - Antennas

可以把式子拆开，变成 \(i\) 与所有 \([i-p_i,i+p_i]\) 之间的点连边。

由于边权都是 \(1\)，所以我们可以 BFS。

复杂度瓶颈在于枚举出边，需要想办法优化这个过程。

由于连的边是一个区间，所以不难想到使用线段树优化这个过程。

讨论一下 \(i\) 与连边的 \(j\) 的大小情况：

• \(j<i\)，那么 \(i-j\le\min(p_i,p_j)\)，即 \(i-j\le p_i,i-j\le p_j\)，移项得 \(j\ge i-p_i,j+p_j\ge i\)。维护区间 \(j+p_j\) 的最大值，在 \([i-p_i,i-1]\) 中对所有 \(j+p_j\ge i\) 的 \(j\) 进行松弛。
• \(j>i\) 的情况类似，转化出来是 \(j-p_j\le i,j\le i+p_i\)。维护区间 \(j-p_j\) 的最小值，在 \([i+1,i+p_i]\) 中对所有 \(j-p_j\le i\) 的 \(j\) 进行松弛。

代码：https://pastebin.ubuntu.com/p/5XS7WGyjY3/。

I - Ice Cream Shop

每一个人存在贡献的都是一段区间，离散化后扫描线一遍即可。

代码：https://pastebin.ubuntu.com/p/SzXSZWVkng/。

L - Il Derby della Madonnina

如果在观察 \(i\) 后能观察到 \(j\)，那么需要满足 \(|a_i-a_j|\le (t_j-t_i)v\)，拆开绝对值就相当于 \(a_i+t_iv\le a_j+t_jv,\ t_iv-a_i\le t_jv-a_j\)。

那么问题就相当于对所有 \((a_i+t_iv,t_iv-a_i)\) 的二元组求 LIS。可以对第一维排序，然后在第二维上跑序列上的 LIS 即可。

代码：https://pastebin.ubuntu.com/p/txRDWrTfBJ/。

N - Drone Photo

如果我们把选出矩形同一行 / 列的两个点由值小的向值大的连边，那么不难发现合法的矩形会有 \(1\) 个点入度为 \(2\)，不合法的矩形会有 \(2\) 个点入度为 \(2\)。并且所有矩形都只有这两种情况。

从小到大加入点，统计出 \(r_i,c_j\) 分别表示这一行 / 列比 \(a_{i,j}\) 小的元素个数，那么在 \((i,j)\) 处就会有 \(r_ic_j\) 种方案使得它入读为 \(2\)。设 \(S=\sum r_ic_j\) 表示所有矩形入度为 \(2\) 的点数的总和，\(C=(\frac{n(n+1)}{2})^2\) 表示所有矩形个数。若有 \(x\) 个矩形合法，那么 \(x+2(C-x)=S\)，解得 \(x=2C-S\)。

代码：https://pastebin.ubuntu.com/p/n8MyHwy6mZ/。