[USACO Open10]数三角形Triangle Counting解题报告

题目 http://cogs.pro/cogs/problem/problem.php?pid=543 分析 这道题的要点在于:含原点的三角形不好数,我们数不含原点的三角形,最后用C(N,3)扣掉它就是答案了。 怎么数“不含原点的三角形”呢? 画出我们所在的坐标系。我们拿一条过原点的直线l,按极角序去扫描: 直线l分成两条射线,一个是a,另一个是b。它绕着原点(Bessie所在点)旋转,请自行想象 … 继续阅读“[USACO Open10]数三角形Triangle Counting解题报告”

[USACO Mar10]星牛争霸StarCowraft解题报告

题目 http://cogs.pro/cogs/problem/problem.php?pid=2010 分析 首先可以发现,我们能够把三种单位的战斗力同时乘以一个数而不改变结果。因此,不妨设第三种单位的战斗力S3=1.出于方便,不妨记x=S1,y=S2 对于一场比赛,我们能够写出一个类似这样的式子: j1x+j2y+j3=) 整理后得到一个类似这样的式子: ax+by

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

题目 http://cogs.pro/cogs/problem/problem.php?pid=279 分析 首先把最短路径树画出来(由题意最短路径唯一,所以是树): 其中1是根。我们将树记作T,i的子树记作B。图中,B是绿色点,T-B是红色点。 而1~i最短路上的最后一条边(也就是不能走的边)即i的父亲边。将这条边去掉以后,1~i的最短路长什么样呢? 可以发现,一定是这样的: 即,先从1沿着树边 … 继续阅读“[USACO Jan09]安全路径Safe Travel解题报告”

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

题目 http://cogs.pro/cogs/problem/problem.php?pid=2008 分析 这是道挺有意思的计算几何题…… 算法就是:枚举凸包的最左下点B,然后将所有合法的点按相对于B的极角序排序,这样凸包上的点一定是顺序选的。然后记忆化搜索:设状态f(B,p2,p3)代表:最左下点为B,凸包上选的最后一个点为p2,正在测试选不选p3.那么有两种转移:①不选p3,将p3改为p2 … 继续阅读“[USACO Dec08]巨大的围栏Largest Fence解题报告”

[USACO Nov08]玩具toys解题报告

题目 http://cogs.pro/cogs/problem/problem.php?pid=2007 分析 首先,稍有常识的人都会看出,这道题其实就是网络流24题中“餐巾问题”的加强版。 “餐巾问题”的标准做法是费用流:每天拆成两点(i,i’),然后S向i’连容量Ti(第i天用量),费用0的边,代表当天的脏餐巾。当然还有别的边,但这个是最重要的。 其实“餐巾问题”还有一 … 继续阅读“[USACO Nov08]玩具toys解题报告”

[USACO Jan07]考试Schul解题报告

题目 http://cogs.pro/cogs/problem/problem.php?pid=2003 分析 这道题比较有意思。 首先,我们不用t和p来表示分数,我们用(x,y),代表满分为x的卷子得了y分。这样更加直观:把一份卷子视作向量,那么它的“分数率”也就是其斜率。最终的分数率自然就是所有向量之和的斜率。 先考虑一个问题:假如对某个给定的d,现在已经按老师的方法确定了最终的分数率G,那么 … 继续阅读“[USACO Jan07]考试Schul解题报告”

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

题意 有一个n*m的网格,有一个机器人初始在(x,y),面朝某个斜45°的方向。机器人会一直走,遇到墙就按弹性碰撞规则(就像台球碰到桌子边缘一样)反弹。机器人每走一格,就会将其所在格子染黑。问机器人走几格之后会将整张网格染成黑白相间(或判断这种情况永远不会发生)。 分析 首先有一个结论:边缘上所有该染黑的格子都已染黑,当且仅当整张网格已按要求染成黑白相间。 证法是归纳。假设第一行该染黑的格子都已染 … 继续阅读“[CF 294D]Shaass and Painter Robot解题报告”