题目
分析
这道题的要点在于：含原点的三角形不好数，我们数不含原点的三角形，最后用C(N,3)扣掉它就是答案了。
怎么数“不含原点的三角形”呢？
画出我们所在的坐标系。我们拿一条过原点的直[……]
分类： OI
[USACO Mar10]星牛争霸StarCowraft解题报告
题目
分析
首先可以发现，我们能够把三种单位的战斗力同时乘以一个数而不改变结果。因此，不妨设第三种单位的战斗力S3=1.出于方便，不妨记x=S1，y=S2
对于一场比赛，我们能够写出一个类似[……]
[USACO Jan09]安全路径Safe Travel解题报告
题目
分析
首先把最短路径树画出来（由题意最短路径唯一，所以是树）：
其中1是根。我们将树记作T，i的子树记作B。图中，B是绿色点，T-B是红色点。
而1~i最短路上的最后一条边（[……]
[USACO Dec08]巨大的围栏Largest Fence解题报告
题目
分析
这是道挺有意思的计算几何题……
算法就是：枚举凸包的最左下点B，然后将所有合法的点按相对于B的极角序排序，这样凸包上的点一定是顺序选的。然后记忆化搜索：设状态f(B,p2,p3[……]
[USACO Nov08]玩具toys解题报告
题目
分析
首先，稍有常识的人都会看出，这道题其实就是网络流24题中“餐巾问题”的加强版。
“餐巾问题”的标准做法是费用流：每天拆成两点(i,i’)，然后S向i’连容量Ti（第i天用量），费[……]
[USACO Open08]牛的邻居Cow Neighborhoods解题报告
[USACO Jan07]考试Schul解题报告
题目
分析
这道题比较有意思。
首先，我们不用t和p来表示分数，我们用(x,y)，代表满分为x的卷子得了y分。这样更加直观：把一份卷子视作向量，那么它的“分数率”也就是其斜率。最终的分数率自[……]
[CF 249D]Donkey and Start解题报告
题意
第一象限上有n[……]
[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°的方向。机器人会一直走，遇到墙就按弹性碰撞规则（就像台球碰到桌子边缘一样）反弹。机器人每走一格，就会将其所在格子染黑。问机器人走几格之后会将整张网格染成黑白相间（或判断这种情况永远不会发生）。
分析
首先有一个结论：边缘上所[……]