[CSP-S模拟测试]:Walk（BFS+建边）

题目描述

　　在比特镇一共有$n$个街区，编号依次为$1$到$n$，它们之间通过若干条单向道路连接。
　　比特镇的交通系统极具特色，除了$m$条单向道路之外，每个街区还有一个编码${val}_i$，不同街区可能拥有相同的编码。如果${val}_i\ and\ {val}_j={val}_j$，即$val_i$在二进制下与${val}_j$做与运算等于${val}_j$，那么也会存在一条额外的从$i$出发到$j$的单向道路。
　　$Byteasar$现在位于$1$号街区，他想知道通过这些道路到达每一个街区最少需要多少时间。因为比特镇的交通十分发达，你可以认为通过每条道路都只需要$1$单位时间。

输入格式

第一行包含两个正整数$n,m$，表示街区的总数以及道路的总数。
第二行包含$n$个正整数${val}_1,{val}_2,...,{val}_n$，分别表示每个街区的编码。
接下来$m$行，每行包含两个正整数$u_i,v_i$，表示一条单向道路，起点为$u_i$，终点为$v_i$。

输出格式

输出$n$行，每行一个整数，其中第$i$行输出到达第$i$个街区的最少时间，如果无法到达则输出$−1$。

样例

样例输入：

5 2
5 4 2 3 7
1 4
2 3

样例输出：

0
1
2
1
-1

数据范围与提示

对于$100\%$的数据，$1\leqslant u_i,v_i\leqslant n,1\leqslant {val}_i<2^{20}$。

题解

$\Theta(n^2)$的暴力建边最短路就不说了。

显然我们不能把所有的边都建上，这样就$T$飞了，所以我们考虑优化建边的过程。

考虑建边的性质，我们可以枚举子集，建边，然后$BFS$，这样我们就优化到了$\Theta(3^{15}+n+m)$。

接着进行优化，我们可以按位枚举，假设第$i$位是$1$，那么我们可以只向把第$i$位的$1$换成$0$连边即可。

时间复杂度：$\Theta(20\times 2^{20}+n+m)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n;

char ch[200001];

int b[200001],que[200001],nxt[200001],p;

unsigned long long a[200001],mod[200001];

void pre_work()

{

	memset(nxt,0,sizeof(nxt));

	memset(b,0,sizeof(b));

	p=que[0]=0;

}

void KMP(int l,int r)

{

	for(int i=l+1;i<=r;i++)

	{

		while(p&&b[i]!=b[p+1])p=nxt[p];

		if(b[i]==b[p+1])p++;

		nxt[i]=p;

	}

}

int main()

{

	int T;scanf("%d",&T);

	mod[1]=1;

	for(int i=2;i<=200000;i++)mod[i]=mod[i-1]*131;

	while(T--)

	{

		scanf("%s",ch+1);

		pre_work();

		n=strlen(ch+1);

		a[1]=ch[1]-'A'+1;

		for(int i=2;i<=n;i++)

			a[i]=a[i-1]*131+ch[i]-'A'+1;

		for(int i=0;i<=n;i++)

			if(a[i+1]==a[n]-a[n-i-1]*mod[i+2])que[++que[0]]=i+1;

		if(que[1]>1)b[que[1]]=1;

		KMP(1,que[1]);

		for(int i=2;i<=que[0];i++)

		{

			if(que[i]<=que[i-1]<<1)

			{

				for(int j=que[i-1]+1;j<=que[i];j++)

					b[j]=b[j+que[i-1]-que[i]];

				KMP(que[i-1],que[i]);

			}

			else

			{

				KMP(que[i-1],que[i]-que[i-1]-1);

				int now=p,zero=1,len=que[i]-que[i-1];

				while(now)

				{

					if(!b[now+1]&&!(len%(len-now-1))){b[len]=1;break;}

					now=nxt[now];

				}

				if(!b[now+1]&&!(len%(len-now-1)))b[len]=1;

				KMP(len-1,len);

				nxt[len]=p;

				len=que[i]-que[i-1];

				for(int j=1;j<=que[i-1];j++)b[len+j]=b[j];

				KMP(len,len+que[i-1]);

			}

		}

		for(int i=1;i<=n;i++)printf("%d",b[i]);

		puts("");

	}

	return 0;

}

rp++

巴特西