Confess_confess词根词缀「建议收藏」

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-7NU5”C[$
3N.#
Sample Output

1 2
Data Constraint

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

题解：

数据范围比较小，直接Bitset暴力匹配即可。关键是读懂题，题目的意思是单个字符为一个数，我一开始理解为了整个字符串为一个64进制数。那么只需要先预处理出单个字符的二进制，拼在一起，取前2n个，用Bitset维护集合，然后保存下二进制数中的1的个数。后面匹配的时候可以用i串和j串的1个数和减去异或值，或者直接去&好像也是可以的。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<bitset>
#define MAXA 1005
using namespace std;
typedef long long LL;
int n,f[100005],Temp,Bit[MAXA] = {1,2,4,8,16,32};
char s[100005];
bitset<12050> Bin[6005],Tempb;
void Change(char *str,int Idx) {
	int cnt = 0;
	Temp = n << 1;
	for(int i=0;i<strlen(str);i++) {
		int b = str[i] - 33;
		for(int j=5;j>=0;j--) {
			cnt++;
			if(b & Bit[j])
			   Bin[Idx].set(cnt);
			if(cnt == Temp) break;
		}
		if(cnt == Temp) break;
	}
	f[Idx] = Bin[Idx].count();
	//cout << Idx << " " << f[Idx] << endl;
}
int main() {
//	freopen("confess.in","r",stdin);
//    freopen("confess.out","w",stdout);
	scanf("%d\n",&n);
	for(int i=1;i<=n+1;i++) {
		scanf("%s",&s);
		Change(s,i);
	}
	for(int i=1;i<=n-1;i++)
	    for(int j=i+1;j<=n;j++) {
	    	Tempb = Bin[i] xor Bin[j];
	    	int x = Tempb.count();
	    	if(f[i] + f[j] - x >= n) {
	    		printf("%d %d",i,j);
	    		return 0;
			}
		}
	    
}
/*
10
EVK#
IH=#
676"
R7,#
74S"
6V2#
O3J#
S-7N
U5"C
[$JU
3N.#
*/

今天的文章Confess_confess词根词缀「建议收藏」分享到此就结束了，感谢您的阅读。