其实"序列中1的数量有限"是一个非常重要的条件。这意味着我们可以找到序列中的第一个1和最后一个1。
考虑这样一件事情：初始时我们把一个长度为\(2^{2w+1}\)的"滑块"放在刚好在第一个1前面的位置(这时滑块的内部全是0)，然后每次把滑块向右移动一格(也就是删掉滑块的第一个字符，在末尾再加上一个)，直到滑块移动到序列中最后一个1的右边为止。发现题目中的要求等价于：给每一种滑块的状态分配一个0或1的值，对于任意一个序列做出上面这种操作，序列中1的个数必须等于过程中经过的所有滑块状态的值之和。(这是关键观察)
可能的滑块状态有\(2^{2w+1}\)种，如果一个状态可以通过"向右移动一格"的操作变成另一个状态，我们就在这两个状态之间连有向边。给每条边赋一个权值，如果用这条边转移时在原滑块末尾加上的字符是1则把值赋为-1，否则赋为0。这时题目中的要求就转化为了：对于从"0000000..."(全0)走一圈回到"0000000..."的任意一条路径，它上面所有点和边的权值和为0。(仔细想一下)
而如果序列中的1数量无限，我们压根找不到第一个1和最后一个1，也就不能像这样思考了。
考虑怎么给每个点赋值才能满足上面说的条件。令"0000000..."代表的节点为s。首先对于任意节点i，从s走到i的任意一条路径权值和都是相等的，否则就不满足上面的条件(因为这张有向图显然是强连通的，任何一个点都能走回s)。令\(sum_i\)表示从s走到i的任意一条路径的权值和。发现对于每个到i直接有边的节点j，\(sum_j+EdgeValue_{i,j}\)都相等(为了满足上面的条件)，令这个值为val。则\(val \le sum_i \le val+1\)。发现以上总结出的所有条件都是不等式的形式(a=b可以转化为\(a \ge b且a \le b\))，所以可以用差分约束。
由于题目要求的是字典序至少为S的答案，不妨先检查S是否合法。然后从后往前枚举答案最晚可以从哪一位开始与S不同。我们每次要干的事情相当于是：指定有向图中的一些点必须取0或者必须取1，其他的点随意，判断是否有解。只要把上面说的\(val \le sum_i \le val+1\)改一下就行了。
令\(N=2^{2w+1}\)。一共需要做\(O(N)\)次差分约束，每次复杂度为\(O(N^2)\)，总复杂度\(O(N^3)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nPROGRAM TERMINATED";
#endif
exit(0);
}
using namespace std;
int w,dist[140],cnt[140],inq[140];
string s,ans="";
vector <pii> rg[140],g[140];
queue <int> q;
int relax(int x,int vv,int y)
{
if(dist[x]>dist[y]+vv)
{
dist[x]=dist[y]+vv;
cnt[x]=cnt[y]+1;
if(cnt[x]>(1<<(w+w+1))+3) return -1;
return 1;
}
else return 0;
}
bool spfa()
{
rep(i,135) dist[i]=1e9,cnt[i]=inq[i]=0;
dist[0]=0;inq[0]=1;q.push(0);
while(!q.empty())
{
int f=q.front();q.pop();inq[f]=0;
rep(i,g[f].size())
{
int val=relax(g[f][i].fi,g[f][i].se,f);
if(val==-1) return false;
if(val==1&&inq[g[f][i].fi]==0) q.push(g[f][i].fi),inq[g[f][i].fi]=1;
}
}
return true;
}
bool check()
{
rep(i,135) g[i].clear();
rep(i,1<<(w+w+1))
{
for(int j=1;j<rg[i].size();++j)
{
int xa=rg[i][0].fi,xb=rg[i][j].fi,va=rg[i][0].se,vb=rg[i][j].se;
g[xa].pb(mpr(xb,vb-va));g[xb].pb(mpr(xa,va-vb));
}
if(rg[i].size())
{
int xx=rg[i][0].fi,vv=rg[i][0].se,ll=0,rr=1;
if(i<ans.size())
{
if(ans[i]=='0') rr=0;
else ll=1;
}
g[i].pb(mpr(xx,vv-ll));g[xx].pb(mpr(i,rr-vv));
}
}
return spfa();
}
int main()
{
fileio();
freopen("cell.in","r",stdin);
freopen("cell.out","w",stdout);
cin>>w>>s;
rep(i,1<<(w+w+1))
{
rep(j,2)
{
int to=(i>>1)|(j<<(w+w));
rg[to].pb(mpr(i,j));
}
}
ans=s;if(check()){cout<<ans<<endl;termin();}
for(int i=s.size()-1;i>=0;--i) if(s[i]=='0')
{
ans=s.substr(0,i);ans.pb('1');
if(check())
{
while(ans.size()<s.size())
{
ans.pb('0');
if(!check()) ans[ans.size()-1]='1';
}
cout<<ans<<endl;
termin();
}
}
puts("no");
termin();
}