=====比赛信息===== * **日期：2020.7.13** * **比赛地址：** [[https://ac.nowcoder.com/acm/contest/5667#rank|传送门]] * **做题情况：lxh(-)，tyx(DF)，gyp(BJ)** =====题解===== ====A - All with Pairs==== ===solved by -, upsolved by tyx=== ===题意=== 给出$n$个字符串，定义函数$f(s,t)=i$，其中$i$是最大的自然数使得$s_{1 ... i} = t_{|t|-i+1 ... |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]$就可以计算答案了 ====B - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====C - Cover the Tree==== ===solved by -,upsolved by lxh=== ===题意=== 给你一棵树，用最少的点到点的路径覆盖整棵树上的所有边（可以重复覆盖） ===数据范围=== 点数 $n \le 100000$ ===题解=== 我们采取一种方案，即把 $cnt$ 个叶子结点按 $dfn$ 序从小到大排，令第 $i$ 个与 $cnt/2+i$ 个连边，奇数个时，在后面加上一个虚拟结点，并将没有连到点的第 $cnt/2$ 个点与根相连。 考虑这种方式的正确性，对于任意一颗子树的根向整个树连的一条边，考虑子树内部 $dfn$ 序是一个区间，则这种方式连边必然会与区间边界有交叉即覆盖了之前所描述的那条边。由这条边的任意性可知，方案正确。但是注意，应保证根的度数不为1。 ====D - Duration==== ===solved by tyx=== ===题意=== 给出一天内的两个时间，问中间差了多少秒 ===数据范围=== 略 ===题解=== 直接算出秒数然后求出差的绝对值即可 ====F - Fake Maxpooling==== ===solved by tyx=== ===题意=== 有一个$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 ====G - ==== ===solved by === ===题意=== ===数据范围=== ===题解=== ====H - Happy Triangle==== ===solved by -,upsolved by lxh=== ===题意=== 按顺序在集合中加入或是删除一些边，在其中询问长为 $x$ 的边能否和还在集合中的边构成三角形。 ===数据范围=== 操作个数 $q \le 200000$，边长 $1 \le x \le 1e9$ ===题解=== 根据三角形的性质我们可以发现，对于一条在集合的边来说，最容易满足的一定是和前驱、后继组成的三角形，且第三条边满足的范围一定为 $ (t2-t1,t2+t1) $。根据这个性质，我们用平衡树维护前驱后继，并在插入时在线段树区间中进行加减，查询时判断是否有区间覆盖查询点即可。由于边长的范围较大，我们需要将用到的值进行离散化处理。$ps:$ 注意这样处理之后，线段树使用的空间是16倍点数。 ====I - Interval==== ===solved by -, upsolved by tyx=== ===题意=== 有一个区间$[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)$往对角线上走，我们可以去掉一些边来把对角线和起点断开，可以轻松发现如果我们把这个图等效成网络流，那么如果有答案答案就是最小割。但是这道题的点数有些多，网络流可能无法通过，这时我们想另一个求最小割的方式——对偶图上求最短路，我们发现这道题的原图非常规则，可以人工看出对偶图的形状，因此我们可以建出对偶图，在题目给出了选择的地方连边，如果有最短路就是答案，如果无法到达终点说明不存在最小割 ====J - ==== ===solved by === ===题意=== ===数据范围=== ===思路=== =====Replay===== 第一小时：tyx发现D是签到题随即A了D题，然后和lxh开始想C，gyp开始想K，但是两道题写的代码均没有通过 第二小时：lxh在写C，gyp发现K题一直没有人过于是转而想B并通过，tyx开始想F发现比较简单但是超时 第三小时：tyx将F中的队列修改成手动实现后MLE，随后gyp发现求gcd需要更快的方法，运用该方法并修改后F题通过，gyp开始想J 第四小时：tyx开始想I，gyp的J题一直超时，lxh修改了几次C但是依然没有通过，gyp发现代码中有一个循环里用了两次变量i，修改后通过 第五小时：tyx想出了I题的正确做法但是没能建出对偶图，交了一个网络流但是WA，gyp重新思考K没有通过，lxh依然没能把C改对 =====总结===== * 要注意循环中的变量问题 * gcd除了可以用log的时间单独求以外还可以用$O(n^2)$的时间预处理1到$n$之间两两之间的gcd