Codeforces Round #641 Div1.E Slime and Hats 中文题解

Caro23333

2020-05-06 19:40:02

Solution

### Slime and Hats 中文题解 为了方便,首先将编号反转,即认为坐在最前面的人是 $n$ ,$n-1$ 坐在其后方,......,$1$ 号坐在最后。 假设第$i$个人的离开时间为 $t_i$ ,帽子颜色为 $c_i$ 。首先考虑:对于一个确定的帽子序列,如何求出它对应的 $\{t_i\}$ 。如果所有人都是白帽子,那么 $t_i=1$ 。否则,考虑黑帽子中坐在最前方的一个,设他的编号为 $x$ 。最开始,$1$号听到有人是黑帽子:此时: - $x=1$,他发现前方都是白帽子,因此他是黑帽子,于是他离开,下一轮所有人根据$1$的思维过程判断出他们都是白帽子,也离开,于是 $t_1=1$ 且 $t_i=2,i\ge 2$ - $x\ge 2$,他发现前方有黑帽子,因此他无法判断自己是不是黑帽子,于是他不离开,于是所有其他人都知道 $2,3,\dots,n$ 当中有黑帽子,故问题转化到 $2,3,\dots,n$ 上。依此类推,直到第 $x$ 轮,$x$ 知道 $x,x+1,\dots,n$ 当中有黑帽子,但 $x+1,x+2,\dots,n$ 中没有黑帽子,因此他自己是黑帽子,他离开,他前方的人在第 $x+1$ 轮离开。 由此,第 $x$ 个人在第 $x$ 轮离开,$x+1,x+2,\dots,n$均在第 $x+1$ 轮离开,且在第 $x+1$ 轮,又开始了一个新的这样的过程。通过上述过程不难知道 $t_i$ 的值: - $c_i=1$,则 $t_i=\sum\limits_{j\ge i,c_j=1}j$ ,此时,记 $b_i=i$ 。 - $c_i=0$,设 $k$ 是坐在他后方的最靠前的黑帽子,则 $t_i=t_k+1$ 。为了方便,规定$0$是一个不参与游戏的黑帽子,$t_0=\sum\limits_{c_j=1}j$,这样,$k$就一定存在。记$b_i=k$。 于是,我们知道 $c_1,c_2,\dots,c_n$ 后就能推出 $t_1,t_2,\dots,t_n$ ,同时有 $t_i=t_{b_i}+(1-c_i)$ *** 接下来,考虑如何解决原问题。对于$i\ge j$,如果$c_i=c_j=1$,易知$t_i\le t_j$。又对于$i>j$,有$b_i\ge b_j$,因此 $$ \forall i>j, t_i-t_j=t_{b_i}+(1-c_i)-t_{b_j}-(1-c_j)=t_{b_i}-t_{b_j}+(c_j-c_i)\le c_j-c_i\le $$ 事实上,对于 $i>j$ ,我们有 $$ \left\{ \begin{array}{lcl} t_i-t_j=1,\ \textrm{if}\ c_j=1\ \textrm{and}\ \forall i\ge k>j,c_k=0 \\ t_i-t_j=0,\ \textrm{if}\ \exists i>k>j,c_k=1,c_1=c_2=\dots=c_{k-1}=c_{k+1}=\dots=c_n=0\ \textrm{or}\ \forall i\ge k\ge j,c_k=0 \\ t_i-t_j<0,\ \textrm{otherwise} \end{array} \right. $$ 通过简单的分类讨论不难证明。 因此,对已经给出的$t$,将满足$i>j,t_i\ge t_j$的$i,i-1,i-2,\dots,j$合并,最终会得到若干个不交的连续区间,称每一个这样的区间为好区间,则每一个满足 $l \neq 1$ 的好区间 $[l,r]$ 具有如下性质: - $c_{l+1}=c_{l+2}=\dots=c_r=0$ - $b_l=b_{l+1}=\dots=b_r$,记其为 $B[l,r]$ 假设共有$m$个这样的区间$[l_1,r_1],[l_2,r_2],\dots,[l_m,r_m]$,满足$1\le l_1\le r_1<l_2\le r_2<\dots<l_m\le r_m\le n$。考虑dp,记$f_{i,0/1}$为只考虑$[l_i,r_i],[l_{i+1},r_{i+1}],\dots,[l_m,r_m]$这些区间,$c_{l_i}=0/1$时,$B[l_i,r_i]$的最大值,若无解则$f_{i,0/1}=-1$。 考虑如何从$f_{i+1,j}$转移到$f_{i,j'}$。若$f_{i+1,j}=-1$,则不更新$f_{i,j'}$;否则,从大到小枚举可能的$f_{i,j'}$,那么只需满足 $$ t_{f_{i,j'}}=\sum\limits_{k\ge f_{i,j'},c_k=1}k=\left(\sum\limits_{k\ge f_{i+1,j},c_k=1}k\right) + \left(\sum\limits_{f_{i+1,j}>k\ge f_{i,j'},c_k=1}k\right) =t_{f_{i+1,j}}+f_{i,j'}+\sum\limits_{r_i<k<f_{i+1,j},c_j=1}k $$ 注意到 $t_{f_{i,j'}},f_{i,j'},t_{f_{i+1,j}}$ 这三项都是已知的,只需要检查$[r_i+1,f_{i+1,j}-1]$中能否选择若干个互不相同的整数之和为 $t_{f_{i,j'}}-f_{i,j'}-t_{f_{i+1,j}}$。只需考虑对给定的正整数$d,L,R$如何在较短的时间内判断$d$能否表示成$[L,R]$当中若干个互不相同的整数之和。 这一问题有许多种解法,这里提供一种需要考虑的细节较少的:如果在$[L,R]$中选择的正整数数量为$num$,则$[L+(L+1)+\dots+(L+num-1),(R-num+1)+(R-num+2)+\dots+R]$当中的所有数都能被表示。二分$num$就可以用$O(\log n)$的复杂度完成这个子问题。 注意到当 $l_1=1$ 时,$[l_1,r_1]$ 并不满足前面的性质,因此不能直接转移,但 $[l_1 ,r_1]$ 当中至多有一个$i$ 满足 $c_i = 1$ ,我们可以暴力枚举这个 $1$ 的位置进行转移,复杂度仍然是 $O(n \log n)$ 的。 于是,我们得到了 $f_{i,0/1}$ ,通过在转移时记录转移到 $f_{i,0/1}$ 的状态很容易给出一组解。至此,问题已经得到了解决,其时间复杂度为$O(n\log n)$。 Problem and Tutorial by AKEE ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,ll> pii; #define x first #define y second #define pb push_back const int MAXN=200005; int n,m,cnt; pii a[MAXN]; bool avis[MAXN]; struct Range { int l,r,type; ll val; Range(){} Range(int l,int r,int type,ll val):l(l),r(r),type(type),val(val){} }b[MAXN]; int f[2][MAXN],wh[2][MAXN],res[MAXN]; vector<int> str[2][MAXN]; bool check(ll s,int l,int r) { if(s<=0)return !s && r-l+1>=0; ll L=1,R=r-l+1,mid,ans=0; while(L<=R) { mid=(L+R)>>1; if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1; else R=mid-1; } return s*2<=(r+r-ans+1)*ans; } void modify(ll s,int l,int r,vector<int> &tar,int start) { ll L=1,R=r-l+1,mid,ans=0; while(L<=R) { mid=(L+R)>>1; if((l+l+mid-1)*mid<=s*2)ans=mid,L=mid+1; else R=mid-1; } for(int i=l;i<=r;i++) if(ans && (i+i+ans-2)*(ans-1)<=(s-i)*2 && (s-i)*2<=(r+r-ans+2)*(ans-1)) {--ans,s-=i;tar.pb(1);} else tar.pb(0); } void update(int i,int ti,int ti_1,int pos,ll d) { if(pos<=f[ti][i])return; str[ti][i].clear(); f[ti][i]=pos;wh[ti][i]=ti_1; str[ti][i].pb(1); for(int j=f[ti][i]+1;j<=b[i].r;j++)str[ti][i].pb(0); modify(d-f[ti][i],b[i].r+1,f[ti_1][i-1]-1,str[ti][i],f[ti][i]); } int main() { #ifndef ONLINE_JUDGE //freopen("code.in","r",stdin); //freopen("code.out","w",stdout); #endif scanf("%d",&n); for(int i=1;i<=n;i++) { ll y; scanf("%lld",&y); if(!y)continue; a[++m]=make_pair(n-i+1,y); avis[n-i+1]=1; } if(!m) { for(int i=1;i<=n;i++)putchar('0'); return 0; } sort(a+1,a+m+1); b[cnt=1]=Range(a[m].x,a[m].x,2,a[m].y); for(int i=m-1;i;i--) { if(a[i].y==a[i+1].y)b[cnt].l=a[i].x,b[cnt].type=0; else if(a[i].y==a[i+1].y-1)b[cnt].l=a[i].x,b[cnt].type=1,b[cnt].val--; else b[++cnt]=Range(a[i].x,a[i].x,2,a[i].y); } b[cnt+1]=Range(-1,-1,0,0); bool error=0; f[0][0]=-1;f[1][0]=n+1; for(int i=1;i<=cnt;i++) { f[0][i]=f[1][i]=-1; for(int t=0;t<=1;t++) if(f[t][i-1]>b[i].r) { if(b[i].type==0 || b[i].type==2) { ll d=(b[i].val-1)-(b[i-1].val-1+t); int pos=-1; for(int j=min(b[i].l-1ll,d);j>b[i+1].r;--j) if(check(d-j,b[i].r+1,f[t][i-1]-1)){pos=j;break;} update(i,0,t,pos,d); } if(b[i].type==1 || b[i].type==2) { ll d=b[i].val-(b[i-1].val-1+t); if(check(d-b[i].l,b[i].r+1,f[t][i-1]-1)) update(i,1,t,b[i].l,d); } } if(f[0][i]<0 && f[1][i]<0 && i==cnt && !b[i].type)error=1; } if(error) { for(int t=0;t<=1;t++) if(f[t][cnt-1]>b[cnt].r) { ll d=(b[cnt].val-1)-(b[cnt-1].val-1+t); int pos=-1; for(int j=min((ll)b[cnt].r,d);j>=b[cnt].l;--j) { if(avis[j])continue; if(check(d-j,b[cnt].r+1,f[t][cnt-1]-1)){pos=j;break;} } update(cnt,0,t,pos,d); } } int cur=(f[1][cnt]>0); for(int i=1;i<f[cur][cnt];i++)res[i]=0; for(int i=cnt;i>0;i--) { for(int j=0;j<(int)str[cur][i].size();j++)res[j+f[cur][i]]=str[cur][i][j]; cur=wh[cur][i]; } for(int i=n;i>0;i--)putchar(res[i]+'0'); return 0; } ```