简单的测试题2 题解

1.穿越马路

30%

C,N10C,N\le10

这么小的数据,应该随便怎么搜索都可以吧。我没有写过。

60%

C,N500C,N\le500

直接二分图最大匹配,用匈牙利算法,应该是提高组要求。输出方案只要输出match[]数组。时间复杂度近似是N3N^3的,应该很容易得到这个分。

100%

C,N100,000C,N\le100,000

实际上,上述方法中很多边都是不必要的,我们考虑贪心。我们还是把区间按照结束时间排序,对于每个区间,找到最小的大于等于开始时间的点,并且不超过结束时间,则计入答案,并删除这个点。可以证明这样的匹配是最优的。由于点可以重复,用std::multiset维护,时间复杂度O(NlogN)O(N\log N)

总结

原题17FEB Silver P1:Why Did the Cow Cross the Road

作为T1还是比较简单的,应该得到至少60分。考察了贪心和STL/平衡树的简单应用。

2.2048

20%

N20N\le20

应该还是可以用搜索通过的。本来想设计N10N\le10的,但是原始数据中没有这个范围的。

65%

N248N\le248

考虑区间DP,用fi,jf_{i,j}表示区间iji\ldots j最大能得到的数,则fi,j=fi,k+1(ik<j,fi,k=fk+1,j)f_{i,j}=f_{i,k}+1(i\le k<j,f_{i,k}=f_{k+1,j})。初始条件fi,i=Aif_{i,i}=A_i,答案为所有区间的最大值。

时间复杂度O(N3)O(N^3),应该能想到这种方法。

100%

N262,144(=218)N\le262,144(=2^{18})

上述方法中,其实有很多区间根本得不到解,比如所有数相等时,可以发现只有区间长度为2的次幂是才有解。用类似倍增的方法,定义fi,jf_{i,j}表示从第i个数开始,恰好得到数j的区间的结束下标。则

fi,j={i+1Ai=jffi,j1,j1otherwisef_{i,j}=\begin{cases}i+1&A_i=j\\f_{f_{i,j-1},j-1}&otherwise\end{cases}

答案为max(j)(fi,j>0)\max(j)(f_{i,j}>0)。时间复杂度O(N(logN+maxAi))O(N(\log N+\max A_i)),而且比较满。

其实,贪心也可以做到O(NlogN)O(N\log N)甚至O(N)O(N),但比较复杂,详见官方题解。

总结

原题16OPEN Platinum P1:262144/Gold P3:248

这题比较巧妙,应该得到65分。

3.瓶颈

30%

N,Ti2,000N,T_i\le2,000

可以发现,贪心地把尽可能多的牛送出是最优的。因此,我们对询问排序,在每个单位时间送出尽量多地牛,计入答案。时间复杂度O(NT)O(NT),这甚至不是多项式时间。

70%

N,K2,000N,K\le2,000

这题另一个重要的性质是每条边的流量都随时间单调递减,通过这个性质,可以得到一个结论:一条边在T个单位时间内的流量等于min(T个单位内到达该节点的牛,MiTM_i*T)。这个结论也可以猜想得到,利用这个结论,可以计算出每个TiT_i的答案,时间复杂度O(NK)O(NK)

如果处理了一条链的情况,可以得到80分。

100%

N,K100,000N,K\le100,000

设单位时间内到达节点i的牛为intoiinto_i,考虑那些intoi<Miinto_i<M_i的节点,这些节点在CiMiintoi\frac{C_i}{M_i-into_i}单位后就会用完原来的牛。此时,可以直接把intoiinto_i看作intoPiinto_{P_i},这个节点不再有效。用优先队列来维护发生用完事件的时间,依次处理即可,当然应该用并查集来维护P。注意各种细节,时间复杂度O(NlogN)O(N\log N)

总结

原题11JAN Gold P1:Bottleneck

这题也比较巧妙,事实上当时没有人想出正解,最好的方法是O(NK)O(NK)的。可以得到70分。

4.GPS的决斗

30%

N2,000;M,W10,000N\le2,000;M,W\le10,000

第一问就是求最短路,由于有负权边不能直接用Dijkstra。考虑使用原始的Bellman-Ford,时间复杂度O(NM)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(MlogN)O(M\log N)

这题数据规模比较大,注意I/O优化,以及使用64位整数保存答案。最好用bfs得到连通块,而不是dfs。

总结

原题11JAN Gold P3:Roads and Planes & 14OPEN Silver P2:Dueling GPSs

图论二合一题,其实难度也不大,代码较长。11JAN原题可以用SPFA+SLF水过,但正解还是值得研究的。60分应该可以得到。