#include <bits/stdc++.h> using namespace std; #define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll long long ll mod=1000000007; int inf=1000000007; ll infl=1000000000000000007; int ile[100007]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt; cin>>tt; while(tt--) { int n; cin>>n; for(int i=1;i<=n;i++) ile[i]=0; string s; cin>>s; s='#'+s; for(int i=1;i<=n;i++) { if(s[i]=='1') { for(int j=i+1;j<=n;j++) { if(s[j]=='1') break; ile[j]++; } } } for(int i=n;i>0;i--) { if(s[i]=='1') { for(int j=i-1;j>0;j--) { if(s[j]=='1') break; ile[j]++; } } } vector<pair<int,int>>V; int c=0,ans=0; for(int i=1;i<=n;i++) { if(s[i]=='1') { ans++; if(c) { if(ile[i-1]) ans+=c; if(ile[i-1]==1) V.pb({2*c,1}); if(ile[i-1]==2) V.pb({c,2}); } c=0; } else c++; } if(c) { if(ile[n]) ans+=c; if(ile[n]==1) V.pb({2*c,1}); if(ile[n]==2) V.pb({c,2}); } sort(all(V),greater<pair<int,int>>()); // cout<<ans<<endl; int it=0; for(auto x:V) { // cout<<x.st<<" "<<x.nd<<endl; if(x.nd==1) { ans-=max(0,x.st/2-it); it++; } if(x.nd==2) { if(x.st-2*it<=2&&x.st-2*it>0) { ans--; it++; } else { ans-=max(0,x.st-2*it-1); it+=2; } } } cout<<ans<<endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #include <bits/stdc++.h> using namespace std; #define endl '\n' #define st first #define nd second #define pb push_back #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define ll long long ll mod=1000000007; int inf=1000000007; ll infl=1000000000000000007; int ile[100007]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt; cin>>tt; while(tt--) { int n; cin>>n; for(int i=1;i<=n;i++) ile[i]=0; string s; cin>>s; s='#'+s; for(int i=1;i<=n;i++) { if(s[i]=='1') { for(int j=i+1;j<=n;j++) { if(s[j]=='1') break; ile[j]++; } } } for(int i=n;i>0;i--) { if(s[i]=='1') { for(int j=i-1;j>0;j--) { if(s[j]=='1') break; ile[j]++; } } } vector<pair<int,int>>V; int c=0,ans=0; for(int i=1;i<=n;i++) { if(s[i]=='1') { ans++; if(c) { if(ile[i-1]) ans+=c; if(ile[i-1]==1) V.pb({2*c,1}); if(ile[i-1]==2) V.pb({c,2}); } c=0; } else c++; } if(c) { if(ile[n]) ans+=c; if(ile[n]==1) V.pb({2*c,1}); if(ile[n]==2) V.pb({c,2}); } sort(all(V),greater<pair<int,int>>()); // cout<<ans<<endl; int it=0; for(auto x:V) { // cout<<x.st<<" "<<x.nd<<endl; if(x.nd==1) { ans-=max(0,x.st/2-it); it++; } if(x.nd==2) { if(x.st-2*it<=2&&x.st-2*it>0) { ans--; it++; } else { ans-=max(0,x.st-2*it-1); it+=2; } } } cout<<ans<<endl; } return 0; } |