「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 题解

[Fortuna OJ]Jul 6th – Group B 解题报告

A – 调整 Tweak

这道题我在考场上打了一个错解,还骗到了 30 分。

正常的思路是:在最短路图上找到几个边进行修改。然而,最优的解决方案并不一定出现在最短路图上的边上,也可以通过修改次优边进行解决。所以,这道题其实跟最短路没什么太大关系,即使后面会用到 Djisktra 来求最短路。

我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份,然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\),可以生成一个副本来连接下一层的目标点,也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\),当最后求最短路时,经过这样的一条边可以被认为是修改一条边,且,这个边是单向向下的,所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路,然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。

继续阅读[Fortuna OJ]Jul 6th – Group B 解题报告