当前位置: 首页 > 工具软件 > Reachability > 使用案例 >

Codeforces Round #562 (Div. 2) E. And Reachability(dp)

周承天
2023-12-01

题目

n(n<=3e5)个整数,第i个数为ai(0<=ai<=3e5),1<=i<=n

如果(ai&aj)>0,则称i到j是可达的,i<j

q(q<=3e5)个询问,每次询问两个下标x和y(x<y),

问在允许中间插入若干个下标位于[x+1,y-1]之间且插入序列单增的ai跳板的情况下,x到y是否可达

例如,ax ai aj ay是插入跳板之后的序列,

那么x到y可达当且仅当x到i可达,i到j可达,j到y可达,且下标满足x<i<j<y

思路来源

Codeforces Round #562 — Editorial

题解

last[i][k]记录大于i的最小下标j,满足aj在二进制表示下第k位为1

go[i][k]记录大于等于i的最小下标j,满足aj在二进制表示下第k位为1,且从i可达

倒着dp,可以把last数组求出来,如果last[i-1][k]能被ai的对应位更新就更新,否则last[i-1][k]沿用last[i][k]

①如果ai在第k位为1,go[i][k]=i显然成立

②ai自己没有第k位,却要去一个有第k位的最小的位置,

那么它只能,先以自己有的二进制位k为跳板,去到last[i][k]对应的下标j,

再去利用go[j][k],寄希望于aj有第k位,或再重复该跳板过程,到达一个有第k位的最小的位置,

多条j的路径都可以更新go[i][k]的值,于其中取小即为go[i][k]

查询问x是否可达y时,只需检查y的所有二进制为1的位k,

若存在k使得go[x][k]<=y,即说明x->go[x][k]->y,可达;

所有都不符合,则不可达

心得

开始WA了一发,注意初始化

感觉自己思维题还是练的不够吧

但所幸现在能照着turorial大致敲出来,码力还凑活

相信随着积累应该是可以渐渐培养思维的

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
const int lg=20;
int go[maxn][lg],last[maxn][lg];
int n,q,a[maxn];
int b[lg],cnt;
int x,y;
bool ok()
{
	for(int k=19;k>=0;--k)
	{
		if(!(a[y]>>k&1))continue;
		if(go[x][k]<=y)return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i)
	scanf("%d",&a[i]);
	for(int i=n+1;i>=1;--i)//go[last[i][b[j]]][k]会用到go[n+1][k] 
	{
		for(int k=19;k>=0;--k)
	    go[i][k]=last[i][k]=n+1;
	}
	for(int i=n;i>=1;--i)
	{
		for(int k=19;k>=0;--k)
		{
			if(a[i]>>k&1)last[i-1][k]=i;//对于上一个位置来说,最小一定是本位置 
			else last[i-1][k]=last[i][k];
			//printf("last[%d][%d]:%d\n",i-1,k,last[i-1][k]);
	    }
	}
	for(int i=n;i>=1;--i)
	{
		cnt=0;
		for(int k=19;k>=0;--k)
		{
			if(a[i]>>k&1)
		 	{
			  go[i][k]=i;
		 	  b[cnt++]=k;
	   		}
		} 
	    for(int k=19;k>=0;--k)
	    {
	    	if(a[i]>>k&1)continue;
	    	for(int j=0;j<cnt;++j)
	    	go[i][k]=min(go[i][k],go[last[i][b[j]]][k]);
	    }
	} 
	while(q--)
	{
		scanf("%d%d",&x,&y);
		puts(ok()?"Shi":"Fou");
	}
	return 0;
} 

 

 类似资料: