2025_6_19 T3

· · 题解

没想到吧，这是我不久前在NOIP模拟赛遇上的题目（但场上是 n\le 45 )，因为本人场切，所以题目难度应该不大

肉测是中位蓝的样子

首先，观察到 n\le 35，如果是 n\le 20 ，可以直接枚举出可能得团的情况，最后 O(n) check 即可，复杂度为 O(n \times 2^n) ，而 n\le35自然启发我们“折半”

怎么折半？我们将前\lfloor \frac{n}{2} \rfloor 个点分为 A 组，将剩下的分为 B 组，先将 A ，B 组中的团找出来，最后把两组的团结合起来

对于A组

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

对于B组

假设 g_{st} ，我们考虑到，之后需要用 f 数组和 g 数组合并以得出最大团 ，如果现在我们有一个 f_{st1} ，想取出一个 g_{st2} 与之配对，所需的条件自然是 st1 中的每一个点与 st2 每一个点皆有连边，自然的，我们对每个 st1 预处理出一个 01 串，指 st1 与哪些点有连边

对于 g_{st} 的定义也就显然了，对于状态 st ，其 所有 为团的子集中,点最多的有多少个点，转移便是

g_{st}=\max{g_{st \oplus 2^x}} (st中含有点 x)

同样，如果 st 本身就是一个团 ，便把 g_{st} 赋值为 st 的二进制中 1 的个数

最后，处理出 f_{st} 中的点与 B 组哪些点都有连边，合并即可

ans=\max (ans,cnt_{st1}+g_{st2}) 设 $w=\lceil \frac{n}{2}\rceil

时间复杂度 O(w \times 2^w)

#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），它同样是重要的进阶技巧，但此处只是皮毛，感兴趣的话可以自学