关于本题,提供一个卡常思路
查看原帖
关于本题,提供一个卡常思路
114530
隐隐约约妖艳楼主2021/2/24 20:51

我发现在枚举哪些边要割进行FF的时候,如果是视为第一个'1'为新加的边,就会T第87个点

for(int i=1;i<(1<<w);i++)
{
	if(i>=(1<<z))z++,y<<=1;
//就是像这样
	for(int j=2;j<=num;j++)
		l[i][j]=j<=20&&(1<<((j>>1)-1))==y&&(j&1)==0?25:l[i^y][j];
	ans[i]=ans[i^y];
	memset(vis,0,sizeof(vis));
	zzz=i;
	x=ddfs(1,0x3f3f3f3f);
	while(x)
	{
		ans[i]+=x;
		memset(vis,0,sizeof(vis));
		x=ddfs(1,0x3f3f3f3f);
	}
}

但如果是视为最后一个'1'为新加的边,就会T第89个点.

for(int i=1;i<(1<<w);i++)
{
	for(int j=2;j<=num;j++)
		l[i][j]=j<=20&&(1<<((j>>1)-1))==lowbit(i)&&(j&1)==0?25:l[i^lowbit(i)][j];
	ans[i]=ans[i^lowbit(i)];
//像这样.(lowbit就是树状数组的那个
	memset(vis,0,sizeof(vis));
	zzz=i;
	x=ddfs(1,0x3f3f3f3f);
	while(x)
	{
		ans[i]+=x;
		memset(vis,0,sizeof(vis));
		x=ddfs(1,0x3f3f3f3f);
	}
}

所以,把两种综合一下(就是加一个rand)就可以卡过去!

y=1;
z=1;
srand(time(0));
for(int i=1;i<(1<<w);i++)
{
	if(i>=(1<<z))z++,y<<=1;
	x=rand()&1?y:lowbit(i);
	for(int j=2;j<=num;j++)
		l[i][j]=j<=20&&(1<<((j>>1)-1))==x&&(j&1)==0?25:l[i^x][j];
	ans[i]=ans[i^x];
	memset(vis,0,sizeof(vis));
	zzz=i;
	x=ddfs(1,0x3f3f3f3f);
	while(x)
	{
		ans[i]+=x;
		memset(vis,0,sizeof(vis));
		x=ddfs(1,0x3f3f3f3f);
	}
}
2021/2/24 20:51
加载中...