当前位置：首页 > news >正文

题解：学而思编程构建回文（二）

news 2026/6/25 21:37:38

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

学而思编程：构建回文（二）

【题目描述】

小猴有n nn个水晶球排成一排，每一个水晶球的颜色都是红、橙、黄、绿、蓝等等26种颜色中的一种，这些水晶球从左到右依次编号为1 , 2 , . . . , n 1,2,...,n1,2,...,n。

小猴最近刚刚学完回文相关知识点：如果一个字符串不论是从左向右看，还是从右向左看，内容都一样，那么这个字符串就是一个回文字符串。例如A B B A ABBAABBA，A A A AAAAAA，Y 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_i+1li+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 nn，q 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

【输出样例】

【算法标签】

#前缀和

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,q;cin>>n>>q;// 输入字符串长度和查询次数string s;cin>>s;// 输入字符串s='a'+s;// 在开头添加字符，使索引从1开始intsum=0;// 满足条件的查询数量intlcnt[500005][26];// 二维前缀和数组，会占用很大内存// 初始化第一行for(intj=0;j<26;j++){lcnt[0][j]=0;}// 计算前缀和for(inti=1;i<=n;i++)// 遍历每个字符{// 前i个字符中，每个字母的出现次数for(intj=0;j<26;j++)// 遍历26个字母{lcnt[i][j]=lcnt[i-1][j]+(s[i]-'A'==j);}}while(q--)// 处理每个查询{intl,r;cin>>l>>r;// 输入查询区间inttong=0;// 奇数次出现的字母个数for(inti=0;i<=25;i++)// 检查每个字母{// 计算区间[l,r]内字母i的出现次数intcnt=lcnt[r][i]-lcnt[l-1][i];if(cnt%2==1)// 如果是奇数次{tong++;}}if(tong<=1)// 最多只有一个字母出现奇数次{sum++;// 满足条件}}cout<<sum;// 输出满足条件的查询数量return0;}