Codeforces 1105

1105 E

题意

给你 (k) 段区间，每段中有 (a_i) 个朋友（可能有相同的），在每一段区间内你只能让一个朋友看你的资料，一个朋友开心的条件是每一次他要看你的资料时都能看到，问你最多能让几个朋友开心。
朋友数 (le 40)

Examples

input
5 3
1
2 motarack
2 mike
1
2 light
output
2
input
4 3
1
2 alice
2 bob
2 tanyaromanova
output
1

解

首先想到状态压缩。
然后，发现 (2^{40}) 根本不可能……
于是发明出一种玄学算法：
先开一个数组 (rnd) ，初始时 (rnd[i]=i) ，然后不停地random_shuffle构造 (1-m) 的排列，每次统计一遍答案（别忘加剪枝），等到快到2000ms时结束程序，输出答案。
需要#include<ctime>。

Code

#include<bits/stdc++.h>
#define maxn 100002
#define maxm 42
using namespace std;
template<typename tp>
void read(tp& x){
	x=0;
	char c=getchar();
	bool sgn=0;
	while((c<'0'||c>'9')&&c!='-')c=getchar();
	if(c=='-')sgn=1,c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	if(sgn)x=-x;
}
template<typename tp>
void write(tp x){
	if(x<0)putchar('-'),write(-x);
	else{
		if(x>=10)write(x/10);
		putchar(x%10+'0');
	}
}
int n,m,a[maxn][maxm],cntmp=-1,rnd[maxm];
long long b[maxm];
char s[43];
map<string,int> mp;
int main(){
	clock_t T=clock();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i][0]);
		if(a[i][0]==2){
			scanf("%s",s);
			if(!mp.count(s))mp[s]=++cntmp;
			a[i][1]=mp[s];
		}
	}
	for(int i=0;i<m;i++)b[i]=(1ll<<m)-1;
	for(int i=2,j;i<=n;i=j+2){
		for(j=i;j<=n&&a[j][0]==2;j++);j--;
		long long c=(1ll<<m)-1;
		for(int k=i;k<=j;k++){
			c&=(1ll<<m)-1-(1ll<<a[k][1]);
		}
		for(int k=i;k<=j;k++){
			b[a[k][1]]&=(c|(1ll<<a[k][1]));
		}
	}
	for(int i=0;i<m;i++)rnd[i]=i;
	int ans=0;
	const double d=CLOCKS_PER_SEC/1000;
	while((clock()-T)/d<1950){
		random_shuffle(rnd,rnd+m);
		long long res=(1ll<<m)-1;
		int cnt=0;
		for(int i=0;i<m&&res;i++){
			if(res&(1ll<<rnd[i])){
				res&=b[rnd[i]];
				cnt++;
			}
		}
		ans=max(ans,cnt);
	}
	printf("%d
",ans);
	return 0;
}