CF1895C

题目描述

给出 $n$ 个长度最多为 $5$ 的由 $\text{1}$ 到 $\text{9}$ 构成的字符串 $s$。

求出有多少个 $(i,j)$ 满足 $s_i+s_j$ 所形成的字符串长度为偶数，并且前半部分的数字之和等于后半部分的数字之和。

P.S：这里的加号表示字符串拼接。

分析

我们可以维护 $nb{r}_{i,j}$ 表示长度为 $i$，数字和为 $j$ 的个数，并记录下来。

枚举时，先枚举幸运串长度，在枚举其中一个字符串（注意要从长度除以 $2$ 开始）在枚举数字和，算出另一个字符串，统计答案，注意还要反着跑一边因为反着拼也是可以的。

答案初始值设为 $n$ 因为每个字符串可以跟自己拼。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2 * 1e5 + 5;
int n, a[N];
vector <int> nbr[10][55];

signed main(){
   
	cin >> n;
	for(int i = 1; i <= n; i ++){
   
		cin >> a[i];
		int len = 0, sum = 0, tmp = a[i];
		while(tmp){
   
			len ++;
			sum += tmp % 10;
			tmp /= 10;
		}
		nbr[len][sum].push_back(a[i]);
	}
	int ans = n;
	for(int len = 2; len <= 10; len += 2){
   
		for(int i = len / 2; i < len; i ++){
   
			int need = len - i;
			for(int sum = 0; sum <= 45; sum ++){
   
				for(int v : nbr[i][sum]){
   
					int sum1 = 0, sum2 = 0, tmp = v, now = 0;
					while(now < len / 2){
   
						sum1 += tmp % 10, now ++, tmp /= 10;
					}
					while(tmp){
   
						sum2 += tmp % 10, tmp /= 10;
					}
					ans += nbr[need][sum1 - sum2].size();
					if(i == len / 2){
   //因为自己跟自己拼已经算过了，所以要减一
						ans --;
						continue;//后面的反着跑一遍就不用做了
					}
					sum1 = sum2 = now = 0, tmp = v;
					while(now < i - len / 2){
   
						sum2 += tmp % 10, now ++, tmp /= 10;
					}
					while(tmp){
   
						sum1 += tmp % 10, tmp /= 10;
					}
					ans += nbr[need][sum1 - sum2].size();
				}
			}
		}
	}
	cout << ans;
	return 0;
}