密码锁
没什么好说的，要么暴力判断，要么手推。
消消乐
我们观察一下这个能消除的结构，因为是每次消除相邻两个，所以不难想到很像括号匹配，或者说可消除的是有对称性的，所以我们一定可以找到一个节点开始反转左右手性，所以我们就可以用栈来保持前半部分的手性，后半部分遇到转折点就是可以消除，可以消除就是可以消除。
先考虑部分分，就是 \(n^2\) 枚举每个子串，再对每个子串进行入栈模拟，是 \(n^3\) 的，35pts。
考虑怎么优化这个暴力。就是考虑大的串必然包含小的串，所以对大的串进行模拟的时候我们是一定将小的串也进行了一次模拟的。考虑对于每个小的串，如果前面是全部可以消除的，就是到它的起点位置时栈为空，那么到它的末尾时看其栈为不为空就已经判断了它是不是可消除的。如果起点不为空，那么我们就不算进去，后面总有一次会起点是空的。所以我们不用再重复模拟，只需要枚举起点然后看栈为空的次数就好了。但是有人就要问了，你这样为什么不会重呢，有可能这个区间是可消除的几个拼接在一起，那你这样算出来栈为空的次数就多了吧。其实不然。你考虑如果两段是合法的，那么拼起来还是合法的，这样就会比单纯的单个合法多了一些排列组合，而如果有不合法的显然对答案没有影响，所以是少想了而不是算多了。
所以我们就有了 \(n^2\) 暴力，可以获得额外的15pts。
考虑继续优化，既然我们入栈的模拟不能优化，那我们就对于枚举头端点进行一个优化，考虑我们后面的计算能不能用上前面的数值呢？你考虑其实我们的字符串对于每次出栈入栈以后都是有一个状态的，我们如果维护栈内的字符串组成的状态，那么是不是就可以避免重复对这一个状态进行计算了。发现在从 \(1\) 到 \(n\) 维护栈序列的时候，若对于某个时刻 \(l\) 和某个时刻 \(r\)，两种时刻的栈序列完全相同，那么说明子串 \(l+1,r\) 一定是可消除的。所以我们可以采用字符串哈希来维护每个时刻的栈序列，那么栈序列相同说明该情况下哈希值完全相同。维护每种哈希值出现了多少次，假设一种哈希值出现了 \(k\) 次，那么其对答案的贡献就是 \(k\choose 2\) 。即 \(k\) 个相同的时刻，每次取两个时刻 \(l\) 和 \(r\) 构成的子串 \(
标签：哈希,23,int,真题,long,两题,考虑,我们,消除 From： https://www.cnblogs.com/mountzhu/p/18457992