CVBB ACM Team

• 日期：2020.7.13

• 比赛地址： 传送门

• 做题情况：lxh(-)，tyx(DF)，gyp(BJ)

给出$n$个字符串，定义函数$f(s,t)=i$，其中$i$是最大的自然数使得$s_{1 \ldots i} = t_{|t|-i+1 \ldots |t|}$，也就是说$s$的前缀和$t$的后缀相同，求$\sum_{i=1}^n \sum_{j=1}^n f(s_i,s_j)^2$，结果对998244353取模

$1 \le n \le 10^5$，$1 \le |s_i| \le 10^5$，$\sum |s_i| \le 10^6$

我们可以先用哈希把所有后缀的信息存下来，然后计算每一个前缀和多少个后缀相同，但是这样会计算除了答案的信息，例如字符串$aba$，其中前缀$a$和$aba$都被计算了一遍，所以我们需要去重。这里我们只需要对每一个字符串算出KMP算法中的$Next$值，然后令$cnt[Next[i]] -= cnt[i]$就可以计算答案了

给出一天内的两个时间，问中间差了多少秒

略

直接算出秒数然后求出差的绝对值即可

有一个$n \times n$的矩阵，其中$A_{ij} = lcm(i,j)$，现在给出$k$，要求这个矩阵中每个$k \times k$的矩阵种最大值的和

$1 \le n,m \le 5000$，$1 \le k \le min\{n,m\}$

求最大值可以直接二维单调队列用$O(nm)$的时间求出，瓶颈在于如何预处理，如果用$O(nm \log n)$的时间会超时，所以需要用递推的方式用$O(nm)$的时间求出gcd

有一个区间$[1,n]$，现在可以进行操作把区间$[l,r]$变成$[l-1,r],[l,r-1],[l+1,r]$或$[l,r+1]$，但是一旦区间变成$[l,l]$就不能再变，现在有$m$个选择，你可以花费$c$把某一个区间$[l,r]$向$[l-1,r]$或$[l,r-1]$的操作禁止，问能不能完全避免把区间变成$[l,l]$，如果能，最小化费是多少

$2 \le n \le 500$，$0 \le m \le n(n-1)$，$1 \le c \le 10^6$

我们可以把每一个区间$[l,r]$想象成网格上的一个点，那么这道题的情形可以等价于从$(1,n)$往对角线上走，我们可以去掉一些边来把对角线和起点断开，可以轻松发现如果我们把这个图等效成网络流，那么如果有答案答案就是最小割。但是这道题的点数有些多，网络流可能无法通过，这时我们想另一个求最小割的方式——对偶图上求最短路，我们发现这道题的原图非常规则，可以人工看出对偶图的形状，因此我们可以建出对偶图，在题目给出了选择的地方连边，如果有最短路就是答案，如果无法到达终点说明不存在最小割

第一小时：

第二小时：

第三小时：

第四小时：

第五小时：