省流:高一 rk6,整体 rk10。
考场上直接用前几天学的 map 优化 dp 优化我 T2 的 \(O(n^4)\) 代码,然后过了 \(4000\)!
感觉后面 dp 的优化是比较好想的,如果想到填表法的话。还要注意处理大小依赖关系,故从小到大加入的 trick。
T4 最后几分钟极限过样例,random_shuffle 过 \(200\)!(其实当时已经把性质什么都推出来了的,主要是一开始没有发现只选 1 个的性质,可能再多几分钟就能把 80pts 的 dp 打出来了,不过有 60 已经很理想了)
T4 到了最后本质上就是求 5 组物品的多重背包(或者叫分组?),然后每一层可以选不同个,价值递增。注意这玩意有决策单调性,所以就可以单次线对转移。(还是要枚举 \(V \mod i\))
T3 猜测每条边只操作一次打的暴力,结果错了。其实结论在考场上猜到了一些,但是只能说没有想到必要条件居然还是充分的,亏大了,应该分 Sub 打一下特殊性质的。只能说构造确实很妙。
感觉以后有些图上面的性质题都可以尝试分成:二分图和奇环来考虑。
然后 T1 更是有点傻了,先是看错了题去打数形 dp。然后又打了个很正确但是很难写的分讨,大概花了 50min 还没写完,然而兔子在厕所告诉我直接暴搜合法答案就可以了……。
标签:9.22,R7,NOIP,T4,dp,性质 From: https://www.cnblogs.com/LCat90/p/18425767