Confess_confess词根词缀「建议收藏」

Confess_confess词根词缀「建议收藏」Description小w隐藏的心绪已经难以再隐藏下去了

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词根词缀「建议收藏」分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/67543.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注