4 Torn Lucky Ticket

发布时间 2024-01-09 20:33:54作者: yufan1102

image
image
image
image

很容易能想到哈希,把每个字符串的数位拆开。然后遍历每个字符串匹配就行

当时我自己漏了一种情况,就是每一种的字符串其实是可以和三种情况的字符串匹配的,分别是比自己长的,短的,一样长的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int cnt[6][50];
int sum[N][50];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		int m=s.size();
		s=" "+s; 
		for(int j=1;j<=m;j++){
			sum[i][j]=sum[i][j-1]+s[j]-'0';
		}
		cnt[m][sum[i][m]]++;
		sum[i][0]=m;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int m=sum[i][0];
		int h=cnt[m][sum[i][m]];
		ans +=h;
		for(int j=1;j<m;j++){
			if(j*2<=m)continue;
			int x=sum[i][j];
			int y=sum[i][m]-x;
			ans += cnt[2 * j - m][2 * sum[i][j] - sum[i][m]];
            ans += cnt[2 * j - m][2 * (sum[i][m] - sum[i][m - j]) - sum[i][m]];
		}
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}