admin管理员组

文章数量:1794759

【Aizu

题目大意

澄闪（doge，原为小澄）最近学习了离散数学，澄闪想到了这样一个问题。

澄闪有一个长度为无穷的 01 串，这个串中有一个位置下标为 0 0 0，从这个位置开始向两侧无限延伸。其中左侧的下标依次为 … . − 2 , − 1 ….-2,-1 ….−2,−1右侧下标依次为 1 , 2 , . . . 1,2,... 1,2,...。 01 串每个位置都为 0 0 0或者 1 1 1。

澄闪定义了对这种长度为无穷的 01 串的一种变换操作。在这种变换操作中，一个位置在变换后的值只与变换前与这个位置的距离不超过 w w w的位置有关。其中 w w w是一个固定的正整数。

这样的变换由一个长度为 2 2 w + 1 2^{2w+1} 22w+1的 01 串 p p p定义， p p p的下标为 0 , . . . , 2 2 w + 1 − 1 0,...,2^{2w+1}-1 0,...,22w+1−1，且 p p p的每个位置都为 0 0 0或 1 1 1。

具体来说，在一次变换中，对于位置 x x x，将变换前 01 串 [ x − w , x + w ] [x-w,x+w] [x−w,x+w]区间看成一个二进制数，设这个数为 a a a。则这个位置变换后的值为 p a p_a pa​。相当于如下操作：
S ′ [ x ] = p [ ∑ i = − w w 2 w − i S [ x + i ] ] S'[x]=p[\sum_{i=-w}^w2^{w-i}S[x+i]] S′[x]=p[i=−w∑w​2w−iS[x+i]]
澄闪认为一个 p p p是好的，当且仅当对于任意一个包含有限个 1 1 1的 01 串 S S S，设它包含 c t ct ct个 1 1 1，则对这个 01 串进行任意次变换后，得到的 01 串仍然只包含 c t ct ct个 1 1 1。

最后，澄闪给出了一个长度为 2 2 w + 1 2^{2w+1} 22w+1的 01 串 q q q， q q q的字符集只包含 0 , 1 0,1 0,1，澄闪想找到一个同样只由 0 , 1 0,1 0,1构成的字典序最小的 01 串 p p p，满足 p p p的字典序大于等于 q q q的字典序且 p p p是好的。

无解输出no。

样例输入

1
00011000

样例输出

00011101

样例解释

串00011100相当于，对于一个位置，如果变换前这个位置以及这个位置两侧拼接而成的串为011，100或101时，这个位置变换后为 1 1 1，否则这个位置变换后为 0 0 0。

但考虑串00111100，其中两侧各有无限延伸的 0 0 0。则它变换后为00100010，两侧仍然全为 0 0 0，这样 1 1 1的个数减少了，因而这个串不是好的。

考虑00011101，这相当于拼接而成的串为011，100，101或111时，这个位置变换后为 1 1 1。

对于上面的那个例子，它变换后为00111010，这是满足条件的。再比如说，对于串00110010111100，它变换后为00101001111010，同样满足条件。

可以证明，00011101是一个好的串，因此答案为00011101。

做题思路

首先，限制的任意次变幻可以看成一次变幻，因为对于任意字符集都要满足。

---

因为 S S S长度无限，有无限个长为 2 w + 1 2w+1 2w+1的字串是全 0 0 0的，所以一个好的串 p p p必定满足 p 0 = 0 p_0=0 p0​=0。

考虑知道 p p p和一个 S S S，如何判断是否符合要求。

显然 S S S没有 1 1 1时一定合法。

我们先把 S S S变幻后得到的 S ′ S' S′左移 w w w位，显然并不会改变正确性。

那么可以从 S S S最左边的 1 1 1开始往左 2 w + 1 2w+1 2w+1位，到最右边的 1 1 1的位置往右 2 w + 1 2w+1 2w+1位，取出真正对 1 1 1有贡献的子串 T T T，这里令 n = ∣ T ∣ n=|T| n=∣T∣。

如 w = 1 w=1 w=1， S S S为…10110111…，则 T T T为00010110111000。

从左往右把 T T T每个长度为 2 w + 1 2w+1 2w+1的子串依次转换为十进制数，得到一个长度为 n − 2 w n-2w n−2w的有序数组 a a a，发现 a a a开头和结尾都是 0 0 0。

上面的例子， a = [ 0 , 1 , 2 , 5 , 3 , 6 , 5 , 3 , 7 , 6 , 4 , 0 ] a=[0,1,2,5,3,6,5,3,7,6,4,0] a=[0,1,2,5,3,6,5,3,7,6,4,0]。

由于是按顺序取出来的子串，所以一定满足 a i = ( 2 a i − 1 + T i + 2 w ) & ( 2 2 w + 1 − 1 ) a_i=(2a_{i-1}+T_{i+2w})\&(2^{2w+1}-1) ai​=(2ai−1​+Ti+2w​)&(22w+1−1)，其中 & \& &为按位与。

根据定义，现在一个好的 p p p需要满足的条件就是 ∑ T i = ∑ p a i \sum{T_i}=\sum{p_{a_i}} ∑Ti​=∑pai​​。

因为我们取 T T T的方式保证了其前 2 w 2w 2w位为 0 0 0，就让 a i − 1 a_{i-1} ai−1​向 a i a_i ai​连一条权为 p a i − T i + 2 w p_{a_i}-T_{i+2w} pai​​−Ti+2w​的有向边（后称正边），此时边权和为 0 0 0。

依旧是上面的例子，当 p p p为00001111，我们会从 5 5 5向 3 3 3连一条权为 − 1 -1 −1的边，从 7 7 7向 6 6 6连一条权为 1 1 1的边。

我们可以取任意 S S S，也就是可以取任意满足左右各有 2 w + 1 2w+1 2w+1个 0 0 0的 T T T。

那就把所有 a i − 1 = u a_{i-1}=u ai−1​=u可能连向的 a i = v a_i=v ai​=v的边建出来，满足整个图所有从 0 0 0开始到 0 0 0结束的路径边权和为 0 0 0。

显然 0 0 0能到达任何点，所以就是整个图都是边权和为 0 0 0的环，即所有边加入反边后无负环。

现在可以判断一个确定的 p p p是否好了。

---

考虑如何判断一个 p p p的前缀是否好（假设我们知道 p p p的前 k k k位）。

对于一条 u u u连向 v v v的边，如果 v ≤ k v\leq k v≤k，直接按照上面的方式建边即可。

否则，可以借鉴差分约束的思想，让其正边取 p v = 1 p_v=1 pv​=1，反边取 p v = 0 p_v=0 pv​=0即让它尽可能合法。

这种做法有一个弊端，边权实际上是点权，可能两个以正边连向 v v v的点 u 1 u_1 u1​和 u 2 u_2 u2​对 p v p_v pv​的需求不同，一个想让其为 0 0 0，而另一个想让其为 1 1 1。

不难证明有且只有只有两个点以正边连向任意 v v v，并且这两个点二进制下有且只有最左边不同，删了它们也不会影响边，那删了就是。

即让 u u u向 v = ( 2 u + t ) & ( 2 2 w − 1 ) v=(2u+t)\&(2^{2w}-1) v=(2u+t)&(22w−1)连权为 p ( 2 u + t ) & ( 2 2 w + 1 − 1 ) − t p_{(2u+t)\&(2^{2w+1}-1)}-t p(2u+t)&(22w+1−1)​−t的边即可。

---

字典序最小从后往前枚举哪一位不同即可。

正解代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
const int inf=1e9+7;
struct xy{int x,y;
};
inline bool operator <(xy a,xy b){return a.x==b.x?a.y>b.y:a.x>b.x;}
int p[202020];
int q[202020];
int d[202020];
int v[202020];
int r[202020];
char a[202020];
vector<xy>e[202020];
priority_queue<xy>Q; 
inline int pd(int k){int s=(1<<(m*2))-1,x,y,z;f(i,0,s)e[i].clear();f(x,0,s)f(t,0,1){y=(z=(x<<1)|t)&s;if(z<=k){e[x].push_back((xy){y,p[z]-t});e[y].push_back((xy){x,t-p[z]});}else{e[x].push_back((xy){y,1-t});e[y].push_back((xy){x,t-0});}}f(i,0,s)d[i]=inf+(v[i]=r[i]=0);while(Q.size())Q.pop();Q.push((xy){d[0]=0,0});while(Q.size()){x=Q.top().y;Q.pop();v[x]=0;f(i,1,e[x].size())if(d[y=e[x][i-1].x]>(z=d[x]+e[x][i-1].y)){if(!v[y])Q.push((xy){z,y});d[y]=z;v[y]=1;}if(++r[x]>s || d[0]<0)return 1;}return 0;
}
signed main(){
//	freopen("cell.in","r",stdin);
//	freopen("cell.out","w",stdout);cin>>m;n=(1<<(2*m+1))-1;scanf("%s",a);f(i,0,n)p[i]=q[i]=a[i]^48;if(!pd(n)){l=n;}else{g(i,n,0)if(!q[i] && !pd(i*(p[i]=1))){f(t,i+1,n)p[t]=pd(t+(p[t]=0));break;}}if(pd(n))return printf("no\n"),0;f(i,0,n)putchar(p[i]^48);return putchar('\n'),0;
}

本文标签： Aizu