DD的USACO征程

rectbarn.cpp
阅读这篇程序，你会感到一股属于逝去的黄金时代的古典气息；是的，这是一篇古色古香的程序。

刚开始看到这题时，真的是一点头绪都没有呢。不得已寻觅各种题解……结果众牛异口同声地说：离散化+线段树。于是便开始写……写着写着……觉得真的麻烦死了。又看了USACO官方的Analysis。很惊异于那个程序的长度和编程复杂度（好短啊……）。不过我怎么都觉得这个程序不应该AC的，因为它的时间复杂度大约为O(20000*N)。（我知道……这种写法是错误的。你可以说这是O(N)，但是它在n次循环里每次都要扫描一个长度为20000的数组……这就导致了超时。）
那个程序真的需要将两个数组拷贝来拷贝去吗？真的需要每次都扫描整个数组吗？不是的！只需要在每次增值或减值时判断数组的这个元素是否由零变一或由一变零就可以了！这样就大大降低了实际的耗时。（虽然原则上来说没有降低渐进时间复杂度。）
最后的程序只有83行哦！但是却能做到最后一个数据0.204s的效果。太神奇了……
picture.cpp

TASK: charrec
LANG: C++

Compiling...
Compile: OK

Executing...
Test 1: TEST OK [0.036 secs]
Test 2: TEST OK [0.036 secs]
Test 3: TEST OK [0.068 secs]
Test 4: TEST OK [0.128 secs]
Test 5: TEST OK [0.304 secs]
Test 6: TEST OK [0.416 secs]
Test 7: TEST OK [0.592 secs]
Test 8: TEST OK [0.592 secs]
Test 9: TEST OK [0.628 secs]

All tests OK.
YOUR PROGRAM ('charrec') WORKED FIRST TIME! That's fantastic
-- and a rare thing. Please accept these special automated
congratulations.

我只能说……这太神奇了。我也没想到。
虽然基本方法是DP谁都能看出来，但这题看上去真的很麻烦，不过仔细的划分模块以后就可以写得很有条理。
charrec.cpp

拆点构图。求网络流。然后就是一个一个删点看流的值是否减小1。
要注意每次求完网络流都会把图破坏掉。所以要重新构图。
telecow.cpp

剪枝：
1.第1行第1列都是1-N。
2.最后一行不用搜，一定有解。
3.前两行可以当成置换群用hash保存答案。
（Analysis里面那个剪枝还没看懂……）
1latin.cpp

方法是这样的：
首先，用你喜欢的方法求出强连通子图。然后第一个问题的解就是没有入边的强连通子图的个数，第二个问题的解就是没有出边和没有入边的强连通子图的数目中较大的一个。
schlnet.cpp

通过这题要掌握二维离散区间中的搜索方法，就是不断调整，同时缩小调整的范围。这显然可以推广到更高的维度。但每次调整的次数应有一个上限，否则就会出问题（在USACO的评测机上会超时，似乎是死循环，而在我的电脑上就不会，所以说for(;还是要慎之又慎啊！）。
fence3.cpp

纯搜索，随便加点剪枝就过了。
如果以后有空的话，用链表优化它，应该可以做到1s以内。
wissqu.cpp

构造法
shuttle.cpp

只要你能看出这是拓扑排序。
frameup.cpp

4.2：这题写傻了……原来可以不排序的，把边反一下就行了。

由于这题的数据规模实在是太小了……所以几乎只要是多项式的算法都能过……汗……我写的就是O(n^3）的，可还是最大的数据0.004……不过显然有更好的方法，看看别人的标程吧。
race3.cpp

这题实在太有意思了！第一问当然easy，关键是第二问。我们如果从“策略”的角度来想，也就是说每一个从A出来的东西要放到哪个B里，会完全无从下手。
正确的方法是：将两问分开来，也就是先假设两个任务是彼此独立的，都当第一问来求。然后利用单调性，把a[k]和b[n-1-k]配对。over。
job.cpp

网络流。用的是广搜增广路。当然了，数据太弱了。（主要是图太稀疏，m太小。）
ditch.cpp

搜索题。比较典型的迭代深搜。里面的优化也是比较典型的。我主要用的优化有：
1. 二分答案。
2. 对boards和rails都进行排序。
3. 出现重复的board或rail时可剪枝。
4. 事先试图缩小答案的上限。
5. 每次枚举用那个board放当前的rail时都先寻找有没有和现在的rail完全相同的，如果找到就不再尝试其它board。
fence8.cpp

这道题的中文翻译有问题！害我多提交两次。强烈郁闷……不过……谁让咱想省点事儿呢，没法儿埋怨那些义务翻译的好心人啊……
nuggets.cpp

我做的第一道几何题……不过这个不算计算几何，应该算作解析几何吧。那个为了排除恰在线上的点而加上一个小差量再取整的方法是我原创的哦！
fence9.cpp

搜索，需要加最优性剪枝。先贪心一个上界很有用。
camelot.cpp

我显然把这道题想麻烦了：构图，每种购买商品的组合是一个顶点，每种打折方式是一条边，然后就SPFA……可是显然不用这么麻烦，可以DP的……以后有空了再用DP写个程序。
shopping.cpp

很不错的广搜题目，用hash表（也就是全排列的康托展开）来判重。虽然最后程序的效率应该还是挺高的（不超过0.2s），但是通过profile分析发现计算hash值的函数占了近80%的时间！求康托展开最高效的方法是什么呢？有O(n)的方法吗？（应该是有的吧）
msquare.cpp

这题我估计一次通过的人也不会多，很少人会一开始就考虑到被零除的那个问题。吸取经验，以后要谨慎了……
ratios.cpp

YOUR PROGRAM ('butter') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.

好高兴啊……第一次写SPFA，还真好用呢！
（循环队列好像也是第一次编？这么简单啊……）butter.cpp

YOUR PROGRAM ('stamps') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.
stamps.cpp

（这道题是昨天写的，可昨天中午和下午USACO挂掉了没法提交……晕……）
我看到这道题的第一个想法是二维线段树，后来突然想到可能不用那么麻烦，似乎用离散化也行。于是便编写了一个离散化（由于是第一次写离散化，调试了一会儿），没想到最后一个数据竟会超时……星牛的解题报告中什么用链表保存矩形怎么分割什么的没看懂。不得已看了maigo的标程……那个方法太强悍了，深有所悟。变量z是很有意义的，直观地来说就是矩形从下面往上面浮，如果受到阻拦就分割，如果浮出水面就记录。
rect1.cpp

输出格式比较特别，以后就会有经验的……要注意细节问题，比如说N恰好被B整除的情况没有经过仔细测试。
fracdec.cpp

有点繁琐的题目，好在我的思路还算清晰……
第一次提交没有通过的原因是因为某些变量初始化成了-1，这是我以前的习惯，而在某些情况（比如说连通子图里只有一个点时），把这里面的ldis和mldis变量初始化成-1就会有问题，改成0就没事了。
cowtour.cpp

呵呵……很简单的题目。关键是为了找出无解的情况需要进行判重。我采用的是龌龊的6维数组来判重……您可以尽情BS。不过还有更好的判重方法么？毕竟本题的空间完全不成问题……标程的超过160000就输出0的方法我也想到了，不过觉得还是有点太过低级……（当然了，在有时判重相当麻烦的情况下，这种思想是很可以借鉴的。）
ttwo.cpp

这是一道原来Chapter6的题……很无奈地看了星牛的解题报告。思路很特别，题目中要求“恰好XX”，然而我们很难直接求出来这个，所以说只能求“最多XX”，然后一算差量立得……
nocows.cpp

简单的搜索题，一次通过……
zerosum.cpp

很考验细心的一道题……要好好读题……（第一遍提交竟然把文件名打错了……runaround……runround……）
runround.cpp

preface.cpp

由于一点点很小的失误，导致一直TLE：max=1<<(B+1);写成了max=1<<B;（max是搜索数的上界）。
事实上当我的程序运行很长时间结果出来样例WA的时候，就应该从正确性上找问题，而不是再盯着效率。通过这道题我明白了：表面上出现的效率问题事实上有可能是因为程序的正确性没有保证。
hamming.cpp

这题真让我有点欲哭无泪……本来一看是那种深搜求最优解的，就觉得可以用迭代加深，我以前没写过迭代加深，随便一写觉得还真的挺好写的！结果一交上去……TLE……优化了半天，最后1.38s，还是过不去……然后只好反思：难道不应该用迭代加深？最后只好写成了最普通的深搜，每次找到解以后与当前最优解比较判断是否更优。结果最大的数据0.008s（这得益于我程序中本来就保留着的几个优化和剪枝）。实在是郁闷至极啊……
holstein.cpp

一道很纯粹的Flood Fill……由于粗心，由于这两天由于某些事情状态不好……提交了4次……真是……无话可说了……
castle.cpp

做这道题的时候出现了一个小插曲：我开始把数据规模看错了……b<=100000000我以为是b<=1000000000……结果用我以为的“极限数据”优化了半天经过了N次Profile之后才勉强跑进1s……结果交上去一看竟然全都是0.0x sec出解……汗啊……
不过锻炼了一下用Profile优化程序的能力，我还意识到把stream换成stdio能优化很多，这也是很不错的。
第一次提交没过样例……汗……这几天做题越来越不仔细了……
pprime.cpp

这个题就是深搜，需要判重。判重的bool数组不用写成三维的，写成两维的就可以，另外一维可以用C减去得到。同样的道理search函数的参量也可以只有两个。但是要注意保存的两维中一定要有C桶的量，这样才能方便的从小到大输出。
发现这两天做USACO使得程序风格有所改善，程序写的应该是比较清晰，傻瓜都能看懂那种……同时我也体验到了程序写得尽量情系给调试带来的好处。
又是一遍AC，很高兴呢！
milk3.cpp

上面那个四个矩形的题看上去太麻烦了……所以就先做了这一题。
首先这个的解法应该是简单的深搜，从0到3枚举每个开关的次数就可以，加上一个最优性剪枝可以提高不少效率（虽然貌似不加也行）。
在这个程序的具体实现中，我采用了非常模块化的设计（感谢C++的inline关键字），这使得程序逻辑比较清晰，调试非常轻松，编写也变得容易。
这个本来可以一遍提交AC的，可是由于不知道末尾多了个空格也会WA而提交了两次……郁闷……
clocks.cpp

第一道交了三次的题……彻底郁闷了……
第一次，使用最朴素的枚举，最坏情况O(n^3)，最后一个点n=20000就TLE了……呵呵……好像是我的思路还停留在1.2……汗……
第二次，采取枚举中间点向两边扩展的方法（这就是Greedy了），结果第三个点就WA……郁闷的调试了半天，结果很显然——算法只找出了长度为奇数的回文……
第三次，修复了上面的Bug……终于AC了……
calfflac.cpp

敲完代码以后一次编译通过+AC，好高兴啊……不过这道题也的确太简单了点……
milk.cpp

YOUR PROGRAM ('palsquare') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations.
真不容易……又看到久违的这句话了。好高兴啊！
palsquare.cpp

又是一道提交了两次的题目……这次是怨我没看清题目：between the beginning and the ending of all milking(从挤奶开始一直到挤奶结束)，就是说统计的时候不能从0时刻开始……
milk2.cpp

friday.cpp

ride.cpp