2017ACM萧山训练第3场(World Final 2013)

2017年8月9日3,2931

A.Self-Assembly

如果一个正方形有两条边a,b

则a->op(b) b->op(a),判图中是否有环,有环则说明我们能把一些正方形绕成环然后翻折旋转变得无限大

C.Surely You Congest

只有最短路相同的会互相影响

按最短路分组后跑 c 次最大流

D.Factors

爆搜前16个素数

F.Low Power

二分答案贪心检验

H:Матрëшка

预处理\(f(i,j)\)表示将 i 到 j 全部套在一起的最小代价,枚举断点

合并两组套娃,不用拆开的情况是某一个套娃比另一组的最小套娃还小

维护前缀和,前缀后缀的最小值,能够\(O(1)\)完成转移

\(g(i)\)表示把前 i 个套娃套成若干完整套娃的最小代价,转移显然

I.Pirate Chest

用单调栈把暴力优化成\(O(n^3)\)

J.Pollution Solution

辛普森积分

但是可能被构造卡掉,可以把积分的范围调整一下

 

  • De℃,.: )2015年5月20日 下午4:33 回复

    又是一年WF时

    #1