2024 杭电多校 10
唉这场在高铁上,勉强打打。
头铁冲 hash,原来 hash 真能被卡啊()血泪教训,能用 kmp 就一定要 kmp
Problems | AC |
---|---|
1001. LIS | |
1002. scenery | ⊕ |
1003. 败北 | |
1004. 轰炸 | |
1005. 套娃 | |
1006. DuelForSun | |
1007. SunBoYi | |
1008. SunBian | ○ |
1009. 不基本子串结构 | ⊕ |
1010. A+B Problem | |
1011. NOI2024 | ○ |
1012. 花环 |
1002
显然可选区间单调不变小这个性质会比较有用,这意味着我们每次肯定是贪心地放着区间两侧会比较优。
有一个比较巧妙的状态设计是这样的:对于一个 $j$,我们设 $[j, dp[j]]$ 这段时间是没被选择过的。
那么对于每一个 $i$,你枚举一个 $j$。然后更新即可
1008
容易发现,除非特定情况下,一坨都会被 split 成两坨。随后在两坨上可以镜像操作。
所以先判断不能将一坨 split 成两坨的情况 (i.e. k == 1 or k == n)
否则 B 会 split 成两坨,这样 B 在 A 对面的那一坨上面镜像操作即可。
1009
kmp 结束以后那个 j 的作用
2024 杭电多校 10