zzuli 2133: 密室逃脱(2017轻工业校赛 )_密室逃脱刚出站就被一个小孩塞到手里一张纸条

2133: 密室逃脱

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 352   Solved: 69

Submit Status Web Board

Description

Input

Output

Sample Input

Sample Output

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

#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;
}