151018的测试总结

第一题

【题目及题号】QYQ的字符串 xjoi15T1

【题解】

看到数据范围就可以暴力枚举左界和右界，然后对于每一个子串扫一遍回文位置上不同的字符数量。

小于等于k ans++

大于k不统计

时间复杂度O(n^3)暴力搞过

但是QJC同学说有一种更为机智的解法，类似manacher，可以O(n^2)做。

具体就是找到中间那个字符，然后向两边同时扩展，如果超过k或者超过边界就停止。

【易错点】

我觉得别把这个题想复杂了，别的没什么需要注意的。

第二题

【题目及题号】QYQ的图 xjoi15T2【待填坑】

好难不会。

只是这个题告诉我别卡时，卡时0分。Orz

第三题

【题目及题号】QYQ在艾泽拉斯 xjoi15T3

【题解】

本题其实是要你计算每个连通块所能得到的最大权值，取前min(tot,k+1)个就好。

本题难点在于求每个连通块所能得到的最大权值。

看到数据范围那么大，如果要O(n)做，肯定是会想到记忆化搜索的。

然后就会发现一个问题，本题的有向图中完全可能出现环，那么就可以使用tarjan缩点去掉环，因为在本题的意义下，环是属于一个点的。

现在这就变成了一张有向无环图，发现每个点只会被它指向的点更新，那么深搜下去使用记忆化搜索就保证每个点只会被访问一次。

判断两点属不属于同一个连通块使用并查集。（本题要注意题目中对连通块的新定义，本题中有边相连就属于一个连通块）

【考试ING】

要注意本题涉及到缩点，所以新图中点的映射要注意，尤其并查集要在缩完点之后使用，防止缩点之后更改关系。

本题我偷了个懒，最后一部分取前k+1个的时候，我直接用了优先队列，就要注意特判队列为空的情况。