[USACO Jan09]安全路径Safe Travel解题报告 题目 http://cogs.pro/cogs/problem/problem.php?pid=279 分析 首先把最短路径树画出来(由题意最短路径唯一,所以是树): 其中1是根。我们将树记作T,i的子树记作B。图中,B是绿色点,T-B是红色点。 而1~i最短路上的最后一条边([……] 继续阅读
[USACO Dec08]巨大的围栏Largest Fence解题报告 题目 http://cogs.pro/cogs/problem/problem.php?pid=2008 分析 这是道挺有意思的计算几何题…… 算法就是:枚举凸包的最左下点B,然后将所有合法的点按相对于B的极角序排序,这样凸包上的点一定是顺序选的。然后记忆化搜索:设状态f(B,p2,p3[……] 继续阅读
[USACO Nov08]玩具toys解题报告 题目 http://cogs.pro/cogs/problem/problem.php?pid=2007 分析 首先,稍有常识的人都会看出,这道题其实就是网络流24题中“餐巾问题”的加强版。 “餐巾问题”的标准做法是费用流:每天拆成两点(i,i’),然后S向i’连容量Ti(第i天用量),费[……] 继续阅读
[USACO Open08]牛的邻居Cow Neighborhoods解题报告 题目 http://cogs.pro/cogs/problem/problem.php?pid=2006 分析 首先我们来搞一搞这个模型。 和一个点的曼哈顿距离[……] 继续阅读
[USACO Jan07]考试Schul解题报告 题目 http://cogs.pro/cogs/problem/problem.php?pid=2003 分析 这道题比较有意思。 首先,我们不用t和p来表示分数,我们用(x,y),代表满分为x的卷子得了y分。这样更加直观:把一份卷子视作向量,那么它的“分数率”也就是其斜率。最终的分数率自[……] 继续阅读
[CF 321D]Ciel and Flipboard解题报告 题意 有一个n*n矩阵aij。n为奇数,m=(n+1)/2。我们每次可以选中一个m*m的子矩阵,将其中所有元素乘以-1.求最后矩阵中所有元素的最大和。n[……] 继续阅读
[CF 294D]Shaass and Painter Robot解题报告 题意 有一个n*m的网格,有一个机器人初始在(x,y),面朝某个斜45°的方向。机器人会一直走,遇到墙就按弹性碰撞规则(就像台球碰到桌子边缘一样)反弹。机器人每走一格,就会将其所在格子染黑。问机器人走几格之后会将整张网格染成黑白相间(或判断这种情况永远不会发生)。 分析 首先有一个结论:边缘上所[……] 继续阅读
[CF 306E]Levko and Game题解翻译 题解翻译 首先我们判断Levko是否能赢。 把所有可改变权值的道路权值都改成r[i],然后从以s1,s2为起点做两次Dijkstra算法。令d1[i]为s1到i的距离,d2[i]为s2到i的距离。考虑一条连接a和b,可以改变权值的道路。如果d1[a][……] 继续阅读