首页 > 代码库 > 【比赛题解】03-25生日赛

【比赛题解】03-25生日赛

03-25是小兔的生日……

这一周是我出题……三道题的难度是 T1<T2<T3

【T1】过生日

技术分享

其中3<=n,m<=1500

技术分享

【T2】方程狂魔

技术分享

技术分享

其实质数个数是664579个……

【T3】监视

技术分享

技术分享

求图的最小生成树,然后天天爱跑步就好。
为什么是最小生成树?
因为每个小伙伴只会走路径上最大权最小的。
先考虑走的边一定是树边:
把这个图MST之后,对于一条树上路径,把路径换成另一条非树上路径,结果一定不会更优。因为另一条路径上的最大权值一定没有当前路径上的最大权值更大。而又因为树上权值互异,所以MST只有一个,最优解也只有一种。
再考虑不会经过重复的树边:
这个比较容易,重复走一条新的树边时,一定把原来路径变得更长2个了,假设原来路径的排序后是:
a a ... b b c c ... d d ,新加入的树边的权为x(b>=x>c),x一定会插入在b与c之间,会使结果更劣,所以不会经过重复的树边。
综上所述,对原图求MST,路径一定是最短树上路径,及S到LCA再从LCA到T。
接下来就是天天爱跑步的事了,题解详见zxyer的blog,他比我港记。
orz zxyer

原题是NOIP2016TGD1T2天天爱跑步,很丧的一题……

【比赛题解】03-25生日赛