读 P8339 [AHOI2022] 钥匙 题解有感

LUHCUH · 2025-02-05 09:42:31 · 闲话

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