QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #726019 | #9586. 野兽节拍 | TheZone | AC ✓ | 87ms | 21744kb | C++20 | 2.7kb | 2024-11-08 21:16:44 | 2024-11-08 21:16:44 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define LB lower_bound
using namespace std;using ll=long long;using pii=pair<int,int>;
const int N=1e6+5;
int n;char s[N];
vector<int> S[26][26][26];
int pre[N],nxt[N];
int st[N],sh;
void del(int x){
st[++sh]=x;
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
}
void ins(int x){
pre[nxt[x]]=nxt[pre[x]]=x;
}
int calc(int a,int b,int c){
int p=1,pt=0;
int cnt=0;
while(p<=n){
if(pre[pre[p]]>0&&s[pre[pre[p]]]==a&&s[pre[p]]==b&&s[p]==c){
p=nxt[p];
del(pre[pre[pre[p]]]);
del(pre[pre[p]]);
del(pre[p]);
cnt++;
continue;
}
if(pre[p]>0&&nxt[p]<=n&&s[pre[p]]==a&&s[p]==b&&s[nxt[p]]==c){
p=nxt[nxt[p]];
del(pre[pre[pre[p]]]);
del(pre[pre[p]]);
del(pre[p]);
cnt++;
continue;
}
if(nxt[p]<=n&&nxt[nxt[p]]<=n&&s[p]==a&&s[nxt[p]]==b&&s[nxt[nxt[p]]]==c){
p=nxt[nxt[nxt[p]]];
del(pre[pre[pre[p]]]);
del(pre[pre[p]]);
del(pre[p]);
cnt++;
continue;
}
while(pt<S[a][b][c].size()&&S[a][b][c][pt]<p) pt++;
if(pt==S[a][b][c].size()) break;
p=S[a][b][c][pt]+3;
del(p-3);del(p-2);del(p-1);
cnt++;
}
while(sh) ins(st[sh]),sh--;
return cnt;
}
void Solve(){
scanf("%d%s",&n,s+1);
for(int i=0;i<=n;i++) nxt[i]=i+1,pre[i+1]=i;
for(int i=1;i<=n;i++) s[i]-='a';
for(int i=2;i<n;i++) S[s[i-1]][s[i]][s[i+1]].push_back(i-1);
int tot=0,a1,a2,a3;
for(int x=0;x<26;x++) for(int y=0;y<26;y++) for(int z=0;z<26;z++){
int w=calc(x,y,z);
if(w>tot) tot=w,a1=x,a2=y,a3=z;
}
printf("%d\n%c%c%c",tot,a1+'a',a2+'a',a3+'a');
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
/*#include<bits/stdc++.h>
#define fi first
#define se second
#define LB lower_bound
using namespace std;using ll=long long;using pii=pair<int,int>;
const int N=1e6+5;
int n;char s[N];
vector<int> S[26][26][26];
int pre[N],nxt[N];
int st[N],sh;
void del(int x){
st[++sh]=x;
pre[nxt[x]]=pre[x];
nxt[pre[x]]=nxt[x];
}
void ins(int x){
pre[nxt[x]]=nxt[pre[x]]=x;
}
int calc(int a,int b,int c){
int p=1,pt=0;
int cnt=0;
while(p<=n){
if(pre[pre[p]]>0&&s[pre[pre[p]]]==a&&s[pre[p]]==b&&s[p]==c){
p=nxt[p];
del(pre[pre[pre[p]]]);
del(pre[pre[p]]);
del(pre[p]);
cnt++;
continue;
}
if(pre[p]>0&&nxt[p]<=n&&s[pre[p]]==a&&s[p]==b&&s[nxt[p]]==c){
p=nxt[nxt[p]];
del(pre[pre[pre[p]]]);
del(pre[pre[p]]);
del(pre[p]);
cnt++;
continue;
}
if(nxt[p]<=n&&nxt[nxt[p]]<=n&&s[p]==a&&s[nxt[p]]==b&&s[nxt[nxt[p]]]==c){
p=nxt[nxt[nxt[p]]];
del(pre[pre[pre[p]]]);
del(pre[pre[p]]);
del(pre[p]);
cnt++;
continue;
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}*/
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10028kb
input:
10 aaababbaab
output:
3 aab
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 10160kb
input:
14 liaoningdalian
output:
2 lia
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 10156kb
input:
3 zyl
output:
1 zyl
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 23ms
memory: 18744kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...
output:
3717 aaa
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 23ms
memory: 19580kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaababaaaaaaabababababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaacacacacaaaaacacacacacacacaaacaaaaaaaaaaaaaaaaaadadaaaaaaaaadaaadadaaaaadaaaaadadaaaaaaaaaaaaaaaaaaaaaaeaeaaaaaeaaaaaaaeaeaeaaaaaaaeaaaaaaaaaaaaaaaaaaaafaaaaaaafafafafafa...
output:
7571 xxx
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 19ms
memory: 18452kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaababaaaaaaaaabaaabaaaaaaaaababaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaacaaaaaaaaacacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaadaaaaadaaaaaaaaaaaaaaaaaaaaeaeaeaaaaaeaaaaaeaaaaaeaeaaaeaeaaaaaaaaaaaaaaaaaafafaaafafaaaaaaaaaaa...
output:
6680 xxx
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 29ms
memory: 19668kb
input:
667888 eqjszvsxnlvgskosbdoyavaooutvfysniyfplykvmcnsgaomyeqqokqsrdykzfbzsbtkvotfsmmjgkhjhhxbgntmdzmxmexstdwwjrtsmumrrcvkeoluhcpvazdnoxscqibnyytrryywasediqzfsptsxggweogoxeoxhtxaynefaoscgobuxcprquxqzhircomstyufqkfdykbbuibknkjeyebhssdtqbxsdbqiwgseiaezqldbswtpdziicnnwvmxcozqttffglgefiwzdkbfnqmiuicjdcdodx...
output:
63 uzb
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 8164kb
input:
1000 baddacbabcddacdcbacaccbadddbadbdaddcdabbbcccdaaaddbadcdbddccadbbddcccaaadacdcbcbbccccabdbcbcdadacadcbcdbdbcddccddbbabdcabdabadddbbdacabdbbdddddaacdabdddddddbddbdcbadbcaaddccdbcbddaccdacbdaabbabababdcabdadddbacabcdbcddcdacaaddddbaccbbcbaacbcdcbbcdaacbaddcbcbcadaabacadadbaaababbccaddaccddbccdcbca...
output:
26 ddc
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 10100kb
input:
1000 ddcddcbbbcabbbbbccbaaddcbaaddcabbabbabdaacdcdbacbddabccddcadcaccadbaddcbcdccbddabccadadcdddbaaacdacadadddadacccbbddcacccccaccacccadbbacacbdccdbccdaabdabdabbddacdccdbaacdddcdbadabddbddbddbabcccdccbcddcdbbbcaaacbcdcdbdccabbdbcbadbbbbacddccadbbaddacaddcdbbbdcdbcbbdaaacadbccbabbbaacbcbaababbbabcdac...
output:
27 ddc
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 8176kb
input:
1000 bbccbcaaccbcdccaacbbcbadbabadddaabacadadacbbdacabdbdcaaaddabbabcacbddcdaccbcbcbddcabbbadacaaabcacbaabaccaccbdbbcddbddcadbbabaadcdccbbaacdbaddacaccbbabdacdbbbddccbcdbaccbbcddbbbddaaadccacdddddccbbbdcdadabbbcccbbbdddacbabacdccbdcdbdaacdabaaaccbbccdcddcdcdbcacacccdbabcaaadabbddcdbdbaacaaddcbcbbccb...
output:
24 bab
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 8ms
memory: 20228kb
input:
931528 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
310509 aaa
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 4ms
memory: 20144kb
input:
615161 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205053 aaa
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 4ms
memory: 20184kb
input:
623944 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
200880 aaa
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 38ms
memory: 20316kb
input:
1000000 baabaabbaaaabbababbbabbbabaabbbaaaabaabbababbbbaabbaabbabbbbbbbaaaaabbbbbababaaababbbaababbbbbbaababbbaaabbbbbbbbababbbbabbbbabbbbbbbaabaaabbaaaaaaaaabbabababbabbbbaabbbbbaaabbbbabbbbaababbabaaaaaababbbaabbabbbbaaaabbbbaabbababaababbababbbbaaaabbbbabbaaabbbbaabaaaabbbbbaababaaabbbabaabababba...
output:
191420 aab
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 33ms
memory: 19128kb
input:
1000000 aabbbbbcbacccabaaaccccaacaccccbcaabacaaabacccabbcaccaaacbaabcbacbcaaababacbbacaabcbaaacbbaaaaaabbaaabbcbaabaccaacccacbbaabbaaaaaabbaccbcaabcabcacabcaacbacaccbbcbbbccbbbcaacbaabcacacccbcbacaccaaaccabaaccbbcbbbcbcabbcbabbabacbbbcbbbcacbcabbaaacbaaaccbacacabcccbbabaccaccbcbbccacbbabbbacacabaccc...
output:
40521 ccb
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 36ms
memory: 18116kb
input:
1000000 acdbcbcccdddcccdccadbdcccaaacbbdadbdacacaadcadadccdbbacdbcbddadabbdcbccbcadadbaddabdbadbbdcbcdcabbdabadabaaaddbcdbbaddcaadbcbcdacdbaacdbddbdacaaacadbbcadadacdbdcdcdccddbdddccacacbbcbbccacbdbbbdbcddbdcaccdcdcdbababbdbcbcacddddaadadcdcbbacbbdbddaadbbbbcccccabbadddbbbaaaddccdaadcaddbbdcdcdaabaa...
output:
16769 abd
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 38ms
memory: 18480kb
input:
1000000 abbaccdaecaaeadcaabecddbdedbcbebeeaeabaaaacedcaaabbbcabcbddcdcececcceacacaedeebaddabcdedeadbacabbbaadbeeeebbdaeadcacadadddbdbcaeeeaeddaccdceacebbaabccacdbdacdbcabaeeddeccecdcaeedbadbceebbcddbbeeecdeceabbdccccadcbeedacadceabadabcbcbbecddacbcbbbbbbadbacbdbcdbecadeecbeabceccabccdecccdbdcdbbeeee...
output:
8338 dce
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 39ms
memory: 20416kb
input:
1000000 abbbbbbabbababbbbaabababbbaaaaabbabbaaabababaaaababbbaaaabaababaaababbbaabbbbbbbaaaaabaabbabaabaaabaababaaabbabaaaaabbbbaabaababbbbbbbabaabaaabbabbbaaababaababababbbaababbaabbbbbaaabbaabbbbabbaabaababbaabbbabaaaabbababaabbabbabbabaabbbbaaababbbbbaaaabaaabbaabaaabaabbaabaaabaabaabbbaaaaabbbab...
output:
191383 bba
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 43ms
memory: 19296kb
input:
1000000 aabbcbcaabbabccabbbccabbcbacabccccccbbbcbccbabacacaccccbcbcbacaaaababbbabacacbbccaacbaacbacccabbabbbccbcbbbcbbacacaccbbaacbaaabaabbaccacccbcbbcacbbacabaabbabcacccaccbcacccccccbcbacaabbcbaaabaaabcabbaacabaaaaaccbabaabccbaabacbbcbbaabcbccccbcaccbbbccbbbbaabacbacbbaacbcccccbabacacbcccaaaccccaca...
output:
40925 caa
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 20ms
memory: 20116kb
input:
1000000 babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabb...
output:
333333 abb
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 22ms
memory: 21744kb
input:
999986 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg...
output:
38461 abc
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 2ms
memory: 10348kb
input:
5388 xxyzyzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwaefaegaehaeiaejaekaelaemaenaeoaepaeqaera...
output:
2 xyz
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 32ms
memory: 18872kb
input:
1000000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaafaaf...
output:
87 fwu
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 0ms
memory: 10164kb
input:
6 ababaa
output:
1 aba
result:
ok 2 lines
Test #25:
score: 0
Accepted
time: 0ms
memory: 8120kb
input:
6 aababa
output:
2 aba
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 47ms
memory: 19604kb
input:
1000000 zenudggmyopddhszhrbmftgzmjorabhgojdtfnzxjkayjlkgczsyshczutkdchiytqlfsevymipufxkxojlvkkqxvjhpjmcxeiluubblcdiwjphlpzwvknsyvbcodpyktizgatrlieiikktghixbikehsiknjuateltwkyyhgabygwtclyeyquaoiqnypoxnvyzvyhfejoljxnwhkkcgitdebuutnzzvawollaiesjsnlbdvdarlewlnusmgwhulzimadkzlngoukodeljdpjpxxdljooczhewfz...
output:
90 cze
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 70ms
memory: 19700kb
input:
1000000 rtzxovxqfapkdmelxiyjroohufhbakpmmvaxqcptiwtcijcabvobzwbrespqhpvjidgmlvjetwieqngdfbinbsjyfgxofbunxgmhjnkdhhwzjaqqhxjurewcpktfzgxdheuuyfrcmqxykcxjaeotsutxkedqsoyoxzvcspgbnzrwypgdqnfbxywblqvdufggbbskburngiyxtrauvhxjeposnzhcbxlkcczhvpxdbmegacemorezpcsnlzbbiasssvhgneavpnoeikfrhkxeredmmsuowksdtoon...
output:
88 yqs
result:
ok 2 lines
Test #28:
score: 0
Accepted
time: 51ms
memory: 20860kb
input:
1000000 ljmybiqxmnqqbsoxkyvgdiupdyamxtyvhjvbdsgogfkgghvubrlefmxiorufmakswraubnxjakandedlvsfepzcxnelmzqkeqbqrawwukmicllbvauvtzuajjsmxuuuzvypgzstvpbmpktcluzglzelpaayvyhwkqmzixfotvxjsohrctbgdezsorqehyxozheoxcgcwcellqwdhgdqjxkyiaetlntxbfgkehdlfkoococgfziqkcibndisxwwsanicoxybhrtpphfibclqqbtmaxbendpnagfxb...
output:
87 qfh
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 87ms
memory: 19628kb
input:
1000000 fyyymvhdtbqyaxbiypqdqdaykusyvdgccwsfohwjgrckffnqanhhkaubwqzsrjzcleuatejofztxpvaqmidwghvywbbltfcujzrerfgjoowflukcusivimfoedcoqlstisjtzfvmtnbhllflpuyfhoagswuyfbufmzbncwvocvzngafbvnkfkbrcutmldoxqnikmdtodzzzzmchstallsfjwmjhszqiqhmwcrsaftrzvebgwhydynoiotqhqkrqhgxxufscrvapaebmmxljfiiuoiiomnxhwwxgp...
output:
92 nsk
result:
ok 2 lines
Test #30:
score: 0
Accepted
time: 56ms
memory: 20944kb
input:
1000000 zokbxiahaosfyclumgnaczggrnljumplxknibxmeedvnefhkygdkqosshpegwunnzsohmxxumnnhckwyczaowpoxezqlovukcuuqgrsbrtifngthlquuqdjvyltgjbrmwoefypvdyzqwlainjoqxrzrwktnblvszfndrjodikurlytsayblhpdnrytxnhfejtjfzeeamttmnjgkffwelozvmyosbmoufjpjzbeohbulotcinspqmyurolxwlwloobkszpnddxhrkbxoytmdsqxaetqzmufcslqpd...
output:
89 ynq
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed