Description

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

Input

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

Output

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

Sample Input

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

Sample Output

1 2

Data Constraint

对于20% 的数据满足n <= 100。
对于50% 的数据满足n <= 1 *10^3。
对于100% 的数据满足n <= 6 * 10^3。

Solution

注意到一定有解（共有 N+1 个）。
预处理出每个 64 进制数中转成 2 进制后的 1 的个数。
再随机化的处理任意两个串，判断是否符合条件即可。
注意 2n 位后的都没有用，要特殊判断一下。

Code

#include<cstdlib>
#include<iostream>
#include<ctime>
using namespace std;
const int N=2002;
int n,m,h,k;
int a[N*3][N],f[64],p[7];
inline bool pd(int x,int y)
{
int sum=0;
for(int i=1;i<m;i++)
    {
        sum+=f[a[x][i]&a[y][i]];
if(sum>=h) return true;
    }
int s=f[a[x][m]&a[y][m]];
for(int i=1;i<=6-k;i++)
if(s&p[6-i]) sum++;
return sum>=h;
}
inline void dfs(int x,int y,int z)
{
if(x==6)
    {
        f[z]=y;
return;
    }
    dfs(x+1,y+1,z+p[x]);
    dfs(x+1,y,z);
}
inline bool check()
{
int x=rand()%(n+1)+1,y=rand()%(n+1)+1;
while(x==y) y=rand()%(n+1)+1;
if(!pd(x,y)) return false;
printf("%d %d",x,y);
return true;
}
int main()
{
scanf("%d",&n);
    m=(n*2-1)/6+1,h=n>>1,k=m*6-n*2;
for(int i=p[0]=1;i<6;i++) p[i]=p[i-1]<<1;
for(int i=1;i<=n+1;i++)
    {
char ch=getchar();
while(ch<33 || ch>96) ch=getchar();
for(int j=1;j<=m;j++) a[i][j]=ch-33,ch=getchar();
    }
    dfs(0,0,0);
//srand(time(NULL));
for(int i=1;i<=n*2;i++)
if(check()) return 0;
/*for(int i=1;i<=n;i++)
 for(int j=i+1;j<=n+1;j++)
 if(pd(i,j))
 {
 printf("%d %d",i,j);
 return 0;
 }*/
printf("NO Solution");
return 0;
}

秒客网

JZOJ 5399. 【NOIP2017提高A组模拟10.7】Confess