阶段性做题总结
有一段时间没有做USACO了，主要是遇到了3.4 Closed Fence! 这题很麻烦的，计算几何的繁题。于是开始做PKU，原来想做TJU，可惜爆掉了~ 后来我们老师说PKU没有题解，做题不知道好坏，推荐我去做SGU，现在在根据"泛做题目列表"做SGU。
Archive of posts tagged USACO
SHTSC 05 结束了，准备 NOI 吧
SHTSC 05 结束了，我考得还行，自然是没有能够进上海队，但是混到了一个额外名额（就是只记分，不发奖），所以这两天都忙着做题、集训，没有时间管理 Blog 了。 这段时间没怎么做 USACO，倒是看了看从前 NOI 的题目。 帮余老师配置了 RH Linux 9，NOI 要用。NOI 老是换平台，今年又换成了 RH Linux 9+Lazarus，Lazarus 其实并不成熟，很多地方还有问题，并不用急着换。随着 FP 2.0 的 Release，FP IDE 越来越稳定了，是个不错的选择。 Old Blog Link: http://computer.mblogger.cn/henryhu/posts/41983.aspx
USACO 到了 1.3.4
1.3.3 终于过了，Camelot 让我想了好久，最后终于通过BFS+优化，在求出一个骑士到目标位置的最短路的同时求出骑士带上国王到达目标位置的最小花费，AC了，最大数据0.91s（优化前1.08s），好险啊~ Packing Rectangles 的前五种情况都很简单，第六种比较烦，我试了好几次，最后加了两句判断，过了。 Controlling Companies 就是不断扫描并更新控制的情况，包括百分比和控制的公司，能够过，速度很快。 1.3.4 讲计算几何，据说第一题( Closed Fences , fence4 ）比较难，我不知道~ 要放暑假了，准备回家好好做题。 期末考试考得不好，比期中全面退步~ 是不是因为信息学上花的时间多了呢？ Old Blog Link: http://computer.mblogger.cn/henryhu/posts/40660.aspx
USACO Problem Status
Problem 23 Controlling Companies Submit 4 AC 2005/6/20 2005/6/30Problem 41 Packing Rectangles Submit 8 AC 2005/6/20 2005/6/30Problem 37 Camelot Submit 7 AC 2005/6/20 2005/7/3Problem Closed Fences 2005/7/3Problem Cow Tours 2005/7/3Problem American Heritage 2005/7/3Problem Transformations 2005/7/3 Old Blog Link: http://computer.mblogger.cn/henryhu/posts/40444.aspx
USACO 到了 1.3.3
USACO 1.3.2 里的 Calf flac 和 A Game 用掉了很多时间，前一个 Submit 了 22 次，后一个 Submit 了 13 次。 Calf Flac 其实就是求回文串，但是算法比较独特，经过同学提醒，终于过了。A Game 我知道是 DP，但是我自己编的 DP 怎么样都不对，原来的状态转移方程：f[t,p]=max(f[t-1,p]+d[t-1],f[t,p-1]+d[t+p])(对A)，f[t,p]为从t开始，长度为p的数据中 A 相对于 B 的最大优势，d[i]为这些数，但是这样转移第六个点就是错，怀疑是算法问题。想下来，应该是对方认为本方会按照最差的走法走，这是一个问题。原来是t从大到小推，后来改成t从小到大推，但还是错，而且问题严重~ 最后改成了f[t,p,1]=max(f[t,p-1,2]+d[p],f[t+1,p,2]+d[t])，f[t,p,1]表示这时本方在区间[t,p]能得到的最大分数（参照OIBH，Thanks to HenryBag），终于 AC 了~ 这题有16个点~ USACO 1.3.3 似乎是关于二进制的，还没有好好看过。 Old Blog Link: http://computer.mblogger.cn/henryhu/posts/39438.aspx