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 的作用

Author

TosakaUCW

Posted on

2024-08-27

Updated on

2024-09-03

Licensed under

Comments