USACO Contest终于又开始了
这次Qualifying Round挺水的,简单写个题解放到这儿.
首先说一下Qualifying Round和别的USACO月赛有啥不同.认为此段比较火星的可以跳过,写这个是因为我也是刚刚知道的.感谢zmc告诉我...
Qualifying Round,就是资格赛.对于原先是Gold的号来说,这次比赛参加之后不会得到任何好处(我要是早知道就不用我的两个Gold参赛了...);对于Bronze和Silver,如果你在这次比赛中取得比较好的成绩,那么你可以直接升为Gold.
第一题,直接忽略掉...不会做的撞墙去.
第二题,很多人竟然没看出是DP...实际上构成四边形,只要每条边的长度都小于n/2就行了...
第三题,分值最高的一道题.我当时用了FancyMouse牛的一个猥琐的贪心做法,但实际上这道题很弱智.加入一个新点,然后和原先的每个点连边;接下来新边的边权就是原先的点权;最后做最小生成树即可.看到这个算法,才知道这就是白痴弱智题...我就是白痴弱智...
第四题,求树上两点间最短路.数据范围的宽松使得做法很多,我见到了写n次nlogn的Dijkstra的(膜拜大牛!),写n次SPFA的,我写了个朴素LCA...
第五题,随便DFS一下.感觉是考英语的而不是考coding的.
第六题,最短路.这道题我也比较傻X,写了个变态的并查集.实际上只需要把已经存在的边权值都设为0就行...
下周放出译题...最近喜欢上翻译了.
顺便广告一下,DLXcn一期校对完成.点击这里查看~