zzuli 2133: 密室逃脱(2017轻工业校赛 )

2133: 密室逃脱

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 352  

Solved: 69

​​Submit​​

​​Status​​

​​Web Board​​

Description

XOR在玩密室逃脱，在某一关中，桌上有一个一张纸，上面写着“请根据所给例子求解答案从而获得密码”，下面写了几个字符串“01 10 11”，而答案为“6”，聪明的XOR立马就知道了这是给出一些二进制数字S，求存在多少对有序二元组（i,j）使得S[i]^S[j]<S[i]，现在还有T组数据，每组是n个长度为m的二进制数字，聪明的XOR立马开始动手求解答案。

Input

第一行一个整数T，表示数据组数。

对于每组数据，首先读入两个整数n,m（n*m<=1000000），接下来为n行，每行为一个长度为m的01串，表示一个二进制数字

Output

对于每个数据，输出一个整数x，表示二元组数目

Sample Input

1
 
3  
 2
 
01
 
10
 
11      

Sample Output

6      

看了题解才做出来  笨方法果然只能超时。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define N 1000000+5
char str[N];
int dp[N];//统计第i位为1的串的个数 
int sum[N];//统计第一个1出现在i位的个数 
int firstOne[N];//统计第i个串第一个1的位置 
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
    int n,m;
    bool first;
    memset(dp,0,sizeof(dp));
    memset(sum,0,sizeof(sum));
    memset(firstOne,-1,sizeof(firstOne));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
      scanf("%s",str);
      for(int j=0;j<m;j++)
      {
        if(str[j]=='0') continue;
        dp[j]++;
        if(firstOne[i]==-1)
        firstOne[i]=j;
      }
    }
    for(int i=1;i<=n;i++)
    {
      if(firstOne[i]!=-1)
      sum[firstOne[i]]++;
    }
    long long ans=0;
    for(int i=0;i<m;i++)
    {
      ans+=(long long)sum[i]*dp[i];
    }
    printf("%lld\n",ans);
  }  
  return 0;
}