2024.6.17
2024.6.17
T1
题面
有一个 \(n\) 个节点的联通图给出一个 \(n\times n\) 的矩阵，其中 \(a_{i,j}\) 表示节点 \(i\) 与节点 \(j\) 之间的最短路，求原图的边权之和的最小值，如果不合法，输出 \(-1\)
\(n\le 300,1\le a\le 10^9\)
解法
我们先利用 \(floyd\) 跑一下，如果存在 \(a_{i,k}+a_{k,j}<a_{i,j}\)，则不存在这样的图。
我们考虑初始时，所有点对之间都有边，并且边权等于最短路径的长度，此时构造出来的图 \(G\)，一定满足要求。
我们考虑如何尽量多的去掉图 \(G\) 上的边，由于没有负权，因此如果 \(a_{i,k}+a_{k,j}=a_{i,j}\)，那么 \(a_{i,j}\) 这条边就可以去掉，因为这条路是多余的。
最后剩下的边权和，就是答案。
方法
- 贪心
T2
题面
输入两个01字符串 \(A\) 与 \(B\),求 \(A\) 中所有长为 \(|B|\) 的字串与 \(B\) 的汉明距离最小值。
汉明距离：两个相同长度字符串对应位置字符不同的数量
\(1\le|B|\le|A|\le10^6\)
解法
我们考虑算卷积，将 \(B\) 翻转并在后面加 \(0\) ，\(S\) 卷积相乘。
结果的第 \(P\) 位的值为 \(\sum_{j=0}^PB_jA_{P-j}=k\) ，对于只有 01 的串，只有 \(1\times 1=1\) ，因此 \(k\) 代表 \(B_j\) 同 \(A_{P-j}\) 中有多少位同时是 \(1\)，也就是说串 \(B_0\) 到 \(B_P\)，与串 \(A_P\) 到 \(A_0\) 中 \(1\) 的匹配数量。如果利用 \(FFT\) 算卷积，则是 \(\mathcal O(n\log n)\) 的 。
同样，我们将 \(0\) 换成 \(1\) ，\(1\) 换成 \(0\)，再做一次卷积，这样可以求出有多少 \(0\) 和 \(0\) 是匹配的。
最后用 \(|B|\) 减去所有匹配中的最大值即可。
方法
-
卷积
-
卷积的两项为 \(\text{bool}\) ，乘法与 \(\operatorname{and}\) 运算等价，相当于同时为 \(1\) 的个数
-
先反转，再卷积，相当于对应位置相乘
-
T3
题面
一个数轴上，小 A 可以从 \(i\) 位置跳到 \([i+1,i+z]\)，每到一个点（除起点）都会花费 \(a\) 元，数轴上有 \(n\) 个特殊的点，当小 A 跳到\(c[i]\) 位置的时候会挣 \(m[i]\) 元，小 A 从 \(x\) 到 \(y\)，求最后最多有多少钱
\(1\le m[i],a,z\le 10^9,1\le n\le 10^5,0\le x\le c[1]<\cdots<c[n]\le y\le 10^9\)
解法
易得方程 \(dp[i]=\max_{j<i}\{dp[j]-\lceil\dfrac{c[i]-c[j]}{z}\rceil a\}+m[i]\)
可化为 \(dp[i]=\max_{j<i}\{dp[j]+\lfloor\dfrac{c[j]}{z}\rfloor a-[c[i]\bmod z>c[j]\bmod z]a\}+m[i]-\lfloor\dfrac{c[i]}{z}\rfloor\)
此时可以对 \(c[i]\bmod z\) 分类讨论，于是用线段树优化DP可以求解，时间复杂度\(\mathcal O(n\log n)\)
方法
- 线段树优化DP
T4
题面
给定一个字符串 \(S\)。
共 \(m\) 个询问，每次形如 i l r ,求以第 \(i\) 个位置为起点的后缀，和起点位置在 \([l,r]\) 内的所有后缀的最长公共前缀的长度,以及选到这个最优解的位置，如有多个解，求这个后缀的字典序最小。
\(1\le m,|S|\le 2\times 10^5,1\le i\le |S|,1\le 1\le r\le |S|\)
解法
后缀数组对所有后缀排序，用 ST 表维护高度高度数组，以求LCP，由于限制了 \(sa[i]\in [l,r]\)，所以在拍好序的后缀上建立可持久化线段树，每次加入 \(rk[i]\) 的后缀，最后查询即可
方法
-
后缀数组
-
ST表
-
可持久化线段树