本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程构建回文二【题目描述】小猴有n nn个水晶球排成一排每一个水晶球的颜色都是红、橙、黄、绿、蓝等等26种颜色中的一种这些水晶球从左到右依次编号为1 , 2 , . . . , n 1,2,...,n1,2,...,n。小猴最近刚刚学完回文相关知识点如果一个字符串不论是从左向右看还是从右向左看内容都一样那么这个字符串就是一个回文字符串。例如A B B A ABBAABBAA A A AAAAAAY R U R Y YRURYYRURY和Q QQ都是回文字符串而A B C A ABCAABCA、A B A B ABABABAB和B A BABA则不是。猴博士想要测试一下小猴是否完全理解了回文这个一知识点向他提出了q qq个相关问题。其中第i ii个问题是小猴能否使用编号在l i l_ili​到r i r_iri​之间包括两个端点的所有水晶球经过任意的重排使得l i l_ili​到r i r_iri​之间的所有水晶球在颜色上的排列能构成一个回文即第l i l_ili​个水晶球颜色与第r i r_iri​个水晶球颜色相同第l i 1 l_i1li​1个水晶球颜色与第r i − 1 r_i-1ri​−1个水晶球颜色相同第l i − 2 l_i-2li​−2个水晶球颜色与第r i − 2 r_i-2ri​−2个水晶球颜色相同…。请你帮助小猴统计q qq个问题中一共有多少个问题的结果是能够构成回文。【输入】第一行两个整数n nnq qq第二行一个长度为n nn的字符串s t r strstr表示排成一排的水晶球颜色s t r strstr只包含大写字符A ∼ Z A\sim ZA∼Z其中每一个字符对应一种不同的颜色。接下来q qq行每行两个整数l i , r i l_i,r_ili​,ri​表示一个问题。【输出】一行一个整数表示q个问题中一共有多少个问题的结果是能够构成回文。【输入样例】9 3 ABBCAAATC 1 3 2 6 37【输出样例】2【算法标签】#前缀和【代码详解】#includebits/stdc.husingnamespacestd;intmain(){intn,q;cinnq;// 输入字符串长度和查询次数string s;cins;// 输入字符串sas;// 在开头添加字符使索引从1开始intsum0;// 满足条件的查询数量intlcnt[500005][26];// 二维前缀和数组会占用很大内存// 初始化第一行for(intj0;j26;j){lcnt[0][j]0;}// 计算前缀和for(inti1;in;i)// 遍历每个字符{// 前i个字符中每个字母的出现次数for(intj0;j26;j)// 遍历26个字母{lcnt[i][j]lcnt[i-1][j](s[i]-Aj);}}while(q--)// 处理每个查询{intl,r;cinlr;// 输入查询区间inttong0;// 奇数次出现的字母个数for(inti0;i25;i)// 检查每个字母{// 计算区间[l,r]内字母i的出现次数intcntlcnt[r][i]-lcnt[l-1][i];if(cnt%21)// 如果是奇数次{tong;}}if(tong1)// 最多只有一个字母出现奇数次{sum;// 满足条件}}coutsum;// 输出满足条件的查询数量return0;}【运行结果】9 3 ABBCAAATC 1 3 2 6 3 7 2