QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#757826 | #9565. Birthday Gift | piaoyun# | WA | 10ms | 8000kb | C++14 | 2.0kb | 2024-11-17 13:50:30 | 2024-11-17 13:50:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+10;
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int n;
char s[NR];
int f[NR][2][2],g[NR][2][2];
int t[NR];
void work()
{
scanf("%s",s+1);n=strlen(s+1);
t[0]=1;
for(int i=1;i<=n;i++)t[i]=0;
memset(f[0],0x3f,sizeof(f[0]));
memset(g[0],0,sizeof(g[0]));
for(int i=1;i<=n;i++)
{
memset(f[i],0x3f,sizeof(f[i]));
memset(g[i],0,sizeof(g[i]));
if(s[i]!='0'){
//1
for(int a=0;a<=1;a++){
for(int b=0;b<=1;b++){
if(b==1){
f[i][a][b^1]=min(f[i-1][a][b]-1,f[i][a][b^1]);
g[i][a][b^1]=max(g[i-1][a][b]-1,g[i][a][b^1]);
}
else{
f[i][a][b^1]=min(f[i-1][a][b]+1,f[i][a][b^1]);
g[i][a][b^1]=max(g[i-1][a][b]+1,g[i][a][b^1]);
}
if(f[i][a][b^1]==0){
f[i][a][b^1]++,t[i]=1;
if(!g[i][a][b^1])f[i][a][b^1]=0x3f3f3f3f;
}
}
}
if(t[i-1])f[i][1][1]=1;
}
if(s[i]!='1'){
//0
for(int a=0;a<=1;a++){
for(int b=0;b<=1;b++){
if(b==0){
f[i][a][b^1]=min(f[i][a][b^1],f[i-1][a][b]-1);
g[i][a][b^1]=max(g[i][a][b^1],g[i-1][a][b]-1);
}
else{
f[i][a][b^1]=min(f[i][a][b^1],f[i-1][a][b]+1);
g[i][a][b^1]=max(g[i][a][b^1],g[i-1][a][b]+1);
}
if(f[i][a][b^1]==0){
f[i][a][b^1]++,t[i]=1;
if(!g[i][a][b^1])f[i][a][b^1]=0x3f3f3f3f;
}
}
}
if(t[i-1])f[i][0][0]=1;
}
// for(int a=0;a<=1;a++){
// for(int b=0;b<=1;b++){
// printf("dp[%d][%d][%d]=%d %d\n",i,a,b,f[i][a][b],g[i][a][b]);
// }
// }
// cout<<"------------------------"<<t[i]<<endl;
}
int ans=0x3f3f3f3f;
if(t[n])ans=0;
for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)ans=min(ans,f[n][i][j]);
printf("%d\n",ans);
}
int main()
{
int T=read();while(T--)work();
return 0;
}
/*
5
0110101
01020102
0000021111
1012121010
0100202010
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5852kb
input:
5 0110101 01020102 0000021111 1012121010 0100202010
output:
3 4 0 6 0
result:
ok 5 number(s): "3 4 0 6 0"
Test #2:
score: -100
Wrong Answer
time: 10ms
memory: 8000kb
input:
50000 1010110101 1010101010 0101010101 0101010010 0101010010 1010101010 0101001010 1010010010 0100101010 1010101001 1010100101 0101010100 0100101011 0101101010 1011010110 1011010101 1010010101 1010010010 0101010101 0010101010 0101011010 0100101010 1010101010 1010010101 1010101101 1101010101 10100101...
output:
0 10 10 4 4 10 0 4 4 6 2 8 2 2 0 4 2 4 10 8 2 4 10 2 4 8 2 8 8 4 8 4 4 6 4 4 4 6 10 10 2 0 0 10 8 10 0 10 10 10 4 10 8 10 0 8 4 0 8 2 8 0 6 2 8 10 2 10 10 2 10 2 10 8 6 4 2 8 8 0 8 10 8 10 8 10 2 6 10 4 10 8 10 4 10 6 10 10 10 6 6 6 4 10 10 10 2 2 8 10 5 10 10 8 3 10 6 10 2 2 8 2 10 4 6 0 10 2 6 2 1...
result:
wrong answer 42nd numbers differ - expected: '2', found: '0'