简单的测试题2 题解
1.穿越马路
30%
$C,N\le10$
这么小的数据，应该随便怎么搜索都可以吧。我没有写过。
60%
$C,N\le500$
直接二分图最大匹配，用匈牙利算法，应该是提高组要求。输出方案只要输出match[]数组。时间复杂度近似是$N^3$的，应该很容易得到这个分。
100%
$C,N\le100,000$
实际上，上述方法中很多边都是不必要的，我们考虑贪心。我们还是把区间按照结束时间排序，对于每个区间，找到最小的大于等于开始时间的点，并且不超过结束时间，则计入答案，并删除这个点。可以证明这样的匹配是最优的。由于点可以重复，用std::multiset维护，时间复杂度$O(N\log N)$。
总结
原题17FEB Silver P1:Why Did the Cow Cross the Road
作为T1还是比较简单的，应该得到至少60分。考察了贪心和STL/平衡树的简单应用。
2.2048
20%
$N\le20$
应该还是可以用搜索通过的。本来想设计$N\le10$的，但是原始数据中没有这个范围的。
65%
$N\le248$
考虑区间DP，用$f_{i,j}$表示区间$i\ldots j$最大能得到的数，则$f_{i,j}=f_{i,k}+1(i\le k<j,f_{i,k}=f_{k+1,j})$。初始条件$f_{i,i}=A_i$，答案为所有区间的最大值。
时间复杂度$O(N^3)$，应该能想到这种方法。
100%
$N\le262,144(=2^{18})$
上述方法中，其实有很多区间根本得不到解，比如所有数相等时，可以发现只有区间长度为2的次幂是才有解。用类似倍增的方法，定义$f_{i,j}$表示从第i个数开始，恰好得到数j的区间的结束下标。则
$$f_{i,j}=\begin{cases}i+1&A_i=j\f_{f_{i,j-1},j-1}&otherwise\end{cases}$$
答案为$\max(j)(f_{i,j}>0)$。时间复杂度$O(N(\log N+\max A_i))$，而且比较满。
其实，贪心也可以做到$O(N\log N)$甚至$O(N)$，但比较复杂，详见官方题解。
总结
原题16OPEN Platinum P1:262144/Gold P3:248
这题比较巧妙，应该得到65分。
3.瓶颈
30%
$N,T_i\le2,000$
可以发现，贪心地把尽可能多的牛送出是最优的。因此，我们对询问排序，在每个单位时间送出尽量多地牛，计入答案。时间复杂度$O(NT)$，这甚至不是多项式时间。
70%
$N,K\le2,000$
这题另一个重要的性质是每条边的流量都随时间单调递减，通过这个性质，可以得到一个结论:一条边在T个单位时间内的流量等于min(T个单位内到达该节点的牛，$M_i*T$)。这个结论也可以猜想得到，利用这个结论，可以计算出每个$T_i$的答案，时间复杂度$O(NK)$。
如果处理了一条链的情况，可以得到80分。
100%
$N,K\le100,000$
设单位时间内到达节点i的牛为$into_i$，考虑那些$into_i<M_i$的节点，这些节点在$\frac{C_i}{M_i-into_i}$单位后就会用完原来的牛。此时，可以直接把$into_i$看作$into_{P_i}$，这个节点不再有效。用优先队列来维护发生用完事件的时间，依次处理即可，当然应该用并查集来维护P。注意各种细节，时间复杂度$O(N\log N)$。
总结
原题11JAN Gold P1:Bottleneck
这题也比较巧妙，事实上当时没有人想出正解，最好的方法是$O(NK)$的。可以得到70分。
4.GPS的决斗
30%
$N\le2,000;M,W\le10,000$
第一问就是求最短路，由于有负权边不能直接用Dijkstra。考虑使用原始的Bellman-Ford，时间复杂度$O(NM)$。
第二问则需要一定的思考。由于每到达一个城镇，系统都会重新计算到T的最短路，所以我们应该建立反图G’，以T为起点求单源最短路。设第一套系统中最短路为d1[]，第二套系统为d2[]，对于反图中的一条有向边(u,v,w1,w2)，如果d1[v]-d1[u]<w1，则这条边不在第一套系统的最短路上，第二套系统同理。我们应该把原图中的边权设置为警告的次数，即加入边(v,u,w)，其中w为警告次数0~2。最后再求一遍S到T的最短路即可。
70%
数据随机生成
用SPFA代替Bellman-Ford，然而由于随机数据比较强，因此可能无法通过。
100%
可以发现，原图有很强的性质：无向边形成的连通块是强连通分量，缩点后有向边形成的图一定是DAG。所以我们可以把原图缩点，进行拓扑排序，无向边的连通块内用Dijkstra计算最短路，再通过有向边转移到另外的块。时间复杂度$O(M\log N)$。
这题数据规模比较大，注意I/O优化，以及使用64位整数保存答案。最好用bfs得到连通块，而不是dfs。
总结
原题11JAN Gold P3:Roads and Planes & 14OPEN Silver P2:Dueling GPSs
图论二合一题，其实难度也不大，代码较长。11JAN原题可以用SPFA+SLF水过，但正解还是值得研究的。60分应该可以得到。