题目 题意：给定一个±字符串，奇数位上的字符串的贡献为正，偶数位上的字符串贡献为逆（+符号做-贡献，-符号做+贡献），字符串的权值为字符串上所有位的贡献和。有若干次查询，每次查询区间[l,r]的字符串，需要删掉最少多少字符，才能使该子串的权值刚好为0。 官方题解 思路：定义b[i]为去掉第i位的字符后，剩余字符串的权值。该数组有一个特点，就是相邻的元素的绝对值差值要么0（同号），要么为2（异号）。现在考虑长度为奇数的字符串，我们设第一位为b[1]，最后一位为b[n]。 （1）如果字符串本身为0，则找到了，不需要删字符； （2）假设b[1]或b[n]为0，那么我们就找到权值为0的字符串了，只需删1个字符 （3）如果b[1]和b[n]都不为0，那么我们可以证明，b[1]和b[n]是异号的。（证明很简单，我们可以把字符串首尾4四种组合±,++,-+,—都算一下，即可得出该结论）不妨设b[1]>0,b[n]
关注
打赏
查看更多评论
热门博文
