首页 技术 正文
技术 2022年11月23日
0 收藏 435 点赞 2,603 浏览 1240 个字

题目链接:

http://codeforces.com/contest/1257/problem/F

题意:

给出$n$个30位整数

找到一个数,让它与这$n$个数分别异或,得到的$n$个数二进制1的个数相同

数据范围:

$1\leq n \leq 100$

分析:

CF官方题解称这是中间相遇技巧

枚举答案的低15位,这时有$2^{15}$种情况

与给出的$n$个数的低15位去异或,得到1的数量定义为$low[i]$

把$(low[2]-low[1],low[3]-low[1],…..low[n]-low[1])$这个vector放入set

再枚举答案的高15位,得到$high[i]$数组

在set中寻找$(high[1]-high[2],high[1]-high[3],…..high[1]-high[1])$

AC代码:

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
using namespace std;
const int maxn=100+7;
const int maxm=(1<<15)+7;
struct Node{
int ans;
vector<int>ve;
bool operator<(const Node &a)const{
return ve<a.ve;
}
}node;
set<Node>se;
int l[maxn],h[maxn];
int getlen[maxm],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
l[i]=(x&((1<<15)-1));
h[i]=x>>15;
}
for(int i=0;i<maxm;i++){
int v=i;
while(v){
if(v&1)getlen[i]++;
v/=2;
}
}
int len=(1<<15);
for(int i=0;i<len;i++){
node.ans=i;
node.ve.clear();
int v=getlen[i^l[1]];
for(int j=2;j<=n;j++)
node.ve.push_back(v-getlen[i^l[j]]);
se.insert(node);
}
for(int i=0;i<len;i++){
node.ans=i;
node.ve.clear();
int v=getlen[i^h[1]];
for(int j=2;j<=n;j++)
node.ve.push_back(getlen[i^h[j]]-v);
if(se.find(node)!=se.end()){
Node now=*se.find(node);
printf("%d\n",(i<<15)+now.ans);
//if((i<<15)+now.ans==1073709057)return 0;
return 0;
}
}
printf("-1\n");
return 0;
}

  

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,948
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,824
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:5,651
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,517
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,718
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,188