关于本题
查看原帖
关于本题
488775
Cuiyi_SAI楼主2024/1/18 14:59

GDKOI 普及 T4 是luogu的 原题,数据范围扩大到 10610^6 只放哈希做法过,但是依据题面线段树分治也应该能拿到60分的档。

但是在我们学校OJ上(应该是用了GDKOI的官方数据),我在luogu AC 了的线段树分治只能拿到35分(WA了),同样的题解里 Calculatelove\color{grey}{Calculatelove} 的代码同样是35分(WA了),SSerxhs\color{red}{SSerxhs} 的代码只有10分(WA了)。而 gyh20\color{red}{gyh20} 大佬的哈希做法则得到了 55分,并实测开大数组之后可以通过 GDKOI 的数据。 同样能过的还有学校OJ上的参考代码:

#include<bits/stdc++.h>
#define YE puts("ymqOAO")
#define NO puts("Bob")
#define fo(i,a,b) for(int i=a;i<=b;i++) 
#define gc getchar()
char ch,fr[1<<21],*p1,*p2;
void rd(int&x)
{
	while(!isdigit(ch=gc));x=ch-48;
	while( isdigit(ch=gc)) x=ch-48+x*10; 
}
typedef unsigned long long ull;
const int N=1e6+10;
int n,m,u,v,to[N<<1],ne[N<<1],la[N],d1,k,c[5],s;
bool vs[N],l1[N];
ull a[N],e[N];
ull R() {ull x=ull(rand()+1)*ull(rand()+2)*ull(rand()+3)*ull(rand()+5)*ull(rand()+7); return x?x:1;}
void dfs(int x,int fa)
{
	vs[x]=1;
	for(int i=la[x],y;y=to[i];a[x]^=e[i>>1],i=ne[i])
		if(!vs[y]) dfs(y,x), e[i>>1]=a[y]; else
		if(y^fa&&!e[i>>1]) e[i>>1]=R();
}
bool ck(int t,ull x,bool p)
{
	if(t>c[0]) return p&&!x;
	return ck(t+1,x,p)||ck(t+1,x^e[c[t]],1);
}
int main()
{
	freopen("cut.in","r",stdin); 
	freopen("cut.out","w",stdout);
	rd(n),rd(m);
	fo(i,1,m)
	{
		rd(u),rd(v);
		to[i*2  ]=v,ne[i*2  ]=la[u],la[u]=i*2  ;
		to[i*2+1]=u,ne[i*2+1]=la[v],la[v]=i*2+1;
		d1+=(l1[i]=u==1||v==1);
	}
	srand(19260817);
	dfs(1,0);
	rd(k);
	fo(i,1,k)
	{
		rd(c[0]); s=0;
		fo(j,1,c[0]) rd(c[j]), s+=l1[c[j]];
		if(s==d1) {NO; continue;}
		ck(1,0,0)?NO:YE;
	}
}

所以是说终究是luogu的题目太水,导致很多假的线段树分治过了吗?

附上学校OJ的 数据

2024/1/18 14:59
加载中...