Starter 189-Blocks in a String（减少块的数量） · znzryb
## 思路讲解
使用分块以及分块思想，考虑一个未定义元素块。
[https://www.codechef.com/problems/BLOCKSTR?tab=solution](https://www.codechef.com/problems/BLOCKSTR?tab=solution)
那么我们这个为什么可以ans-=2？
```cpp
....01????10.....
```
这种情况自然不必多说，那么确实是实打实的减少了2个块。
```cpp
.....11??????11?????11......
```
那么我们的疑惑是这种情况下-2，-2可以吗？答案当然是可以的，这里的“？”全部变为1了以后总块数就是1了
```cpp
sort(all(cnts[0]));
sort(all(cnts[1]),greater<ll>());
sort(all(cnts[2]),greater<ll>());
ll ans=oans;
vector<bool> alde(N+5,false);
FOR(i,0,N){
if(i<cnt1){
cout<<-1<<" ";
continue;
}
if(i>N-cnt0){
cout<<-1<<" ";
continue;
}
if(i==cnt1){
cout<<ans<<" ";
continue;
}
if(!cnts[2].empty()){ // 1 1
ll id=SZ(cnts[2])-1;
cnts[2][id]--;
if(cnts[2][id]<=0){
cnts[2].pop_back();
ans-=2;
}
cout<<ans<<" ";
continue;
}
if(!cnts[1].empty()){
ll id=SZ(cnts[1])-1;
cnts[1][id]--;
if(cnts[1][id]<=0){
cnts[1].pop_back();
}
cout<<ans<<" ";
continue;
}
if(!cnts[0].empty()){
ll id=SZ(cnts[0])-1;
if(!alde[id]) ans+=2;
cnts[0][id]--;
alde[id]=true;
if(cnts[0][id]<=0){
cnts[0].pop_back();
}
cout<<ans<<" ";
continue;
}
}
```
## AC代码
[https://www.codechef.com/viewsolution/1168370649](https://www.codechef.com/viewsolution/1168370649)
::: 源代码
```cpp
// Problem: Blocks in a String
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/BLOCKSTR?tab=statement
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
using ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
using i128 = __int128;using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT;
char S[MAXN];
/*
*/
inline void init(){
}
inline void solve(){
cin>>N;
init();
ll cnt1=0,cnt0=0;
FOR(i,1,N){
cin>>S[i];
if(S[i]=='1') ++cnt1;
else if(S[i]=='0') ++cnt0;
}
S[N+1]='\0',S[0]='\0';
ll idx=1;
vector<vector<ll> > g(N+5);
FOR(i,1,N){
if(S[i]!='?') continue;
if(g[idx].empty() || i-g[idx].back()==1 ){
g[idx].pb(i);
}else{
++idx;
g[idx].pb(i);
}
}
ll oans=1;char up=S[1];
FOR(i,2,N){
char ch=S[i];
if(ch=='?') ch='0';
if(ch!=up){
++oans;
up=ch;
}
}
vector<vector<ll> > cnts(N+5);
FOR(i,1,idx){
if(g[i].empty()) continue;
ll l=g[i].front(),r=g[i].back();
ll id=S[l-1]-'0'+S[r+1]-'0';
cnts[id].pb(r-l+1);
}
sort(all(cnts[0]));
sort(all(cnts[1]),greater<ll>());
sort(all(cnts[2]),greater<ll>());
ll ans=oans;
#ifdef LOCAL
debug(ans);debug(oans);
#endif
vector<bool> alde(N+5,false);
FOR(i,0,N){
if(i<cnt1){
cout<<-1<<" ";
continue;
}
if(i>N-cnt0){
cout<<-1<<" ";
continue;
}
if(i==cnt1){
cout<<ans<<" ";
continue;
}
if(!cnts[2].empty()){ // 1 1
ll id=SZ(cnts[2])-1;
cnts[2][id]--;
if(cnts[2][id]<=0){
cnts[2].pop_back();
ans-=2;
}
cout<<ans<<" ";
continue;
}
if(!cnts[1].empty()){
ll id=SZ(cnts[1])-1;
cnts[1][id]--;
if(cnts[1][id]<=0){
cnts[1].pop_back();
}
cout<<ans<<" ";
continue;
}
if(!cnts[0].empty()){
ll id=SZ(cnts[0])-1;
if(!alde[id]) ans+=2;
cnts[0][id]--;
alde[id]=true;
if(cnts[0][id]<=0){
cnts[0].pop_back();
}
cout<<ans<<" ";
continue;
}
}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1168370649
*/
```
:::
## 心路历程（WA，TLE，MLE……）
这个0？？？0的这个块的排序要反过来，因为我们需要他更持久一点，因为他毕竟是要ans+=2的。
```cpp
sort(all(cnts[0]));
```