星系模拟器开发日志(一) 如何科学地用C++画图

代码下载地址: http://pan.baidu.com/s/1eQjiETc 2015.8.11更新: 最近突然有一个想法:写一个程序,用来模拟太阳系的行星运动,甚至是任意星球的运动。感觉这个想法非常excited,所以就准备开始写。程序的名字就叫“星系模拟器”吧,或者也可以称作“拉普拉斯的长者?”,英文名Solar Simulator 为了避免写完后过一个月看不懂代码的悲剧重演,我准备把整个开 … 继续阅读“星系模拟器开发日志(一) 如何科学地用C++画图”

Farewell, OI!

听说写退役感言是传统,那我也写一个吧……   似乎很多OIer会对信息学竞赛怀有一种特殊的感情,我可能没那么强烈。NOI之后,我最主要的感受就一条:结束了,终于结束了。   初一最早听说有信息学竞赛的时候,我其实是拒绝的,因为当时我是一个搞数学竞赛的骚年……但还是抱着试一试的心态去了,结果就一发不可收拾,初中是OI数竞一块搞,高中就翘掉数竞全力搞OI,直到现在。   … 继续阅读“Farewell, OI!”

[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解题报告”