QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#655822 | #9229. Juliet Unifies Ones | woodie_0064# | AC ✓ | 1ms | 3788kb | C++20 | 1.3kb | 2024-10-19 09:50:28 | 2024-10-19 09:50:29 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 3;
int T;
int n, num;
const int inf = 0x3f3f3f3f;
void work(){
string s;cin >> s;
while(s.back() == '0') s.pop_back();
reverse(s.begin(),s.end());
while(s.back() == '0') s.pop_back();
int n = s.size();
if(n == 0) {
cout << "0\n";
return;
}
auto calc = [&] () {
vector <int> f(n);
f[0] = 0;
int pre = 0,zero = 0,cnt = 0;
for(int i = 0;i < n;i++) {
int j = i;
f[i] = min(cnt,f[pre] + zero);
cnt += 1;
while(j + 1 < n && s[j + 1] == '1') {
j += 1;
f[j] = f[i];
cnt += 1;
}
pre = j;
zero = 0;
while(j + 1 < n && s[j + 1] == '0') {
zero += 1;
j += 1;
f[j] = f[i];
}
// cout << cnt << ' ' << zero << ' ' << i << ' ' << j << '\n';
i = j;
}
// cout << s << '\n';
// for(auto &x : f) cout << x << ' ';
// cout << '\n';
return f;
};
auto f = calc();
reverse(s.begin(),s.end());
auto g = calc();
reverse(g.begin(),g.end());
reverse(s.begin(),s.end());
int ans = inf;
for(int i = 0;i < n;i++) if(s[i] == '1') ans = min(ans,f[i] + g[i]);
cout << ans << '\n';
}
int main(){
// freopen("test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
// cin >> T;
// while(T--){
work();
// }
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
input:
00011011001
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
11101111111111111101001011110111111110011101010110
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
00000000100000000000100000010001000
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
00000000000000000000000000000000000000000000000000
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
00000000100000000000100000011000
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
11000010100100000011101100000001000100000000000000
output:
8
result:
ok 1 number(s): "8"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
01100100111011110101010110000100001111110001110001
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1110101111001
output:
3
result:
ok 1 number(s): "3"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
1001
output:
1
result:
ok 1 number(s): "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
11111111111111111111111111111111111111111111111111
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
11111100000000001101010101100011
output:
9
result:
ok 1 number(s): "9"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
00011011001
output:
2
result:
ok 1 number(s): "2"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
11011
output:
1
result:
ok 1 number(s): "1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
100011011
output:
2
result:
ok 1 number(s): "2"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
0
output:
0
result:
ok 1 number(s): "0"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
1010101010011011001101100110011101101011100110110
output:
19
result:
ok 1 number(s): "19"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
01110100000000111100000011000000000110010001110101
output:
14
result:
ok 1 number(s): "14"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
01100001000000010000000000010010000100100101001000
output:
9
result:
ok 1 number(s): "9"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
1101010101010101010101010101010101010101010101011
output:
23
result:
ok 1 number(s): "23"
Extra Test:
score: 0
Extra Test Passed