本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
瑞学堂：瑞瑞的字符统计
【题目描述】
瑞瑞得到了一串由小写字母组成的字符串S SS。他想统计这个字符串中，所有回文子串中，每个字母出现的总次数。
回文串是指正读和反读都一样的字符串。单个字符被视为回文串。
例如，字符串aba的回文子串有：a（位置1），b（位置2），a（位置3），aba（整个串）。其中字母a出现了4 44次，字母b出现了2 22次。
由于结果可能很大，请输出每个字母出现次数对10 9 + 7 10^9+7109+7取模后的结果。
请你帮助瑞瑞编写程序完成这个任务。
【输入】
输入一行一个字符串S SS，仅由小写字母组成。
【输出】
输出26 2626个整数，用空格分隔，依次表示字母a到z在所有回文子串中出现的总次数对10 9 + 7 10^9+7109+7取模的结果。
【输入样例】
aba【输出样例】
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0【核心思想】
问题分析：给定字符串S SS，求所有回文子串中每个字母出现的总次数（对10 9 + 7 10^9+7109+7取模）。这是一个Manacher + 差分数组问题，关键在于：先用 Manacher 求出以每个位置为中心的回文半径，再用差分技巧统计每个位置被多少个回文子串覆盖，最后累加各字母的贡献。
算法选择：
- Manacher 算法：求出以处理后字符串每个位置i ii为中心的最长回文半径d [ i ] d[i]d[i]
- 差分数组（二阶差分）：每个中心i ii的回文串对区间[ i − d [ i ] + 1 , i + d [ i ] − 1 ] [i-d[i]+1, i+d[i]-1][i−d[i]+1,i+d[i]−1]产生"中间高两边低"的三角形贡献，用二阶差分将O ( n 2 ) O(n^2)O(n2)的区间覆盖优化为O ( n ) O(n)O(n)
- 前缀和还原：两次前缀和将差分数组还原为每个位置的实际覆盖次数
关键步骤：
- Manacher 预处理：插入
#统一奇偶回文，计算d [ i ] d[i]d[i] - 二阶差分标记（遍历每个中心i ii）：
- 回文覆盖范围[ l , r ] = [ i − d [ i ] + 1 , i + d [ i ] − 1 ] [l, r] = [i-d[i]+1, i+d[i]-1][l,r]=[i−d[i]+1,i+d[i]−1]
coeff[l] += 1，coeff[i+1] -= 2，coeff[r+2] += 1
- 两次前缀和还原覆盖次数：
cur += coeff[i]（一阶前缀和），sum += cur（二阶前缀和），cnt[i] = sum
- 统计字母贡献：遍历处理后字符串，对实际字符位置i ii（非
#非$），ans[s[i]-'a'] += cnt[i] - 去重修正：每个回文子串被计算了两次（奇数中心和偶数中心），最终答案乘2 22的逆元( M O D + 1 ) / 2 (MOD+1)/2(MOD+1)/2
- Manacher 预处理：插入
时间/空间复杂度：
- 时间复杂度：O ( n ) O(n)O(n)，ManacherO ( n ) O(n)O(n)，差分标记和前缀和O ( n ) O(n)O(n)
- 空间复杂度：O ( n ) O(n)O(n)，处理后字符串、d dd数组、差分数组等
Manacher + 差分的核心思想：
- 回文覆盖的三角形分布：以i ii为中心、半径为R RR的回文串，位置j jj被覆盖当且仅当∣ j − i ∣ < R |j-i| < R∣j−i∣<R，覆盖次数随距离中心增加而递减，形成三角形贡献
- 二阶差分转常数操作：三角形数列的二阶差分为常数，通过
+1, -2, +1的标记将O ( n 2 ) O(n^2)O(n2)的逐点覆盖降为O ( 1 ) O(1)O(1)的区间标记 - 对称性去重：插入
#后，每个实际回文子串既对应某个原字符中心（奇数长度）也对应某个#中心（偶数长度），总贡献被计算两次，需除以2 22 - 模运算技巧：用乘法逆元代替除法，避免浮点精度问题
- 适用于"统计所有回文子串中各位置/字符贡献"的问题，核心在于将回文结构转化为区间覆盖，再用差分优化统计
【算法标签】
#Manacher
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 将int定义为long long，避免中间计算溢出constintN=100005*3,MOD=1e9+7;// N为处理后字符串最大长度，MOD为模数chara[N],s[N];// a存储原始字符串，s存储处理后的字符串（插入分隔符#）intd[N];// d[i]为Manacher算法中以i为中心的最长回文半径intcoeff[N];// coeff用于差分数组，记录每个位置作为回文中心次数的贡献intcnt[N],ans[26];// cnt[i]为位置i在所有回文子串中被覆盖的总次数，ans[26]记录26个字母的出现次数// Manacher算法核心函数：计算以每个位置为中心的最长回文半径voidget_d(char*s,intn){d[1]=1;// 初始化：以第一个字符为中心的回文半径为1// i遍历每个中心位置，l和r维护当前最右回文串的左右边界for(inti=2,l,r=1;i<=n;i++){// 如果当前位置i在当前最右回文串[r]的范围内，利用对称性初始化d[i]if(i<=r)d[i]=min(d[r-i+l],r-i+1);// 中心扩展：尝试向两边扩展回文串while(s[i-d[i]]==s[i+d[i]])d[i]++;// 更新最右回文串边界if(i+d[i]-1>r)l=i-d[i]+1,r=i+d[i]-1;}}signedmain()// 使用signed main配合#define int long long{scanf("%s",a+1);// 读入原始字符串intn=strlen(a+1),k=0;// n为原始字符串长度// 预处理：在原始字符串的每两个字符之间以及首尾插入分隔符'#'s[0]='$';// s[0]放哨兵字符$，防止越界s[++k]='#';// 第一个字符为#for(inti=1;i<=n;i++){s[++k]=a[i];// 放入原始字符s[++k]='#';// 在每个字符后插入#}n=k;// 更新n为处理后字符串的长度get_d(s,n);// 执行Manacher算法// 第一步：利用差分数组统计每个位置被多少个回文子串覆盖for(inti=1;i<=n;i++){intR=d[i];// R为以i为中心的回文半径if(R<=1)continue;// 半径为1表示只有自身（单个#），无实际字符贡献// 回文串在处理后字符串中的覆盖范围intl=i-R+1;// 左边界intr=i+R-1;// 右边界// 差分标记：以i为中心的回文串对区间[l,r]内每个位置的贡献// 使用二阶差分技巧，将三角形贡献转化为常数差分coeff[l]=(coeff[l]+1)%MOD;// 左端点：一阶差分+1// 顶点右侧：一阶差分从+1变-1，净变化-2coeff[i+1]=(coeff[i+1]-2+MOD)%MOD;// 右端点外：一阶差分从-1变0coeff[r+2]=(coeff[r+2]+1)%MOD;}// 第二步：通过两次前缀和还原每个位置被覆盖的次数intcur=0,sum=0;for(inti=1;i<=n;i++){cur=(cur+coeff[i])%MOD;// 一阶前缀和（当前一阶差分值）sum=(sum+cur)%MOD;// 二阶前缀和（当前位置被覆盖的总次数）cnt[i]=sum;// 记录位置i被覆盖的次数}// 第三步：统计每个实际字母的出现次数for(inti=1;i<=n;i++){// 只统计实际字符位置（非#且非$的位置，即原始字符串的字符位置）if(s[i]!='#'&&s[i]!='$'){ans[s[i]-'a']=(ans[s[i]-'a']+cnt[i])%MOD;// 累加该位置被覆盖的次数}}// 第四步：输出结果// 每个实际回文子串在Manacher中被计算了两次（奇数中心和偶数中心各一次），所以答案要除以2intINV2=(MOD+1LL)/2;// 2在模MOD下的逆元（MOD为质数，且MOD为奇数，(MOD+1)/2即为2的逆元）for(inti=0;i<26;i++){ans[i]=ans[i]*INV2%MOD;// 除以2（乘逆元）cout<<ans[i]<<" ";// 输出26个字母的结果}cout<<endl;return0;}【运行结果】
aba 4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
