题解 CF132E 【Bits of merry old England】

· · 题解

这种奇奇怪怪的东西怎么可能是网络流？还真是。

这题折腾了我一整个上午。

打个广告先

首先，仿照CF1187G Gang Up，我们可以按照时间建图，在每个时间点建出（序列中不同数的数量）个点（这些点在下文称作值节点），分别表示当前有没有变量为这一个值。

同时，我们仿照[NOI2008]志愿者招募进行链式建图。因为每个变量赋成每个值的时间段肯定是连续的一段时间，为了限制同时只能有m个变量有值我们自然会想到链式建图以限制流量（链上的点称作链节点）。

在相邻的两个时间段之间连边，表示这个变量可以不修改直接在下一个时间点用。在每一个时间点，都可以将某个变量清空，即从值节点连向对应的链节点，费用为0。

在每一个时间点，都可以给一个变量赋上值，因此从链节点连向值节点，费用为（值节点对应的代价）。

在每一个时间点，都有一个字符要被输出。这意味着必须有一个被赋成当前值的变量。我们使用有上下界的网络流，强行限制当前值的对应值节点必须转移到下一时刻。

最后输出也比较繁琐，反正就是它什么时候边被跑了就意味着这条边所对应的操作是要进行的。

这么一番操作猛如虎后，你敲出了如下代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,num[500],s,t,lim,deg[100100],val[500];
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
namespace MCMF{
    const int N=100000,M=2000000;
    int head[N],cnt,dis[N],fr[N],id[N],S,T,cost;
    struct node{
        int to,next,val,cost;
    }edge[M];
    inline void ae(int u,int v,int w,int c){
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    bool in[N];
    inline bool SPFA(){
        memset(dis,0x3f,sizeof(dis)),dis[S]=0,q.push(S),in[S]=true;
        while(!q.empty()){
            register int x=q.front();q.pop(),in[x]=false;
    //      printf("%d\n",x);
            for(register int i=head[x];i!=-1;i=edge[i].next){
                if(!edge[i].val)continue;
                if(dis[edge[i].to]>dis[x]+edge[i].cost){
                    dis[edge[i].to]=dis[x]+edge[i].cost,fr[edge[i].to]=x,id[edge[i].to]=i;
                    if(!in[edge[i].to])in[edge[i].to]=true,q.push(edge[i].to);
                }
            }
        }
        if(dis[T]==0x3f3f3f3f)return false;
        int x=T,mn=0x3f3f3f3f;
        while(x!=S)mn=min(mn,edge[id[x]].val),x=fr[x];
        cost+=dis[T]*mn,x=T;
        while(x!=S)edge[id[x]].val-=mn,edge[id[x]^1].val+=mn,x=fr[x];
        return true;
    }
}
using namespace MCMF;
vector<int>v;
vector<pair<int,int> >res;
stack<int>bin;
int main(){
    read(n),read(m),memset(head,-1,sizeof(head));
    for(register int i=0;i<n;i++)read(num[i]),v.push_back(num[i]);
    sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin()),lim=v.size();
    s=n*lim+n,t=n*lim+n+1,S=n*lim+n+2,T=n*lim+n+3;
    for(register int i=0;i<n;i++)num[i]=lower_bound(v.begin(),v.end(),num[i])-v.begin();
    for(register int i=0;i<n-1;i++){
        ae(n*lim+i,n*lim+i+1,m,0);
        for(register int j=0;j<lim;j++){
            ae(n*lim+i,i*lim+j,1,__builtin_popcount(v[j]));
            ae(i*lim+j,n*lim+i,1,0);
            if(j==num[i])deg[i*lim+j]--,deg[(i+1)*lim+j]++;
            else ae(i*lim+j,(i+1)*lim+j,1,0);
        }
    }
    ae(s,n*lim,m,0),ae(n*lim+n-1,t,m,0);
    for(register int i=n-1,j=0;j<lim;j++){
        ae(n*lim+i,i*lim+j,1,__builtin_popcount(v[j]));
        ae(i*lim+j,n*lim+i,1,0);
        if(j==num[i])deg[i*lim+j]--,deg[t]++;
        else ae(i*lim+j,t,1,0);     
    }
    ae(t,s,0x3f3f3f3f,0);
    for(register int i=0;i<=t;i++){
        if(deg[i]>0)ae(S,i,deg[i],0);
        if(deg[i]<0)ae(i,T,-deg[i],0);
    }
    while(SPFA());
    for(register int i=0;i<m;i++)bin.push(i);
    for(register int i=0;i<lim;i++)val[i]=-1;
    for(register int i=n*lim;i<n*lim+n;i++){
        for(register int j=head[i];j!=-1;j=edge[j].next){
            if(edge[j].to/lim!=i-n*lim)continue;
            if(!edge[j].cost&&edge[j].val)bin.push(val[edge[j].to%lim]),val[edge[j].to%lim]=-1;
        }
        for(register int j=head[i];j!=-1;j=edge[j].next){
            if(edge[j].to/lim!=i-n*lim)continue;
            if(edge[j].cost&&!edge[j].val)res.push_back(make_pair(bin.top(),v[edge[j].to%lim])),val[edge[j].to%lim]=bin.top(),bin.pop();
        }
        res.push_back(make_pair(-1,val[num[i-n*lim]]));
//      for(int j=0;j<lim;j++)printf("%d ",val[j]);puts("");
    }
    printf("%d %d\n",res.size(),cost);
    for(register int i=0;i<res.size();i++)if(res[i].first==-1)printf("print(%c)\n",'a'+res[i].second);else printf("%c=%d\n",'a'+res[i].first,res[i].second);
    return 0;
}

然后发现，光荣地T飞了……

怎么肥四？我们想一下，这么搞点数最大是n^2=6.25*10^4级别的，边数大概是个8n^2-16n^2，费用流用的又是玄学的SPFA，并且这种很有规律的图好像刚好符合SPFA中关于“网格图”的性质！

在经历一番卡常失败后，我们不得不尝试优化代码。

我们现在的代码是，任何时候任何字符都能自由地清零或赋值。不如我们统一放到被启用前赋值，启用后决定是否保留还是直接放弃吧。

原来，我们每种数值在每个位置都有点。现在，我们可以只保留在当前时刻的值等于该数值时候的点。

打个比方，我们原来的代码中，链节点相当于一条主干道，其它每种值都相当于一条支路。原来，支路可以在任何地方任意上下车；现在，支路只有在出口处（即等于时刻值的时刻）才能上下车。虽然各条支路仍然是相互独立的，但所有支路的总出口数已经变成了n级别的了！

这就可以通过本题。

（代码中脑子没转过来还拆了点，但实际上不用的）

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,num[500],s,t,deg[100100];
inline void read(int &x){
    x=0;
    register char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
namespace MCMF{
    const int N=100000,M=2000000;
    int head[N],cnt,dis[N],fr[N],id[N],S,T,cost,flow;
    struct node{
        int to,next,val,cost;
    }edge[M];
    inline void ae(int u,int v,int w,int c){
//      printf("%d %d %d\n",u,v,c);
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    bool in[N];
    inline bool SPFA(){
        memset(dis,0x3f,sizeof(dis)),dis[S]=0,q.push(S),in[S]=true;
        while(!q.empty()){
            register int x=q.front();q.pop(),in[x]=false;
    //      printf("%d\n",x);
            for(register int i=head[x];i!=-1;i=edge[i].next){
                if(!edge[i].val)continue;
                if(dis[edge[i].to]>dis[x]+edge[i].cost){
                    dis[edge[i].to]=dis[x]+edge[i].cost,fr[edge[i].to]=x,id[edge[i].to]=i;
                    if(!in[edge[i].to])in[edge[i].to]=true,q.push(edge[i].to);
                }
            }
        }
        if(dis[T]==0x3f3f3f3f)return false;
        int x=T,mn=0x3f3f3f3f;
        while(x!=S)mn=min(mn,edge[id[x]].val),x=fr[x];
        cost+=dis[T]*mn,x=T,flow+=mn;
        while(x!=S)edge[id[x]].val-=mn,edge[id[x]^1].val+=mn,x=fr[x];
        return true;
    }
}
using namespace MCMF;
vector<pair<int,int> >res;
stack<int>bin;
map<int,int>val;
int main(){
    read(n),read(m),memset(head,-1,sizeof(head));
    for(register int i=0;i<n;i++)read(num[i]);
    s=n*3,t=n*3+1,S=n*3+2,T=n*3+3;
    for(register int i=0;i<n;i++){
        ae(i,i+n,1,__builtin_popcount(num[i]));
        deg[i+n]--,deg[i+2*n]++;
        ae(i+2*n,i==n-1?t:i+1,1,0);
        for(int j=i+1;j<n;j++)if(num[j]==num[i]){ae(i+2*n,j+n,1,0);break;}
    }
    ae(s,0,m,0),ae(n-1,t,m,0);
    for(int i=0;i<n-1;i++)ae(i,i+1,m,0);
    ae(t,s,0x3f3f3f3f,0);
    for(register int i=0;i<=t;i++){
        if(deg[i]>0)ae(S,i,deg[i],0);
        if(deg[i]<0)ae(i,T,-deg[i],0);
    }
    while(SPFA());
    for(register int i=0;i<m;i++)bin.push(i);
    for(register int i=0;i<n;i++)val[num[i]]=-1;
    for(int i=0;i<n;i++){
        for(int j=head[i];j!=-1;j=edge[j].next)if(edge[j].to==i+n&&!edge[j].val)res.push_back(make_pair(bin.top(),num[i])),val[num[i]]=bin.top(),bin.pop();
        res.push_back(make_pair(-1,val[num[i]]));
        for(int j=head[i+2*n];j!=-1;j=edge[j].next)if(edge[j].to==(i==n-1?t:i+1)&&!edge[j].val)bin.push(val[num[i]]),val[num[i]]=-1;
    }
    printf("%d %d\n",res.size(),cost);
    for(register int i=0;i<res.size();i++)if(res[i].first==-1)printf("print(%c)\n",'a'+res[i].second);else printf("%c=%d\n",'a'+res[i].first,res[i].second);
    return 0;
}