题目链接

戳我

\(Solution\)

将好友访问你的主页的状态用二进制存下来

其中若第\(i\)位是\(1\),则表示这个好友在第\(i\)个\(1\)操作后访问了你的主页,否则没访问。

所以如果两位好友都高兴则两位好友的二进制数\(\&\)的值为\(0\)

所以这样就变成了一个最大独立集的问题了

如果\(\&\)不为\(0\)这两个好友不能在一个集合.

看数据范围，我们考虑折半

我们先分成两半，一半的最大独立集合保留.另一半用高维前缀和(实际上时高维\(max\))

枚举没有处理的独立集

答案是独立集个数+可以使得这个独立集满足的另一半的高位前缀和.取个\(max\)这里如果不懂可以看代码

我的代码复杂度可能有点不对，因为我是直接搜的,太懒了,实在不想建图

\(Code\)

#include<bits/stdc++.h>

#define rg register

#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

using namespace std;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();

    return f*x;

}

bitset<1000001> vis[44];

string s;

map<string,int> Map;

int f[44][44],bj[44];

int Ans[20048576][3],c[55],n,m,tot,js;

void dfs(int x,int begin,int end,int ans,int flag){

	if(x==end+1){

		int p=0;

		for(int i=begin;i<=end;i++){

			if(c[i]==1) p++; else continue;

			for(int j=begin+1;j<=end;j++)

				if(c[i]==1&&c[j]==1&&f[i][j])

					return ;

		}

		Ans[ans][flag]=p;return;

	}

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

		c[x]=i,dfs(x+1,begin,end,(ans<<1)|i,flag);

}

int main(){

	m=read(),n=read();

	for(int i=1;i<=m;i++){

		int opt=read();

		if(opt==1) { tot++;continue;}

		cin>>s;

		int p=Map[s];

		if(!p) p=Map[s]=++js;

		vis[p][tot]=1;

	}

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

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

			if(i!=j&&((vis[i]&vis[j])!=0))

				f[i][j]=1;

	int mid=n>>1,len=1<<(n/2+1),maxx=0;

	dfs(1,1,mid,0,0);

	dfs(mid+1,mid+1,n,0,1);

	for(int i=1;i<len;i<<=1)

		for(int j=0;j<len;j++)

			if(i&j)

				Ans[j][1]=max(Ans[j][1],Ans[i^j][1]);

	for(int i=0;i<len;i++){

		int x=i,pp=mid;

		memset(bj,0,sizeof(bj));

		while(x){

			int now=x&1;

			if(now==1)

				for(int j=mid+1;j<=n;j++)

					if(f[pp][j])

						bj[j]=1;

			x>>=1,pp--;

		}

		int y=0;

		for(int j=mid+1;j<=n;j++)

			y=((y<<1)|(bj[j]^1));

		maxx=max(maxx,Ans[i][0]+Ans[y][1]);

	}

	cout<<maxx;

    return 0;

}