[JZOJ5399]:Confess（随机化）

题目描述

　　小$w$隐藏的心绪已经难以再隐藏下去了。
　　小$w$有$n+1$（保证$n$为偶数）个心绪，每个都包含了$[1,2n]$的一个大小为$n$的子集。
　　现在他要找到隐藏的任意两个心绪，使得他们的交大于等于$\frac{n}{2}$。

输入格式

　　一行一个整数$n$。
　　接下来每行一个长度为$k$的字符串，该字符串是一个$64$进制表示，$ASCII$码为$x$的字符代表着$x-33$，所有字符在$33$到$33+63$之间。
　　转为二进制表示有$6k$位，它的前$2n$个字符就是读入的集合，第$i$位为$1$表示这个集合包含$i$，为$0$表示不包含。

输出格式

　　一行两个不同的整数表示两个集合的编号。
　　如果无解输出$"NO\ Solution"$。

样例

样例输入：

10
EVK#
IH=#
676"
R7,#
74S"
6V2#
O3J#
S-7$
NU5"
C[$$
3N.#

样例输出：

1 2

数据范围与提示

　　对于$20\%$的数据满足$n\leqslant 100$。
　　对于$50\%$的数据满足$n\leqslant 1\times 10^3$。
　　对于$100\%$的数据满足$n\leqslant 6\times 10^3$。

题解

随机化竟然是正解，还好我机灵了一下。

官方题解我也是醉了……

用$bitset$优化一下就好啦。

两个集合的交的期望大小为：

$$\min(\sum\limits_{i=1}^{2n}\frac{C_{c_i}^2}{C_{n+1}^2}|\sum\limits_{i=1}^{2n}c_i=n(n+1))=\frac{n-1}{2}$$

至少需要$n$对就好了。

时间复杂度：$\Theta(\frac{n^2}{\omega})$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n;

int bin[9];

char ch[10000];

bitset<12000> bit[6010];

int main()

{

	scanf("%d",&n);

	for(int i=0;i<6;i++)bin[i+1]=1<<i;

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

	{

		scanf("%s",ch+1);

		int len=strlen(ch+1);

		int top=0;

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

		{

			int x=ch[j]-33;

			if(++top>2*n)break;

			if(x&bin[6])bit[i][top]=1;

			if(++top>2*n)break;

			if(x&bin[5])bit[i][top]=1;

			if(++top>2*n)break;

			if(x&bin[4])bit[i][top]=1;

			if(++top>2*n)break;

			if(x&bin[3])bit[i][top]=1;

			if(++top>2*n)break;

			if(x&bin[2])bit[i][top]=1;

			if(++top>2*n)break;

			if(x&bin[1])bit[i][top]=1;

		}

	}

	while(1)

	{

		int x=rand()%(n+1)+1;

		int y=rand()%(n+1)+1;

		if(x==y)continue;

		if((bit[x]&bit[y]).count()>=(n>>1))

		{printf("%d %d\n",x,y);return 0;}

	}

	return 0;

}

rp++

巴特西