DD的USACO征程

Congratulations! You have finished all available material.

这题的算法和最小前缀和类似！要认真体会。cowxor.cpp

今天或明天就能通关USACO了。

刚开始看到这题时，真的是一点头绪都没有呢。不得已寻觅各种题解……结果众牛异口同声地说：离散化+线段树。于是便开始写……写着写着……觉得真的麻烦死了。又看了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

算法是矩形切割。要配合链表的操作。（似乎必须写双链表？）
这是我的程序中“模块化”和“抽象层次”做得比较满意的一点。虽然没有用OO。但是将链表的操作抽象成几个函数，将输入数据的处理抽象成几个函数……层次上非常清晰。我对这程序非常满意。
window.cpp

太easy的dp，不过方程写垃圾了……不说也罢。
bigbrn.cpp

这竟然是一道完全不用加剪枝的深搜？可是……谁能告诉我这个的复杂度应该怎么算？
snail.cpp

裸凸包……graham-scan。用折腾了半个下午加半个晚上。不断地出低级错误。太累了……不多说什么了。
fc.cpp

很精妙的一个DP。
v[k][j]表示以i和j开头的最长主题。
v[k][j]=s[j+1]-s[k+1]==s[j]-s[k]?v[k+1][k+1]+1:1;
如何减少储存空间？注意状态间的依赖性。按照枚举i和j的距离来求值。我想你应该明白我的意思。
第一次提交没过是因为没看见is at least five notes long这一句。
theme.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

以下是Bronze和Silver的全部AC程序。Gold的等我有心情再做。
balance.cpp
expense.cpp
fireshow.cpp
latin.cpp
round.cpp
traffic.cpp

先比较麻烦地构图，然后Floyd最小圈即可（这个算法开始没有写对，结果提交了三次）。
fence6.cpp

It's a milestone. I will go on.

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

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

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