[USACO Jan09]安全路径Safe Travel解题报告

题目


分析

首先把最短路径树画出来（由题意最短路径唯一，所以是树）：



其中1是根。我们将树记作T，i的子树记作B。图中，B是绿色点，T-B是红色点。

而1~i最短路上的最后一条边（也就是不能走的边）即i的父亲边。将这条边去掉以后，1~i的最短路长什么样呢？

可以发现，一定是这样的：


即，先从1沿着树边走到T-B中的某个点u，然后再沿着某条非树边走到B中的某个点v，然后再沿着树边走到i。

为什么这样是对的呢？假设这条最短路上最后一个T-B中的点是u，那么1~u[……]

继续阅读

[USACO Dec08]巨大的围栏Largest Fence解题报告

题目


分析

这是道挺有意思的计算几何题……

算法就是：枚举凸包的最左下点B，然后将所有合法的点按相对于B的极角序排序，这样凸包上的点一定是顺序选的。然后记忆化搜索：设状态f(B,p2,p3)代表：最左下点为B，凸包上选的最后一个点为p2，正在测试选不选p3.那么有两种转移：①不选p3，将p3改为p2->p3这条射线沿逆时针旋转卡到的第一个点。②选p3，将p2改为p3，p3改为以p3为起点，方向为p2->p3的射线沿逆时针旋转卡到的第一个点。


这个过程很像是Graham和卷包裹法的某种[……]

继续阅读

[USACO Nov08]玩具toys解题报告

题目


分析

首先，稍有常识的人都会看出，这道题其实就是网络流24题中“餐巾问题”的加强版。

“餐巾问题”的标准做法是费用流：每天拆成两点(i,i’)，然后S向i’连容量Ti（第i天用量），费用0的边，代表当天的脏餐巾。当然还有别的边，但这个是最重要的。

其实“餐巾问题”还有一个枚举+贪心的做法。

假设我们已经确定了一共新买多少餐巾。那我们一开始就把这些餐巾全买下来，然后从第1天到第N天逐天进行模拟：

①如果还有一些新买的餐巾，就用掉它们。

②如果不够，从后往前枚举第i[……]

继续阅读

[USACO Jan07]考试Schul解题报告

题目


分析

这道题比较有意思。

首先，我们不用t和p来表示分数，我们用(x,y)，代表满分为x的卷子得了y分。这样更加直观：把一份卷子视作向量，那么它的“分数率”也就是其斜率。最终的分数率自然就是所有向量之和的斜率。

先考虑一个问题：假如对某个给定的d，现在已经按老师的方法确定了最终的分数率G，那么我们能否改变略去的d份试卷，使得分数率高于G呢？

这时我们可以采用在一类二分答案+网络流/最短路题里常用的思路：对每一份试卷i，算出pi=yi-G*xi（我们把pi称作(xi,yi)[……]

继续阅读

[CF 294D]Shaass and Painter Robot解题报告

题意

有一个n*m的网格，有一个机器人初始在(x,y)，面朝某个斜45°的方向。机器人会一直走，遇到墙就按弹性碰撞规则（就像台球碰到桌子边缘一样）反弹。机器人每走一格，就会将其所在格子染黑。问机器人走几格之后会将整张网格染成黑白相间（或判断这种情况永远不会发生）。

分析

首先有一个结论：边缘上所有该染黑的格子都已染黑，当且仅当整张网格已按要求染成黑白相间。

证法是归纳。假设第一行该染黑的格子都已染黑，那就会发现第二行该染黑的格子都已染黑。因为第一行某个染黑格必定一进一出，即其左下和右下的两格都染黑了。当然也要考虑角上的情况，还有第一行该染黑的最后一个格子只进不出的情况（这时由于它两旁相[……]

继续阅读