题解：CF1349E Slime and Hats
0.前言：
题解区唯二的两篇题解，一篇是官方题解的翻译过分复杂，一篇是 wt 巨佬的讲的过分简略，导致我研究了半个早上+一整个晚上还是和机房同学共同讨论才会做。我太菜了qwq。 同时应该是人生第一道 *3500，遂写篇题解纪念一下。
注意：此题解以文字讲解为主，更习惯看推一坨式子的可移步官方题解。
1.分析Ⅰ（正向做法）：
首先我们考虑知道每个人的帽子颜色，能否推出每个人在什么时候离开。
首先容易发现，如果没有黑帽子的人，那么所有人会在时刻
其次，如果有黑帽子的人，并且最后一个人看到前面都是白帽子，那么他会在时刻
同理，第
我们发现这个“倒数第几个”每次这么形容太麻烦了，于是我们将序列翻转，即令最前面的人编号为
黑帽子中编号最大的人
2.分析 Ⅱ（预处理出块）：
现在我们开始考虑告诉了你部分人的离开时间
我们借用一下 wt 巨佬的图：
注意：以下所有描述规定前或右表示翻转后的编号大，后或左表示翻转后的编号小，与上图统一。
解释一下图片（感觉没必要解释）：横轴是每个人的编号，注意我们已经翻转了序列，最右边的点是第一个离开的黑帽子，下一时刻他前面的白帽子，也就是最右边的线段，一起离开。
所以除去最左边的那一段，剩下的一定是多个形如“最左边一个单点，右边一段比他高一个单位的线段”这样的东西。
但是由于信息被挖掉了一些，导致图并不完全，我们的任务其实就是补全这个图，也就知道哪些点是黑哪些点是白了。
图不完全，我们尝试将这些散信息合并合并，得到一些我们可以用的信息帮助解题。于是，我们通过认（xue）真（xi）思（ti）考（jie）知道，首先将不确定离开时间的点去掉，将剩下的散点合并为
- 单独的一个点；
- 一条线段；
- 一条线段并且左边有一个比其低一个单位的点。
下面称散点合并成的东西为块。
首先最开始每个点都认为是类型
对于类型
3.分析 Ⅲ（赋颜色）：
对于类型
定义一些数组、变量。
我们记录第
同时设
再设
为什么我们希望
如何凑时间差呢？首先要求出时间差。
假设现在在第
如果这个块为类型
得到时间差后，我们考虑有哪些数可以来凑这个差。显然自由点编号
给出结论，如果选择
接下来考虑构造解，也就是构造中间的自由点哪些是黑帽子，这个是容易的。二分出
注意，由于 dp 有两种状态，因此对每种合法的状态都应该构造一组解，而解的转移是整个数组转移，不好搞。所以我们只记录到每一个块的构造的解，并记录从哪里转移的即可。
4.Corner CaseⅠ（最左边的块）
我们知道，最左边的块长的并不一样，如果我们按照前面的做法去做却做不出合法解的时候，我们就需要考虑这种情况。并且一定只可能是这种情况，因为保证有解。
考虑最后一个块，显然它应当是类型
5.Corner Case Ⅱ（边界哨兵）
初始化
对于最右边的块，我们可以认为有一个
对于最左边的块，我们可以认为其可以在
6.Code：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,nn,f[200005][2],lst[200005][2],anss[200005];
bool vis[200005];
vector<int> ans[200005][2];
struct node{
int x;
ll t;
}a[200005];
struct seg{
ll l,r,flag,t;
}b[200005];
bool cmp(node x,node y){
return x.x<y.x;
}
ll check(ll tar,int L,int R){
if(tar<=0){//小特判
if(!tar&&R-L+1>=0) return 0;
return -1;
}
ll l=0,r=R-L+1,mid;
while(l<=r){
mid=l+r>>1;
if((L+L+mid-1)*mid/2<=tar) l=mid+1;
else r=mid-1;
}
l--;
return (R+R-l+1)*l/2>=tar? l:-1;
}
void work(int x,int flag,ll l,ll r,ll tar,ll num){
if(!num) return;
ll sum=(l+l+num-1)*num/2;
for(int i=l+num-1,j=r;sum<=tar;i--,j--){
ll sum2=sum-i+j;
if(sum2<tar){
sum=sum2;
}
else{
for(int k=l;k<i;k++){
ans[x][flag].push_back(k);
}
ans[x][flag].push_back(j-(sum2-tar));
for(int k=j+1;k<=r;k++){
ans[x][flag].push_back(k);
}
break;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
if(!x) continue;
vis[n-i+1]=1;
a[++nn]=(node){n-i+1,x};
}
if(!nn){//小特判
for(int i=1;i<=n;i++){
putchar('0');
}
return 0;
}
sort(a+1,a+nn+1,cmp);
b[++m]=(seg){a[nn].x,a[nn].x,0,a[nn].t};
for(int i=nn-1;i>=1;i--){
if(a[i].t==a[i+1].t){
b[m].l=a[i].x;
b[m].flag=1;
}
else if(a[i].t==a[i+1].t-1){
b[m].l=a[i].x;
b[m].flag=2;
b[m].t--;
}
else{
b[++m]={a[i].x,a[i].x,0,a[i].t};
}
}
memset(f,-1,sizeof(f));
f[0][1]=n+1;
b[m+1]=(seg){-1,-1,0,0};
for(int i=1;i<=m;i++){
for(int j=0;j<2;j++){
if(f[i-1][j]==-1) continue;
if(b[i].flag==0||b[i].flag==1){
ll d=(b[i].t-1)-(b[i-1].t+j-1);//j^1=1-j
for(int k=min(b[i].l-1,d);k>b[i+1].r;k--){
ll ok=check(d-k,b[i].r+1,f[i-1][j]-1);
if(~ok){
if(f[i][0]>=k) continue;//注意要最大
f[i][0]=k;
ans[i][0].clear();//清空上一次的答案
ans[i][0].push_back(k);
work(i,0,b[i].r+1,f[i-1][j]-1,d-k,ok);
lst[i][0]=j;
break;
}
}
}
if(b[i].flag==0||b[i].flag==2){
ll d=(b[i].t-b[i].l)-(b[i-1].t+j-1);
ll ok=check(d,b[i].r+1,f[i-1][j]-1);
if(~ok){
if(f[i][1]>=b[i].l) continue;
f[i][1]=b[i].l;
ans[i][1].clear();
ans[i][1].push_back(b[i].l);
work(i,1,b[i].r+1,f[i-1][j]-1,d,ok);
lst[i][1]=j;
}
}
}
}
if(!(~f[m][0]||~f[m][1])){
for(int j=0;j<2;j++){
if(f[m-1][j]==-1) continue;
ll d=(b[m].t-1)-(b[m-1].t+j-1);
for(int k=min(b[m].r,d);k>=b[m].l;k--){
if(vis[k]) continue;
ll ok=check(d-k,b[m].r+1,f[m-1][j]-1);
if(~ok){
if(f[m][0]>=k) continue;
f[m][0]=k;
ans[m][0].clear();
ans[m][0].push_back(k);
work(m,0,b[m].r+1,f[m-1][j]-1,d-k,ok);
lst[m][0]=j;
break;
}
}
}
}
int nw=1;
if(~f[m][0]) nw=0;
for(int i=m;i>=1;i--){
for(int y:ans[i][nw]){
anss[y]=1;
}
nw=lst[i][nw];
}
for(int i=n;i>=1;i--){
putchar(anss[i]+'0');
}
putchar('\n');
return 0;
}略微尸山勿喷qwq。