根本不知道自己在写什么,玄关
查看原帖
根本不知道自己在写什么,玄关
739307
All_Failed_OI_Cici楼主2024/8/15 20:28

样例都过不了,马拉车算法也不太会写,还问有没有人能帮我康一康?

#include<bits/stdc++.h>
using namespace std;
const int M=2e4+10;
struct node{
	char c;
	int id;//位置 
};
vector<node> a;
string str;
char x;
int mal,mar;
bool judge(char a,char b){
	if((a==b-'a'+'A'&&isupper(a)&&islower(b))||(b==a-'a'+'A'&&isupper(b)&&islower(a))||a==b) return true;
	else return false;
}
string mnc(){
	string temp="#";
	for(int i=0;str[i];i++){
		(temp+=str[i])+="#";
	}
	return temp;
}
void print(int l,int r){
	for(int i=l;i<=r;i++) cout<<a[i].c;
}
signed main(){
	int num=0;
	while(x!=EOF){
		x=getchar();
		str+=x;
	}
	for(int i=0;i<str.size();i++){
		if(isupper(str[i])||islower(str[i])) a.push_back({str[i],i});
	}
	string s=str;
	for(int i=0;i<str.size();i++){
		if(!isupper(str[i])&&!islower(str[i])) str.erase(i,1);
	}
	str=mnc();
	int *r=(int *)calloc(sizeof(int),str.size()),c=0,ans=0,an=0;
    for(int i=0;i<str.size();++i){
        if(c+r[c]>i) r[i]=min(r[2*c-i],c+r[c]-i);
        while(i-r[i]>=0&&judge(str[i-r[i]],str[i+r[i]])) ++r[i];
        --r[i];
        if(i+r[i]>c+r[c]) c=i;
        if(ans<r[i]){
        	ans=r[i];
//        	int y;
        	if(str[i]=='#'){
        		an=r[i]*2+1;
			}
        	else{
        		an=r[i]*2;
			}
			mal=s.find(str[i-r[i]]);
        	mar=s.find(str[i+r[i]]);
		}
        //ans=max(ans,r[i]);
    }
    cout<<an<<endl;
    print(mal,mar);
	return 0;
}

谢谢大佬,勿喷,毕竟我只是个蒟蒻

2024/8/15 20:28
加载中...