[赛后总结]G2022 Regular Contest 13总结

实际上这场比赛已经过去一个月了，但是我还是想把我的题解放到博客里面来。
前一次选题被大佬喷太毒瘤，所以这次就成了送分场。
要不他们就不会有心情做我接下来两场的题目了。

天天爱种菜 题解

前言

tag:最小生成树?
原题:[CSP-S JX 2019 T3]网格图

算法1:64分

容易发现题目是在让你求最小生成树。
所以你爱怎么暴力怎么来:)
复杂度$O(nm\log nm)$。

算法2:100分

考虑一整行/一整列的边排序依次加入图中，根据破圈法原理，你会发现你这次加的边最少时当前这一整行/一整列的边的数量减去你在另一方向上已经加入的行数/列数。因此直接做就行了。
注意第一个加入的行和列需要特判，不过大样例已经把这个细节卡掉了，大家应该都会注意到这一点。
复杂度:$O(n+m\log n+m)$

制胡串问题 题解

前言

tag:hash+二分/SA/SAM/后缀树
原题:[NOI 2016 day1]优秀的拆分

算法1:25-30分

暴力check一个子串是否满足$AA$的形式，$BB$同理，然后在中间点乘起来即可。
复杂度:$O(n^3)$
upd:很遗憾的是，做这题的数据有一点水，导致一些同学$O(n^3)$开O2也得了60分。

算法2:60分

考虑对check $AA$的形式做一些优化，这里提供四种做法：
1.直接使用SAM/SA/后缀树。
2.考虑lcp(i,j)表示以$i,j$开始的lcp长度。这都是老套路了
3.暴力建trie树。
4.当然还可以用标算做法RK hash。
复杂度:$O(n^2)$

算法3:100分

正解还是比较困难的。
其实我们会发现我们不需要暴力枚举两个位置之后再去找lcp。可以发现的是，如果我们不仅从两个位置往后找最长匹配,还往两个位置向前找最长匹配，我们可以找到包含这两个位置的所有$AA$的形式
但是我们还需要知道这个字符串的长度$L$,因为我们需要将两个字符串$AA$,$BB$拼起来，我们需要知道它的结束位置。
因此我们先枚举长度$L$，确定位置$s[0],s[L],s[2L],...$，让后我们对相邻两个位置字母相同的都做一遍这个算法。我们可以通过RK hash+二分来做到这一点。然后我们就得到了每个包含两个点且长度为$L$的字符串的起始位置的区间。
接下来就简单了，考虑对起始位置区间和终止位置区间差分前缀和一下即可。这是字符串问题的常见套路。

复杂度:$O((n+n/2+n/3+...+n/n)\log n)=O(n{\log }^{2}n)$
当然你用SAM/SA会少一个log。

迷宫 题解

搬题人:Panda_hu

前言

tag:提交答案-构造最优化方案问题
原题:我也不知道我从哪里翻出来的:)然后我还瞎改了一下。
本来想搬旷野大计算的，但是害怕被喷死。
这题算是提交答案中非常简单的一道题目了，希望大家玩的开心。

子任务1

手玩即可。
如果你懒得自己走迷宫写个暴力也行:)
期望得分:$10$。

子任务2

感觉地图很大?
但是点数很少…仔细看一下数据你会发现全在$8\times 8$的矩阵以内。因此我们同样手玩/写暴力。
期望得分:$10+20$。

乱搞1

注意到只要你的方案合法，你就至少能够得到10%的分数。
因此每个答案先交个起点上去:)
期望得分:$1+2+2+2+3$

乱搞2

这种题目明显可以用随机算法来做啊:)
试着随机游走$100$次取最优解交上去。
期望的得分:我没试过。

乱搞3

这题出的比较失败的关键原因就在于如果你dfs按照类似上左下右这样的顺序跑通常都能够得到满分或接近满分的成绩。不过没关系，出题人就是想把这题的分送给大家的:)

你们的乱搞

??

子任务3

观察数据，你会发现数据呈现一种横竖道路交错的形式。
如果你用代码检验一下，你会发现这个数据的道路没有环。

因此dfs一下即可。
期望得分:$10+20+20$

子任务4

接下来的数据地图很小，你可以用一个程序把地图可视化下来观察。
这个子任务的地图是这样的:

我们可以这样走:

然后你写一个代码模拟一下即可。
期望得分:$10+20+20+20$

子任务5

大致地图:

显然地图被分为了几个小矩阵，每个矩阵的行数都是奇数，列数不定。
如果列数为偶数:

如果列数为奇数:

但是我们需要特判列数为1的情况，我们不能够进入这些矩阵，但是如果是在终点位置的列数为1的矩阵是可以进入的。
期望得分:$10+20+20+20+30=100$

总结

大家一定AK地很开心:)