首页 > 代码库 > JZOJ5258.【NOIP2017模拟8.11】友好数对
JZOJ5258.【NOIP2017模拟8.11】友好数对
显然有个O(n2)的暴力枚举，不过会超时。（但也有六十分呐）
时间主要花在了一个一个判断，我们设想能否一次性判断很多个。
两个数异或后有二进制中有两个一，就是说两个数二进制下有两位是不同的，即有ai xor 2k xor bj xor 2l=0(k!=l)；
那么我们可以考虑枚举ai xor 2k，丢到hash表里，然后再枚举每个bj xor 2l，在hash里找是否有相等的。
为避免重复（ai xor 2k bj xor 2l 与 ai xor 2l bj xor 2k是相等的），我们可以令k<l。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cmath> 7 #define mo 9999999 8 #define N 100005 9 int n,hash[mo],m,a[N],b[N],g[mo],qwq[31];10 long long ans; 11 void init(int x){12 int a=x%mo;13 while ((hash[a]!=0)&&(hash[a]!=x)) a=(a+1)%mo;14 hash[a]=x;15 g[a]++;16 }17 int get(int x){18 int a=x%mo;19 while ((hash[a]!=0)&&(hash[a]!=x)) a=(a+1)%mo;20 return g[a];21 }22 int main(){23 scanf("%d%d",&n,&m);24 for (int i=1;i<=n;i++)25 scanf("%d",&a[i]);26 for (int j=1;j<=m;j++)27 scanf("%d",&b[j]);28 qwq[0]=1;29 for (int i=1;i<=30;i++)30 qwq[i]=2*qwq[i-1];31 for (int i=1;i<=n;i++)32 init(a[i]^qwq[0]);33 ans=0;34 for (int i=1;i<30;i++){35 for (int j=1;j<=m;j++)36 ans+=get(b[j]^qwq[i]);37 for (int j=1;j<=n;j++)38 init(a[j]^qwq[i]);39 }40 printf("%lld\n",ans);41 }
JZOJ5258.【NOIP2017模拟8.11】友好数对
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。