赞
踩
XOR在玩密室逃脱,在某一关中,桌上有一个一张纸,上面写着“请根据所给例子求解答案从而获得密码”,下面写了几个字符串“01 10 11”,而答案为“6”,聪明的XOR立马就知道了这是给出一些二进制数字S,求存在多少对有序二元组(i,j)使得S[i]^S[j]<S[i],现在还有T组数据,每组是n个长度为m的二进制数字,聪明的XOR立马开始动手求解答案。
第一行一个整数T,表示数据组数。
对于每组数据,首先读入两个整数n,m(n*m<=1000000),接下来为n行,每行为一个长度为m的01串,表示一个二进制数字
对于每个数据,输出一个整数x,表示二元组数目
6
思路:只用考虑每个数最高位的 1 的位置,该位置最高位 1 相同的个数 a,贡献为 a * a,然后加上该位置为1但最高位 1 不是该位置的个数 (b-a),a * (b - a)(因为当x和最高位比自己大的数异或时,x只能放后面), a*a+a*(b-a)
- #include <bits/stdc++.h>
- #define N 1000010
- using namespace std;
- long long int a[N],b[N],mark[N]; //a[i]是第i列为1且该为是最高位字符串的个数
- char s[N]; //b[i]是第i列为1的字符串个数
- int main() //mark[i] 是第i个字符串最高位 为1所在的位置
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int n,m,p;
- scanf("%d %d",&n,&m);
- fill(a,a+N,0);
- fill(b,b+N,0);
- fill(mark,mark+N,0);
- for(int i=0;i<n;i++)
- {
- scanf("%s",s);
- p=0;
- for(int j=0,t=1;j<m;j++,t++)
- {
- if(s[j]=='1')
- {
- b[t]++;
- if(p==0) //找到第i个字符串最高位1所在的位置
- {
- mark[i]=t;
- p=1;
- }
- }
- }
- }
- for(int i=0;i<n;i++)
- {
- a[mark[i]]++;
- }
- long long int ans=0;
- for(int i=1;i<=m;i++)
- {
- ans=ans+a[i]*b[i];
- }
- printf("%lld\n",ans);
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。