5.20 省选模拟赛 T1 图启发式合并线段树合并染色计数问题

LINK：图

在说这道题之前吐槽一下今天的日子 520 = 1+1+4+514. /cy

这道题今天做的非常失败一点分都没拿到手关键是今天的T3 把我整个人给搞崩了。

先考虑如果得到了这么一张图怎么得到染色的方案数。

发现很难计算容斥？总方案-2个相同的+3个相同的我都觉得不太靠谱且复杂度过高。

考虑直接用乘法原理计数随便从一个点dfs 然后把相邻的点能选择的方案-1.

这样也是错误的如一个四个点的环(可能不满足题目中的条件类似的不过也是可以构造出来的。

第一个点贡献为n 第二个点贡献为n-1 第三个点贡献为n-1 第四个点贡献为n-2

容易发现端倪如果第三个点和第一个点颜色一样那么第四个点方案就可以为 n-1了。

所以这是不正确的。

进一步的我们发现关键是和某个点相邻的多个点可能没有边相连所以他们颜色可能相同。

结合题目条件一个编号比周围都小的点一定没有这个限制。

那么从大到小考虑染色就可以使相邻的点颜色不同了。

考虑50分的做法把图建出来暴力染色即可。

这里建图我直接枚举了两个点b c 寻找是否存在一个a 满足 a<b,a<c 且a和b 以及a和c有边相连。

bitset优化一下即可。

const int MAXN=1002;

int n,m;

bitset<MAXN>b[MAXN],s,cc;

int a[MAXN],vis[MAXN],ans=1;

inline int mul(int a,int b){return (ll)a*b%mod;}

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

inline int mus(int a,int b){return a-b<0?a-b+mod:a-b;}

inline int ksm(int b,int p)

{

	int cnt=1;

	while(p)

	{

		if(p&1)cnt=mul(cnt,b);

		b=mul(b,b);p=p>>1;

	}

	return cnt;

}

inline void dfs(int x)

{

	vis[x]=1;ans=mul(ans,a[x]);

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

	{

		if(!b[x][i])continue;

		if(!vis[i])--a[i];

	}

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

	{

		if(!b[x][i])continue;

		if(!vis[i])dfs(i);

	}

}

int main()

{

	freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

	get(n);get(m);

	rep(1,m,i)

	{

		int get(x),get(y);

		b[x][y]=b[y][x]=1;

	}

	s.reset();

	rep(2,n,i)

	{

		s[i-1]=1;

		rep(i+1,n,j)

		{

			if(b[i][j])continue;

			cc=b[i]&b[j]&s;

			if(cc.count())b[i][j]=b[j][i]=1;

		}

	}

	rep(1,n,i)a[i]=n;

	//rep(1,n,i){rep(1,n,j)cout<<b[i][j]<<' ';cout<<endl;}

	fep(n,1,i)

	{

		int cnt=0;

		rep(i+1,n,j)if(b[i][j])++cnt;

		ans=mul(ans,n-cnt);

	}

	put(ans);return 0;

}

考虑正解：

此时问题变成了求每个点和其相连的编号比其大的个数.

还是考虑题目中的a,b,c 和刚才的暴力一样需要从小到大做。

考虑最小的a 显然可以直接得到答案。

此时容易想到和a相连的那些点必然也相连。

在从小到大考虑到某个和a相连的点w的时候 w和a能连得集合是相同的。

把a的集合拿过来用即可得到和自己相连的点集。

可以发现这个关系具有传递性且每次只会传递到一个点上。

所以由于要支持查询最小值和数量所以可以利用set 进行启发式合并。nlog^2

当然也可以使用线段树合并来优化复杂度.nlog

值得注意的是需要去重所以无法使用可并堆/堆来做。这里给出线段树合并的code。

const int MAXN=1000010;

int n,m,id;

int a[MAXN],root[MAXN],ans=1;

inline int mul(int a,int b){return (ll)a*b%mod;}

inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}

inline int mus(int a,int b){return a-b<0?a-b+mod:a-b;}

inline int ksm(int b,int p)

{

	int cnt=1;

	while(p)

	{

		if(p&1)cnt=mul(cnt,b);

		b=mul(b,b);p=p>>1;

	}

	return cnt;

}

struct wy{int l,r;int sum;}t[MAXN*30];

inline void insert(int &p,int l,int r,int x)

{

	if(!p)p=++id;++sum(p);

	if(l==r)return;

	int mid=(l+r)>>1;

	if(x<=mid)insert(l(p),l,mid,x);

	else insert(r(p),mid+1,r,x);

}

inline int ask(int p,int l,int r)

{

	if(!sum(p))return 0;

	--sum(p);

	if(l==r)return l;

	int mid=(l+r)>>1;

	if(sum(l(p)))return ask(l(p),l,mid);

	return ask(r(p),mid+1,r);

}

inline int merge(int x,int y,int l,int r)

{

	if(!x||!y)return x|y;

	if(l==r)return x;

	int mid=(l+r)>>1;

	l(x)=merge(l(x),l(y),l,mid);

	r(x)=merge(r(x),r(y),mid+1,r);

	sum(x)=sum(l(x))+sum(r(x));

	return x;

}

int main()

{

	freopen("1.in","r",stdin);

    //freopen("a.out","w",stdout);

	get(n);get(m);

	rep(1,m,i)

	{

		int x,y;

		get(x);get(y);

		if(x>y)swap(x,y);

		insert(root[x],1,n,y);

	}

	rep(1,n,i)

	{

		ans=mul(ans,n-sum(root[i]));

		//cout<<sum(root[i])<<endl;

		int ww=ask(root[i],1,n);

		//cout<<sum(root[i])<<endl;

		if(ww)root[ww]=merge(root[ww],root[i],1,n);

	}

	put(ans);

	return 0;

}

巴特西

5.20 省选模拟赛 T1 图启发式合并线段树合并染色计数问题

最新文章

热门文章

巴特西

5.20 省选模拟赛 T1 图 启发式合并 线段树合并 染色计数问题

最新文章

热门文章

5.20 省选模拟赛 T1 图启发式合并线段树合并染色计数问题