核心内容摘要
《深院寂寥：她在禁忌的荒原里，种下了一支带刺的玫瑰》
2023信奥赛C提高组csp-s复赛真题及题解消消乐题目描述小 L 现在在玩一个低配版本的消消乐该版本的游戏是一维的一次也只能消除两个相邻的元素。
现在他有一个长度为n nn且仅由小写字母构成的字符串。
我们称一个字符串是可消除的当且仅当可以对这个字符串进行若干次操作使之成为一个空字符串。
其中每次操作可以从字符串中删除两个相邻的相同字符操作后剩余字符串会拼接在一起。
小 L 想知道这个字符串的所有非空连续子串中有多少个是可消除的。
输入格式输入的第一行包含一个正整数n nn表示字符串的长度。
输入的第二行包含一个长度为n nn且仅由小写字母构成的的字符串表示题目中询问的字符串。
输出格式输出一行包含一个整数表示题目询问的答案。
输入输出样例 1输入 18 accabccb输出 15说明/提示【样例 1 解释】一共有5 55个可消除的连续子串分别是cc、acca、cc、bccb、accabccb。
【数据范围】对于所有测试数据有1 ≤ n ≤ 2 × 10 6 1 \le n \le 2 \times 10^61≤n≤2×106且询问的字符串仅由小写字母构成。
测试点n ≤ n\leqn≤特殊性质1 ∼ 5 1\sim 51∼510 1010无6 ∼ 7 6\sim 76∼7800 800800无8 ∼ 10 8\sim 108∼108000 80008000无11 ∼ 12 11\sim 1211∼122 × 10 5 2\times 10^52×105A13 ∼ 14 13\sim 1413∼142 × 10 5 2\times 10^52×105B15 ∼ 17 15\sim 1715∼172 × 10 5 2\times 10^52×105无18 ∼ 20 18\sim 2018∼202 × 10 6 2\times 10^62×106无特殊性质 A字符串中的每个字符独立等概率地从字符集中选择。
特殊性质 B字符串仅由a和b构成。
思路分析本题要求统计字符串的所有非空连续子串中可消除的个数。
一个字符串可消除当且仅当可以通过反复删除相邻的相同字符最终变为空串。
直接枚举所有子串并模拟消除过程的时间复杂度为 O(n²)无法通过 n ≤ 2×10⁶ 的数据。
需要线性或接近线性的算法。
关键转化用栈模拟消除过程。
维护一个栈遍历字符串若当前字符等于栈顶字符则弹出栈顶否则压入当前字符。
遍历完成后栈为空则整个字符串可消除。
对于子串 s[l…r]其可消除等价于从 l 开始模拟消除过程结束时栈为空。
这等价于从 1 到 l-1 的栈状态与从 1 到 r 的栈状态相同。
因为从 l 开始模拟相当于初始栈为空处理完 s[l…r] 后栈为空意味着从 l-1 的状态出发处理 s[l…r] 后状态不变所以 f[l-1] f[r]其中 f[i] 表示处理完前 i 个字符后的栈状态。
因此问题转化为求有多少对 (l, r) 满足 1 ≤ l ≤ r ≤ n 且 f[l-1] f[r]。
对于每个 r统计有多少个 l 满足 f[l-1] f[r]累加即可。
实现细节用哈希值表示栈状态便于比较和存储。
从左到右扫描用栈维护当前状态同时记录每个位置的哈希值。
使用哈希表记录每个哈希值出现的次数扫描时累加以当前位置结尾的可消除子串数。
注意初始状态 f[0] 也要计入。
代码实现#includebits/stdc.husingnamespacestd;typedefunsignedlonglongull;// 自然溢出哈希constintN2000005;// 最大长度constintB131;// 哈希基数intn;chars[N];// 字符串1-indexedcharstk_c[N];// 栈中字符ull stk_h[N];// 栈中记录的前一个哈希值inttop;// 栈顶指针unordered_mapull,intcnt;// 哈希值出现次数intmain(){scanf(%d,n);scanf(%s,s
;// 从1开始读入ull h0;// 当前哈希值cnt[0]1;// 初始空栈状态出现一次对应f[0]top0;ull ans0;// 答案可能很大用ullfor(inti1;in;i){charcs[i];intvc-a1;// 字符映射为1~26if(topstk_c[top]c){// 栈非空且栈顶字符相同则弹出hstk_h[top];// 恢复弹出前的哈希值top--;}else{// 否则压栈top;stk_c[top]c;stk_h[top]h;// 记录压栈前的哈希值hh*Bv;// 更新哈希值}anscnt[h];// 以i结尾的可消除子串数等于之前相同状态的出现次数cnt[h];// 当前状态出现次数1}printf(%llu\n,ans);return0;}功能分析核心算法利用栈模拟消除过程将子串可消除的条件转化为前缀状态相等从而通过哈希和计数在线性时间内求解。
时间复杂度O(n)。
每个字符最多入栈和出栈一次哈希表操作均摊 O(
。
空间复杂度O(n)。
栈和哈希表最多存储 n 个状态。
注意事项使用自然溢出哈希基数 B 取 131字符映射为 1~26 以避免前导零问题。
初始状态 f[0] 对应空栈哈希值为 0需预先加入计数。
答案可能达到 n(n
/2需使用 64 位无符号整数。
各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}