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

· · 题解

Slime and Hats 中文题解

为了方便，首先将编号反转，即认为坐在最前面的人是 n ，n-1 坐在其后方，......，1 号坐在最后。

假设第i个人的离开时间为 t_i ，帽子颜色为 c_i 。首先考虑：对于一个确定的帽子序列，如何求出它对应的 \{t_i\} 。如果所有人都是白帽子，那么 t_i=1 。否则，考虑黑帽子中坐在最前方的一个，设他的编号为 x 。最开始，1号听到有人是黑帽子：此时：

由此，第 x 个人在第 x 轮离开，x+1,x+2,\dots,n均在第 x+1 轮离开，且在第 x+1 轮，又开始了一个新的这样的过程。通过上述过程不难知道 t_i 的值：

于是，我们知道 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] 具有如下性质：

假设共有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

#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;
}