QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #198220 | #5501. Ctrl+C Ctrl+V | grass8cow# | AC ✓ | 36ms | 4884kb | C++14 | 680b | 2023-10-03 09:59:39 | 2023-10-03 09:59:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
char c[5010000],O[4]={'a','n','i','a'};
int dp[4],n,dp2[4];
void ad(int &x,int y){x=min(x,y);}
void sol(){
scanf("%s",c+1);n=strlen(c+1);
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
memset(dp2,0x3f,sizeof(dp2));
for(int j=0;j<4;j++)ad(dp2[0],dp[j]+1);
for(int j=0;j<4;j++){
if(O[j]!=c[i]){
if(c[i]=='a')ad(dp2[1],dp[j]);
else ad(dp2[0],dp[j]);
}
else{
if(j<3)ad(dp2[j+1],dp[j]);
}
}
for(int j=0;j<4;j++)dp[j]=dp2[j];
}
int ans=1e9;
for(int j=0;j<4;j++)ad(ans,dp[j]);
printf("%d\n",ans);
}
int main(){
int T;
cin>>T;while(T--)sol();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
input:
3 aniasieurodzilaapotemnicsieniedzialo nicciekawegouanianiagnieszkianialicji jeszczekrotszaautobiografiaani
output:
1 2 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 20ms
memory: 3848kb
input:
10000 aniaanianianianiaviananibnianianianianianiapianianianianianianiaanianianianiananianianianiananifw ananiacnganiaaywbwrkaniahaniaganiaglljaniaouaqrdyaniaypvsgjltrbcvjssrtnehqfzpfvaniahwaniauzncovwfmiqejteiuaniacblxyfikauptesitsitvananianiajndy anianianianianianiaanianianianianiaanianianianianiaa...
output:
13 11 53 16 10 13 35 2 39 7 19 14 47 7 78 34 59 60 21 13 22 18 18 9 77 3 19 14 44 64 18 26 14 4 27 38 9 65 13 27 51 23 3 13 26 69 5 20 32 23 22 13 29 2 23 2 18 21 68 50 21 9 5 6 21 22 77 1 60 54 8 19 51 13 6 18 70 18 22 19 20 4 74 17 26 8 19 78 11 28 72 8 45 21 23 21 15 54 65 14 2 9 10 5 33 78 0 30 ...
result:
ok 10000 lines
Test #3:
score: 0
Accepted
time: 36ms
memory: 3908kb
input:
335 ananianianianianianianianianianianianianianianianianianianianianianianianianianiaanianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianianiananianianianianianianianiananianianianianianianianianianianianianianianianianianianianianianianiania...
output:
3075 476 650 443 510 2446 624 560 2256 679 3138 361 512 300 484 1726 659 559 1887 381 3048 700 507 2769 2688 615 706 631 3009 367 516 535 3150 1759 418 489 1738 2676 497 666 655 2391 547 405 677 2189 492 465 413 2008 2477 2125 2586 1788 439 2765 2781 667 279 294 523 654 414 2126 2156 2175 1855 3135 ...
result:
ok 335 lines
Test #4:
score: 0
Accepted
time: 31ms
memory: 4884kb
input:
5 aanninaiiiiiaaaaaiiniaaiaaanniiaaaiiiainainananinannnaiaiiainnianaainaaiaanannnnnniaiaiainanaaniaaaainaaanaanianiininiaiiaaaaaainaniinaininniiiinaaaannnananniianaananiainiiiniinninnnainaiiiaanaananinaininiiaaanaiiininnanannannnnaiaaaniiaaniaaanaaaiinianniaiiaiinaannaanniiaininaiianaiiiniinaaiiania...
output:
15253 17190 166607 49472 166658
result:
ok 5 lines