QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#766496 | #9586. 野兽节拍 | pigpigger | TL | 2ms | 9740kb | C++20 | 1.8kb | 2024-11-20 17:31:11 | 2024-11-20 17:31:11 |
Judging History
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){
to[pre[pre[p]]]=go;
ans=solve(x,y,z,pre[pre[p]])+1;
to[pre[pre[p]]]=p;
}
else {
to[pre[p]]=go;
ans=solve(x,y,z,pre[pre[p]])+1;
to[pre[p]]=p;
}
}
else if(c[pre[p]]==x){
to[pre[p]]=go;
ans=solve(x,y,z,pre[p])+1;
to[pre[p]]=p;
}
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: 0ms
memory: 9740kb
input:
10 aaababbaab
output:
3 aab
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 7724kb
input:
14 liaoningdalian
output:
2 lia
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 9732kb
input:
3 zyl
output:
1 zyl
result:
ok 2 lines
Test #4:
score: -100
Time Limit Exceeded
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...