P5304:[GXOI/GZOI2019]旅行者 – 题解

主要思路

这个题还蛮神仙的,我很喜欢。

如果是做暴力的话,那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路,我们尝试把这个规模进行缩小,然后只求小规模的全局解(并不是求出所有最短路),然后多次求解之后可以得到全规模的全局解。

继续阅读P5304:[GXOI/GZOI2019]旅行者 – 题解

「国家集训队 2011 扬天」解题报告

A – 等差子序列

因为是个排列,读入时我们可以把已有的数值放在数轴上,发现只要有一个对称即可。我们可以用哈希的思想魔改一下树状数组,维护串和反串的哈希然后判断即可。

继续阅读「国家集训队 2011 扬天」解题报告

「2018泉州国庆集训#3」 – 解题报告

A – 人类基因组

这套题全都是暴力出奇迹系列。

我们枚举一个端点,然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\),然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。

然后用 sb 线段树搞下就行了,太特么傻逼了。

继续阅读「2018泉州国庆集训#3」 – 解题报告

CF1206D:Shortest Path 题解

主要思路

刚开始以为是搞\(\log n\)个基底点,然后双向边上面做事情,最后发现找图上最小环的复杂度非常的高。所以 GG。

正解考虑把问题的规模进行缩小:也就是把一些答案预先特判掉。比如说,如果某一个位上有超过三个点连接,那么环的大小就可以被确定为是\(3\),也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。

再考虑剩下的情况。此时,\(n\)已经缩小了很多,所以我们暴力建图,用 Floyd 跑最小环即可。

继续阅读CF1206D:Shortest Path 题解