HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

蓝桥杯2015年第六届真题-切开字符串-题解（C++代码）

　　作者: HzuQZH　　　　发表时间：2020-10-09 21:06:51 浏览：281　|　评论：0　

原题链接：蓝桥杯2015年第六届真题-切开字符串

### 解题思路： 先从左往右处理出下标i前的正回文子串数量，再从右往左处理出下标i后的非正回文子串的数量，最后两个数组相乘就得处答案。
<br>

### PS：非正回文子串分两种：1、长度为偶数的子串；2、长度为奇数的非回文子串

```cpp
#include<bits/stdc++.h>
#define x first
#define y second
#define mem(h) memset(h,-1,sizeof h)
#define mcp(a,b) memcpy(a,b,sizeof b)
using namespace std;
typedef long long LL;
typedef unsigned long long ull; 
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
namespace IO{
	inline LL read(){
		LL o=0,f=1;char c=getchar();
		while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
		while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
		return o*f;
	}
}using namespace IO;
//#############以上是自定义技巧（可忽略）########## 
const int N=1e5+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e8+7,P=131;
int d[N],ud[N];//d表示从左往右正回文子串数量，ud表示从右往左非正回文子串数量
string s,t;
set<string>e,ne;//存回文子串和非正回文子串
int n;
bool judge(string str){
	string k=str;
	reverse(k.begin(),k.end());
	return str==k;
}
int main(){
	cin>>n>>s;
	for(int i=0;i<n;i++){//枚举子串的右端点
		for(int j=i;j>=0;j-=2){//枚举字串左端点，每次奇数长度取
			int len=i-j+1;//子串长度
			t=s.substr(j,len);//截取子串
			if(judge(t)){//判断是否为回文串
				e.insert(t);//如果是就插入set中
			}
		}
		d[i]=e.size();//d[i]表示下标i前包含的正回文串数量
	}
	for(int i=n-1;i>=0;i--){//枚举子串的左端点
		for(int j=i;j<n;j++){//枚举子串的右端点
			int len=j-i+1;//子串的长度
			t=s.substr(i,len);//截取子串
			int flag=0;
			if(len%2==1){//如果长度为奇
				if(e.find(t)!=e.end()){//在回文子串集合中查看，如果存在就是正回文子串
					flag=1;
				}
			}
			if(!flag){//如果是非正回文子串就插入非正回文子串的集合
				ne.insert(t);
			} 
		}
		ud[i]=ne.size();//ud[i]表示下标i后包含的非正回文串数量
	}
	int res=0;
	for(int i=1;i<n;i++){
		res=max(res,d[i-1]*ud[i]);
	}
	cout<<res<<endl;
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

数列排序（C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

蓝桥杯2015年第六届真题-切开字符串-题解（C++代码）

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【绝对值排序】（C语言代码）

【蟠桃记】（C语言代码）

1011题解

DNA （C语言代码）

数组与指针的问题

排序算法（选择，插入，冒泡）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C二级辅导-温度转换（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

数列排序 （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

蓝桥杯2015年第六届真题-切开字符串-题解（C++代码）

评论区

精彩推荐

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

【绝对值排序】 （C语言代码）

【蟠桃记】 （C语言代码）

1011题解

DNA （C语言代码）

数组与指针的问题

排序算法（选择，插入，冒泡）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C二级辅导-温度转换 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

数列排序（C语言代码）

大神老白（C语言代码）

　　评论区

【绝对值排序】（C语言代码）

【蟠桃记】（C语言代码）

C二级辅导-温度转换（C语言代码）