首页 > 代码库 > 集训 0628

集训 0628

今天的题很奇怪。

T1:几乎欧拉图。

SYQ之前出过这道题的加强版。

T2:给定一个网格图,你可以从边上经过,要求你找到一条权值最小的从左上角开始的回路,使这个回路包含所有关键点。

关键点比较少的时候可以DP+SPFA。

正解是先预处理出从左上交到每个关键点的最短路径树,然后发现一定存在一种最优方案不经过所有树边。

作出不经过树边的图后,就可以直接最短路求解。

T3:

给定一堆数,对于每个生成的排列(本质可以相同),求sn!/s2/s3/s4/s5....si表示前i项之和。

SB出题人。

出题人不知道从哪里找的一点性质,就出道了模拟题里,真是蛋疼。

不准备写了。

 

集训 0628