题解：洛谷 P9753 [CSP-S 2023] 消消乐

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P9753 [CSP-S 2023] 消消乐 - 洛谷【题目描述】小 L 现在在玩一个低配版本的消消乐该版本的游戏是一维的一次也只能消除两个相邻的元素。现在他有一个长度为n nn且仅由小写字母构成的字符串。我们称一个字符串是可消除的当且仅当可以对这个字符串进行若干次操作使之成为一个空字符串。其中每次操作可以从字符串中删除两个相邻的相同字符操作后剩余字符串会拼接在一起。小 L 想知道这个字符串的所有非空连续子串中有多少个是可消除的。【输入】输入的第一行包含一个正整数n nn表示字符串的长度。输入的第二行包含一个长度为n nn且仅由小写字母构成的的字符串表示题目中询问的字符串。【输出】输出一行包含一个整数表示题目询问的答案。【输入样例】8 accabccb【输出样例】5【解题思路】【算法标签】#提高# #线性DP-一维#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN2000005;intn;chars[N];inttoCheck[N][26];intmatch;intdp[N];signedmain(){cinn;// 输入字符串长度ncins1;// 输入字符串从下标1开始存储intans0;// 存储最终答案for(inti1;in;i)// 遍历字符串的每个字符{intvalues[i]-a;// 将当前字符转换为0-25的数字// 查找当前字符之前最近出现的位置matchtoCheck[i-1][value];if(match0)// 如果之前没有出现过当前字符{match1;// 设置为1表示从第一个字符开始}else// 如果之前出现过当前字符{inttempmatch-1;// 找到匹配位置的前一个位置// 状态转移当前位置的贡献等于匹配位置前一个位置的贡献加1dp[i]dp[temp]1;ansdp[i];// 累加到答案中// 复制状态将temp位置的状态信息复制到当前位置for(intk0;k25;k){toCheck[i][k]toCheck[temp][k];}}// 更新当前位置字符的最新出现位置toCheck[i][s[i]-a]i;}coutansendl;// 输出最终答案return0;// 程序正常结束}【运行结果】8 accabccb 5