最近文章

雅礼集训 2018 Jan 2nd – 解题报告

A – 串

如果本身就不是回文串,那么答案就是 \(1\);如果本身是的话,考虑找一个分割点使得左右都不是,那么答案就是 \(2\);如果还是没找到,那么就是无解了,因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。

继续阅读雅礼集训 2018 Jan 2nd – 解题报告

「USACO 2018.01 Platinum」解题报告

A – Lifeguards

先可以想到把所有的包含的区间给去掉,然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单,然而 \(k \leq 200\) 就很麻烦。

继续阅读「USACO 2018.01 Platinum」解题报告

BZOJ2707:「SDOI2012」走迷宫 – 题解

主要思路

这题细节真他妈多。

首先,看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了,比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候,从 queue 拿出顶点后先高斯消元一波,把环内的、SCC 之间的(也就是之前求出的 \(dp[u]\))一起放到方程组里进行消元即可。细节看代码吧,真的呕了。

继续阅读BZOJ2707:「SDOI2012」走迷宫 – 题解