Nov09 USACO 解题报告
phoeagon
Gold Division。
感谢SinyaLee中文翻译。
1. 灯
给定一个无向连通图，一开始所有节点为黑色。每次选定一个顶点，使得它以及与它有直接边相连的节点变换颜色。求最少步数使得所有节点变为白色。
首先，OIBH上有人说这个是解方程。
然后，发现我找不出方程。
由于我觉得这题比较难~
普通BFS首先一定会MLE。35个节点很难判重（Hash？）。
于是我写了一个裸的IDDFS。结果就过了12（13？）个点？ 3个最大规模的TLE。
此题正解是，把35个灯分成两组，第一组18个第二组17个。
首先搜前十八个是否选定。把所有情况以及对应的次数存起来，排序。
之后搜后面一半，每次在存的数组中二分查找，找到解就检查是否更新ans。
注意，第一次搜索时，由于判重不方便~ 所以搜出来的情况中，选定的灯不一样多也可能导致结果一样~ 所以要双关键字排序（但这种情况比较少见，只出现在很稠密的图~）
2、谁请客
裸的网络流~
没什么好说，随便怎么最大流都过去~ 我写的是最裸的Forever F~
另一种做法是拆点作匈牙利~
分数很高的kimiyoung同学想出了一种可以AC的贪心法~
3、拯救***
距离函数很WS~
找规律~~
怎么搞~
Analysis这样写：
Checking correctness of such a distance function is rather difficult. If you are a fast coder, you could check it by writing an alternative solution using a BFS and comparing results. And if the distance function does fail, you still have a partial (slow) solution.
总之我完挂在这题上~
Silver Division
Silver的题好像更具有启发性~
更加有想头~
1. A Coin Game
动态规划在博弈论中的应用。
F[i,j]表示第i到第n个硬币，先手取j个时先手最多可以拿到的硬币面值。
f[i,j]= sum[i,n] - max { f[i+j,x] } (0<x<=2*j)
O(n^3)。
用一个数组max[i,j]记录f[i,0..j]的最大值.
优化到O(n^2)
2. Grand Farm-off
模拟题。
此题猥琐。
非c/c++者极易超时。
我花了一个晚上压缩常数到用Pascal能AC。大概思路是：
1、编译开关
2、尽量避免不必要的取模运算。
3、把小循环拆出来分一句一句写（Phoenix道写起来很不爽）
4、能用longint不用int64，必须用int64时用qword（因为非负。）实践证明qword比int64快。当我优化到山重水复疑无路，而最后一个test case依然是1.028s时，改成qword就0.855了~
5、快排每次只排包含第n-1个元素的区间，其他区间不递归。并为小规模情况写一个选排。
3、Job Hunt
经典的最短路模型（本来是最长路~）
因为要找负环，最方便的做法是Bellman-Ford~
Bronze Division
没啥好说，题目没什么新意。
但要AC其实不容易~
1. Cow Pinball
裸的数字三角形。DP
2. The Chivalrous Cow
裸的跳马最短路。
可以建图dijkstra，可以BFS。
随便怎么都过，很小的范围。
3. Claustrophobic Cows
给定N<=2000个点。求出欧式距离最近的两个点。
由于规模很小，不需要分治，直接平方级暴力。
这题很难1A。因为貌似不是很大的坐标范围，其实平方相加会超过32位整形longint。
突然发现这篇写得最多的是“裸“和“暴力”
= =|||
| 
