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

题目


分析

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

算法就是:枚举凸包的最左下点B,然后将所有合法的点按相对于B的极角序排序,这样凸包上的点一定是顺序选的。然后记忆化搜索:设状态f(B,p2,p3[……]

继续阅读

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

题意

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

分析

首先有一个结论:边缘上所[……]

继续阅读