专栏文章

2025_6_19 T3

EEvan_Leo_Azir
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip1odz0
此快照首次捕获于
2025/12/03 04:42
3 个月前
此快照最后确认于
2025/12/03 04:42
3 个月前
查看原文
没想到吧，这是我不久前在NOIP模拟赛遇上的题目（但场上是 n≤45n\le 45 )，因为本人场切，所以题目难度应该不大
肉测是中位蓝的样子
首先，观察到 n≤35n\le 35，如果是 n≤20n\le 20 ，可以直接枚举出可能得团的情况，最后 O(n)O(n) check 即可，复杂度为 O(n×2n)O(n \times 2^n) ，而 n≤35n\le35自然启发我们“折半”
怎么折半？我们将前⌊n2⌋\lfloor \frac{n}{2} \rfloor 个点分为 AA 组，将剩下的分为 BB 组，先将 AA ，BB 组中的团找出来，最后把两组的团结合起来

对于A组

假设 fstf_{st} ，表示如果选的点为 stst {11 为选了，00 为不选}，能不能形成团 ，这个数组的处理很简单，直接 O(2n)O(2^n) 枚举集合就行

对于B组

假设 gstg_{st} ，我们考虑到，之后需要用 ff 数组和 gg 数组合并以得出最大团 ，如果现在我们有一个 fst1f_{st1} ，想取出一个 gst2g_{st2} 与之配对，所需的条件自然是 st1st1 中的每一个点与 st2st2 每一个点皆有连边，自然的，我们对每个 st1st1 预处理出一个 0101 串，指 st1st1 与哪些点有连边
对于 gstg_{st} 的定义也就显然了，对于状态 stst ，其 所有 为团的子集中,点最多的有多少个点，转移便是
gst=max⁡gst⊕2x(st中含有点x)g_{st}=\max{g_{st \oplus 2^x}} (st中含有点 x)
同样，如果 stst 本身就是一个团 ，便把 gstg_{st} 赋值为 stst 的二进制中 11 的个数
最后，处理出 fstf_{st} 中的点与 BB 组哪些点都有连边，合并即可
ans=max⁡(ans,cntst1+gst2)ans=\max (ans,cnt_{st1}+g_{st2})
cntst1cnt_{st1} 指 st1st1 二进制位数
设 w=⌈n2⌉w=\lceil \frac{n}{2}\rceil
时间复杂度 O(w×2w)O(w \times 2^w)
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxv=2e1+10,maxn=4e1+10;
int n,m,lim,ans;
int g[1<<23],fe[1<<22],pow_2[maxv],q1[maxn],q2[maxn];
bool f[1<<22];
int read()
{
	int ret=0,w=1;char ch=0;
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
	return ret*w;
}
void adde(int u,int v)
{
	if(v<=lim) q1[u]|=pow_2[v-1];
	else q2[u]|=pow_2[v-lim-1];
}//用01串表示点与 A,B 组的连边
void pre_all()
{
	pow_2[0]=1;
	for(int i=1;i<maxv;i++) pow_2[i]=pow_2[i-1]<<1;
}
void inpu() {n=read();m=read();}
void init()
{
	ans=0;
	memset(q1,0,sizeof(q1));memset(q2,0,sizeof(q2));
}
void pre()
{
	lim=n>>1;
	for(int i=1,u,v;i<=m;i++)
	{
		u=read(),v=read();
		adde(u,v);adde(v,u);
	}
	for(int i=1;i<=n;i++)
	{
		if(i<=lim) q1[i]|=pow_2[i-1];
		else q2[i]|=pow_2[i-lim-1];
	}
}
void DP1()
{
	for(int i=0;i<pow_2[lim];i++)
	{
		bool flag=0;fe[i]=pow_2[n-lim]-1;
		for(int j=1;j<=lim;j++) if(i&pow_2[j-1])
		{
			fe[i]&=q2[j];//预处理出状态 i 最多能和哪些点拼接
			if((i&q1[j])!=i) {flag=1;break;}
		}
		f[i]=!flag;
	}
}
void DP2()
{
	for(int i=0;i<pow_2[n-lim];i++)
	{
		int cnt=0;
		bool flag=0;
		for(int j=lim+1;j<=n;j++) if(i&pow_2[j-lim-1])
		{
			cnt++;
			if((i&q2[j])!=i) {flag=1;break;}
		}
		if(!flag) {g[i]=cnt;continue;}
		g[i]=0;
		for(int j=lim+1;j<=n;j++) if(i&pow_2[j-lim-1]) g[i]=max(g[i],g[i^pow_2[j-lim-1]]);
	}
}
void cal()
{
	for(int i=0;i<pow_2[lim];i++) if(f[i])
	{
		int cnt=0;
		for(int j=1;j<=lim;j++) if(i&pow_2[j-1]) cnt++;
		ans=max(ans,g[fe[i]]+cnt);
	}
}
void solve()
{
	inpu();
	if(n==1) printf("1\n");
	else
	{
		init();
		pre();
		DP1();
		DP2();
		cal();
		printf("%d\n",ans);
	}
}
int main()
{
	pre_all();
	int t=1;
	while(t--) solve();
	return 0;
}
是实际上，这里用到了一个名为 子集状压 的算法（也称 sosDP），它同样是重要的进阶技巧，但此处只是皮毛，感兴趣的话可以自学

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...