CTSC 2010 Summary

[Ctsc2010]星际旅行

这个题目的做法还是比较难想的,首先考虑在根结束的情况,

那么每条边两个方向经过次数一样,
同时,只在每条边至少经过一次的条件下,

只要满足H的限制,那么这个必有可行的方案(欧拉路)。
由于题目中说了H>=度数,不难证明最优解一定用了所有边。
那么就可以代数化了。
代数化之后,不难发现可以网络流建模。

网络流->最小割->树的最小权覆盖->dp。

假设不在根结束,那么最后令他最后再走回根,也就是将到根的路径上除了根的点的H+1
这个可以用dp求出。
代码:
https://ideone.com/qzTp2

[Ctsc2010]三国围棋擂台赛

这题算是比较水的了吧。。

[Ctsc2010]性能优化
首先可以想到一个用DFT的做法。。但是那样会有精度问题。。。
通过用mod n+1的原根代替单位根。。可以解决这个问题。。
代码:
https://ideone.com/mjOj1

[Ctsc2010]产品销售

首先费用流做法是这样的,对每个需求连一条边到它被解决的那天(可以是之前,代价是保存费用,可以是之后,代价是用户损失费)

那么考虑费用流算法。。注意到这个的增广路是满足“区间合并”性质的
费用流每次取费用最小的增广路。。用线段树维护费用流~~
最多增广O(N)次
但是这个方法非常的麻烦。而且nzk说不可过。
所以就没写了。。。

[Ctsc2010]珠宝商
//待写~~
代码:
https://ideone.com/rHbcO