CCF-GESP计算机学会等级考试2024年9月三级C++T2回文拼接
·

![]()
解析:模拟法,按要求循环验证即可,详见代码:
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin >> n;
while (n--) {
cin >> s;
int len = s.length();
bool flag = 0;//假设不是拼接回文
for(int i = 2; i <= len - 2; i++) { //枚举第一段字符长度
bool f1 = 1, f2 = 1; //假设前后两段都是回文串
//前半段,j为顺序,k为逆序
for(int j = 0, k = i - 1; j < i; j++, k--) {
if (s[j] != s[k]) { //不相等就不是回文串
f1 = 0; //标记为非回文串
break;
}
}
//后半段,j为顺序,k为逆序
for(int j = i, k = len - 1; j < len; j++, k--) {
if (s[j] != s[k]) {//不相等就不是回文串
f2 = 0;//标记为非回文串
break;
}
}
if (f1 == 1 && f2 == 1) {//如果都是回文串
flag = 1;//标记为回文拼接
break;
}
}
if(flag == 1) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
使用函数简化的写法:
#include<bits/stdc++.h>
using namespace std;
string s;
bool f(int l,int r){//判断字符串s从l到r是否为回文串
for(int i=l,j=r;i<j;i++,j--){
if (s[i]!=s[j]) return 0;
}
return 1;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>s;
bool flag=0;
int n=s.size();
for(int i=2;i<=n-2;i++){//枚举前段字符串长度
if (f(0,i-1)&&f(i,n-1)){//分别判断前后段是否为回文
flag=1;
break;
}
}
if (flag==1){
cout<<"Yes\n";
}else{
cout<<"No\n";
}
}
return 0;
}
使用string类和函数的代码:
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> s;
int len = s.length();
bool flag = 0;//假设不是拼接回文
for(int j = 2; j <= len - 2; j++) { //枚举第一段字符长度
string s1 = s.substr(0, j);
string s2 = s.substr(j, len - j + 1);
string t1 = s1;
string t2 = s2;
reverse(t1.begin(), t1.end());//翻转
reverse(t2.begin(), t2.end());//翻转
if (s1 == t1 && s2 == t2) {//如果都是回文串
flag = 1;//标记为回文拼接
break;
}
}
if(flag == 1) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐


所有评论(0)