简单的测试题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分应该可以得到。