MiceHunter 杯省选模拟赛 II

OI - Official

From This_poet


小时

尚未报名

Oh, I see you ! 3/37 From
排座位 7/40 From
猫捉老鼠 8/50 From

MiceHunter 杯省选模拟赛 II

弱省省选难度,OI赛制,5小时3题,This_poet出题,计入能力排名。(注:题目非完全原创……)

简要题解:

第一题实际上是贪心。首先在两个连续的L或R中间插入X,然后考虑首尾相同的情况。这些处理之后对整个序列再来一次贪心,尽量让L和R都对上就行了。不过这样的话会少处理一种情况只能得到部分分数,还有一种需要特判,可以参考标程:http://ch.vijos.org/Record/Show/87cae0ff-aa65-4863-9b50-53d164524f84

第二题就是最小表示法状压dp,用最小表示法来表示每个联通块,联通的格子用相同的数字表示就可以了。相邻两行间转移可以用floyd或者并查集。http://ch.vijos.org/Record/Show/0cc2cbaa-3a71-43ec-b8db-29d707d09d87

第三题其实是最简单的?AC人数做多…… 就是TreeDP了……不过似乎NlogN处理逆元容易被卡常数,最好是O(N)处理。http://ch.vijos.org/Record/Show/d94c23b4-4765-47ab-a48d-ebbaa2675660