QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#825741 | #69. Lamps | guleng2007 | 4 | 45ms | 37084kb | C++20 | 1.1kb | 2024-12-21 22:22:13 | 2024-12-21 22:22:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int dp[N][2][2][2];
char s[N], t[N];
int main()
{
int n;
cin >> n;
scanf("%s",s+1);
scanf("%s",t+1);
memset(dp,0x3f,sizeof(dp));
dp[0][0][0][0]=0;
for(int i=0;i<n;i++)
for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++)
for(int bg=0;bg<=1;bg++)
if(dp[i][j][k][bg]<=100000000)
{
for(int newj=0;newj<=1;newj++)
{
int cost=0;
if(newj==1 && j==0)
cost++;
for(int newk=newj^(s[i+1]!=t[i+1]);newk<=1;newk++)
{
int newbg=0;
if(newk==1)
{
if(k==0)
newbg=t[i+1]-'0';
else
newbg=bg;
}
if(newk && (!k || (t[i]!=t[i+1] && t[i+1]-'0'!=bg)))
cost++;
dp[i+1][newj][newk][newbg]=min(dp[i+1][newj][newk][newbg],dp[i][j][k][bg]+cost);
}
}
}
int ans=0x3f3f3f3f;
for(int i=0;i<=1;i++)
for(int j=0;j<=1;j++)
for(int k=0;k<=1;k++)
ans=min(ans,dp[n][i][j][k]);
printf("%d\n",ans);
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 35988kb
input:
1 1 0
output:
1
result:
ok single line: '1'
Test #2:
score: 6
Accepted
time: 4ms
memory: 35428kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 6
Accepted
time: 4ms
memory: 35376kb
input:
2 10 01
output:
1
result:
ok single line: '1'
Test #4:
score: 6
Accepted
time: 0ms
memory: 36112kb
input:
2 01 10
output:
1
result:
ok single line: '1'
Test #5:
score: 6
Accepted
time: 4ms
memory: 36596kb
input:
2 11 00
output:
1
result:
ok single line: '1'
Test #6:
score: 6
Accepted
time: 4ms
memory: 35364kb
input:
2 11 10
output:
1
result:
ok single line: '1'
Test #7:
score: 6
Accepted
time: 3ms
memory: 35224kb
input:
2 11 01
output:
1
result:
ok single line: '1'
Test #8:
score: 6
Accepted
time: 0ms
memory: 36856kb
input:
18 000000000000000000 101010101010101010
output:
9
result:
ok single line: '9'
Test #9:
score: 6
Accepted
time: 0ms
memory: 36000kb
input:
18 111111111111111111 010101010101010101
output:
9
result:
ok single line: '9'
Test #10:
score: 6
Accepted
time: 0ms
memory: 36824kb
input:
17 11111111111111111 10101010101010101
output:
8
result:
ok single line: '8'
Test #11:
score: 6
Accepted
time: 0ms
memory: 35800kb
input:
17 00000000000000000 01010101010101010
output:
8
result:
ok single line: '8'
Test #12:
score: 6
Accepted
time: 0ms
memory: 36492kb
input:
18 110111100010101111 010111100011100000
output:
3
result:
ok single line: '3'
Test #13:
score: 6
Accepted
time: 0ms
memory: 35384kb
input:
17 10110110110110101 01011100100110000
output:
4
result:
ok single line: '4'
Test #14:
score: 6
Accepted
time: 4ms
memory: 35812kb
input:
18 000000110001001000 111111001011011100
output:
3
result:
ok single line: '3'
Test #15:
score: 6
Accepted
time: 0ms
memory: 36336kb
input:
17 11011010101011111 10011000100000101
output:
4
result:
ok single line: '4'
Test #16:
score: 6
Accepted
time: 0ms
memory: 36308kb
input:
18 011011101011011000 001010011011110001
output:
4
result:
ok single line: '4'
Test #17:
score: 6
Accepted
time: 9ms
memory: 36508kb
input:
17 10111101010001010 00111001111010010
output:
4
result:
ok single line: '4'
Test #18:
score: 6
Accepted
time: 0ms
memory: 35284kb
input:
18 100110111111001010 100000001101000010
output:
3
result:
ok single line: '3'
Test #19:
score: 6
Accepted
time: 0ms
memory: 35320kb
input:
17 00101111101000011 00111001111110001
output:
3
result:
ok single line: '3'
Test #20:
score: 6
Accepted
time: 0ms
memory: 36408kb
input:
18 001010100000100100 000100110011100110
output:
4
result:
ok single line: '4'
Test #21:
score: 6
Accepted
time: 3ms
memory: 36008kb
input:
17 11101100011001011 11101110111111111
output:
2
result:
ok single line: '2'
Test #22:
score: 6
Accepted
time: 0ms
memory: 36468kb
input:
18 010101110011000110 011001110000001110
output:
3
result:
ok single line: '3'
Test #23:
score: 6
Accepted
time: 3ms
memory: 36380kb
input:
17 10010100000010010 10010111101001000
output:
4
result:
ok single line: '4'
Test #24:
score: 6
Accepted
time: 4ms
memory: 36464kb
input:
18 001111100001101100 001111001111111100
output:
2
result:
ok single line: '2'
Test #25:
score: 6
Accepted
time: 0ms
memory: 36620kb
input:
17 10011011100011110 10000000011100010
output:
2
result:
ok single line: '2'
Test #26:
score: 0
Wrong Answer
time: 0ms
memory: 35156kb
input:
18 010100101101110100 111000010010101001
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 4
Accepted
Test #59:
score: 4
Accepted
time: 0ms
memory: 36892kb
input:
1 0 0
output:
0
result:
ok single line: '0'
Test #60:
score: 4
Accepted
time: 0ms
memory: 35540kb
input:
1 0 1
output:
1
result:
ok single line: '1'
Test #61:
score: 4
Accepted
time: 0ms
memory: 36608kb
input:
2 00 00
output:
0
result:
ok single line: '0'
Test #62:
score: 4
Accepted
time: 0ms
memory: 35940kb
input:
2 00 10
output:
1
result:
ok single line: '1'
Test #63:
score: 4
Accepted
time: 3ms
memory: 36552kb
input:
2 00 01
output:
1
result:
ok single line: '1'
Test #64:
score: 4
Accepted
time: 4ms
memory: 35624kb
input:
2 00 11
output:
1
result:
ok single line: '1'
Test #65:
score: 4
Accepted
time: 23ms
memory: 37072kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
0
result:
ok single line: '0'
Test #66:
score: 4
Accepted
time: 40ms
memory: 37072kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #67:
score: 4
Accepted
time: 44ms
memory: 37008kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #68:
score: 4
Accepted
time: 41ms
memory: 37084kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
500000
result:
ok single line: '500000'
Test #69:
score: 4
Accepted
time: 39ms
memory: 36976kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
499999
result:
ok single line: '499999'
Test #70:
score: 4
Accepted
time: 31ms
memory: 37068kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1
result:
ok single line: '1'
Test #71:
score: 4
Accepted
time: 39ms
memory: 37084kb
input:
1000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
100
result:
ok single line: '100'
Test #72:
score: 4
Accepted
time: 45ms
memory: 37072kb
input:
999999 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
12345
result:
ok single line: '12345'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%