kevin

用户名：kevin516

访问量：3939

签　名：

等　　级
排　　名	1774
经　　验	2649
参赛次数	10
文章发表	9
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2015年第六届真题-切开字符串-题解(C++代码)
浏览：481

蛇行矩阵-题解(C++代码)
浏览：269

你可能喜欢

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

　　作者: kevin　　　　发表时间：2020-03-02 10:26:31 浏览：481　|　评论：0　

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

思路：
正回文子串是长度为奇数的回文子串，它的条件有两个，一是字符串必须是回文串，二是长度为奇数。
非正回文子串，也有两种情况，一是根本不是回文串，二是长度为偶数的回文串。
从左到右遍历，记录下每个位置的正回文子串的个数
从右到左遍历，记录每个位置的非正回文子串的个数
用两个数组分别记录每个位置的正回文子串和非正回文子串的数量，最后求最大值

代码：

#include<iostream>
	#include<algorithm>
	#include<set>
	using namespace std;
	typedef long long ll;
	const int N=100000;
	bool  judge(string str){
	      string t = str;
		  reverse( t.begin() ,t.end());
		  if( t == str )
	  	      return true;
	      return false; 
	}
	int main (){
		int n ;
		string str,temp;
		cin>>n;
		cin>>str;
		ll zheng[N];
		ll fei[N];
		set<string> e,ne;
		for( int i=0;i<n;i++){
		 	 for(int j=i;j>=0;j-=2){//j-=2 
			    int t=i-j+1;
				temp=str.substr(j,t);
				int flag =judge(temp);
				if(flag)
					e.insert(temp);
			}
			zheng[i]=e.size();
		}
		for (int i=n-1;i>=0;i--){
		     for(int j=i;j<n;j++){
				int flag=0;
				int t=j-i+1;
				temp=str.substr(i,t);
				if(temp.size()%2)
					if( e.find(temp)!=e.end())
						flag=1;
				if( !flag)
					ne.insert(temp);
			}
			fei[i]=ne.size();
		}
		ll ans=0;
		for(int i=1;i<n;i++)
			ans=max(ans,zheng[i-1]*fei[i]);
		cout<<ans<<endl;
		return 0;
	}

0.0分

3 人评分

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

kevin

TA的其他文章

你可能喜欢

勾股数（Java代码）

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

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

（格式错误） qq290048663 碰巧告知我吧

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

评论区

精彩推荐

母牛的故事（C语言代码）

C语言训练-自由落体问题（C语言代码）

格式化数据输出（C语言代码）

多输入输出练习2 （C语言代码）

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

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

C语言训练-列出最简真分数序列* （C语言代码）

1415题求解

素数的个数一直是超时

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

kevin

TA的其他文章

你可能喜欢

勾股数 （Java代码）

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

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

（格式错误） qq290048663 碰巧告知我吧

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

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

评论区

精彩推荐

母牛的故事 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

格式化数据输出 （C语言代码）

多输入输出练习2 （C语言代码）

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

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

C语言训练-列出最简真分数序列* （C语言代码）

1415题求解

素数的个数 一直是超时

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

勾股数（Java代码）

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

　　评论区

母牛的故事（C语言代码）

C语言训练-自由落体问题（C语言代码）

格式化数据输出（C语言代码）

素数的个数一直是超时