csp-s游记

· · 生活·游记

考前：

考后：

嗯对大概就是游记吧。

开局开T1，发现可以直接贪，10min写完（我码力不行不要嘲笑我）

开T2：

发现每个乡村可以选或者不选，产生不同的贡献和代价，猜测是最小割……然后一个小时过去：

接着发现可以把每个乡村建成点直接跑最小生成树……然后又一个小时过去：

因为每个乡村也可以不选，所以最小生成树是假的……好消息是把特殊性质的分拿到了。

观察到k<=10,开始暴力枚举每个乡村选不选，复杂度 O(2^kmlogm) ……计算发现：

绝对跑不动。。。。然后想办法把 log 砍了，最终估分72。（我竟然想不到m条原图边中只有n-1条边有贡献……）

开T3。

因为大纲写的字符串算法只有kmp和马拉车所以开始思考……又一个小时过去发现：

（你知道我要说什么。）

然后只剩半个小时了。

鸿儒文破儒房。

打了两个暴力。T3哈希 n^2 暴力匹配，T4爆搜+剪枝。

乐观估分100+72+25+24，悲观估分100+72+25+0。

赛后：

完了。这下上200都够呛了。

这不完蛋了我还学啥OI啊。

后记：

哇哇哇出成绩了！！！

T1 95？？？？

T2 80，CCF少爷机果然nb！可惜没跑过1e9不然我就AC了。也算把T1分补回来了。

T3 25!

T4 4分，情理之中。

总结：95+80+25+4=204，拿1=够呛啊……等明年吧。