读 P8339 [AHOI2022] 钥匙 题解有感
- 对于一个仅有
x,y 组成的序列,x 为钥匙,y 为箱子。 - 重点在于统计
xxyyxxyxyxyy 的任意子段的贡献。 - 基本的,我们让
xy 的贡献为1 - 但
xxyy 的少了1 的贡献,不妨令xxyy 的贡献为1 - 但
xxyxyy 的贡献又不对,那不妨令xxyxyy 的贡献也为1 - 那好像只要,一段区间满足,视
x 为1 ,y 为-1 若满足一段x,y 和为0 且任意前缀>0 就有1 的贡献。 - 起始,捡起钥匙,开启箱子,就像维护括号序列的栈一样,有增有减。钥匙,箱子有很多种配对方式,但向括号序列匹配一样配对,保证了,配对的唯一性,而且存在栈,就一定存在括号序列,一定存在匹配。