QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#766426#9586. 野兽节拍forget-star#TL 2ms10052kbC++201.9kb2024-11-20 17:17:302024-11-20 17:17:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 17:17:39]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:10052kb
  • [2024-11-20 17:17:30]
  • 提交

answer

#include<bits/stdc++.h>
//#define int long long
#define fr(i,a,b) for(int i(a),end##i(b);i<=end##i;i++)
#define fd(i,a,b) for(int i(a),end##i(b);i>=end##i;i--)
#define de fprintf(stderr,"on-%d\n",__LINE__)
using namespace std;
const int maxn=1e6+5;
int n;
char c[maxn];
int nex[maxn],pre[maxn];
int to[maxn];
int solve(int x,int y,int z,int p){
	if(c[p]==0||c[nex[p]]==0||c[nex[nex[p]]]==0)return 0;
	int ans=0;
	if(c[p]==x&&c[nex[p]]==y&&c[nex[nex[p]]]==z){
		nex[pre[p]]=nex[nex[nex[p]]];
		pre[nex[pre[p]]]=pre[p];
		int go=to[p];
		if(go==nex[p])go=to[go];
		if(go==nex[nex[p]])go=to[go];
		if(c[pre[pre[p]]]==x&&c[pre[p]]==y){
			if(y!=x){
				int tmp=to[pre[pre[p]]];
				to[pre[pre[p]]]=go;	
				ans=solve(x,y,z,pre[pre[p]])+1;
				to[pre[pre[p]]]=tmp;
			}
			else {
				int tmp=to[pre[p]];
				to[pre[p]]=go;
				ans=solve(x,y,z,pre[pre[p]])+1;
				to[pre[p]]=tmp;
			}
		}
		else if(c[pre[p]]==x){
			int tmp=to[pre[p]];
			to[pre[p]]=go;
			ans=solve(x,y,z,pre[p])+1;
			to[pre[p]]=tmp;	
		}
		else {
			ans=solve(x,y,z,go)+1;	
		}
		pre[nex[pre[p]]]=nex[nex[p]];
		nex[pre[p]]=p;	
	}
	else {
		ans=solve(x,y,z,to[p]);	
	}
	return ans;
}
int fi[100];
vector<int> ANS;
bool operator <(vector<int> A,vector<int> B){
	fr(i,0,2)if(A[i]<B[i])return 1;
	return 0;
}
signed main(){
#ifdef pig
	freopen("pig.in","r",stdin);
	freopen("pig.out","w",stdout);
#endif
	cin>>n;
	scanf("%s",c+1);
	fr(i,1,n)c[i]=c[i]-'a'+1;
	fr(i,1,n-1){
		nex[i]=i+1;
		pre[i+1]=i;
	}
	fd(i,n,1){
		to[i]=fi[c[i]];
		fi[c[i]]=i;
	}
	int ans=0;
	ANS.resize(3);
	ANS[0]=c[1];
	ANS[1]=c[2];
	ANS[2]=c[3];
	fr(i,1,26)if(fi[i])fr(j,1,26)if(fi[j])fr(k,1,26)if(fi[k]){
		int t=solve(i,j,k,fi[i]);
		vector<int> now;
		now.resize(3);now[0]=i;now[1]=j;now[2]=k;
		if(t>ans||t==ans&&now<ANS){
			ans=t;
			ANS=now;
		}
	}
	cout<<ans<<'\n';
	fr(i,0,2)putchar(ANS[i]+'a'-1);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 10052kb

input:

10
aaababbaab

output:

3
aab

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 7752kb

input:

14
liaoningdalian

output:

2
lia

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 7776kb

input:

3
zyl

output:

1
zyl

result:

ok 2 lines

Test #4:

score: -100
Time Limit Exceeded

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...

output:


result: