题目描述
难度分:1400
输入n(1≤n≤2×105)和长为n的字符串数组 a,每个字符串的长度均在[1,5]内,且只包含数字字符1
~9
。
定义【好字符串】满足:偶数长度,且左半的数字之和等于右半的数字之和。
输出有多少对(i,j)满足a[i]+a[j]是好字符串。
注意i和j的大小没有限制,i<j,i=j,i>j都可以。
输入样例1
10
5 93746 59 3746 593 746 5937 46 59374 6
输出样例1
20
输入样例2
5
2 22 222 2222 22222
输出样例2
13
输入样例3
3
1 1 1
输出样例3
9
算法
枚举
首先可以想到,由于好串的长度为偶数,所以必然是偶数长度的串相互组合,奇数长度的串相互组合,我们可以按长度分组计算答案,两个组的答案加起来就是最终答案。而每个数字字符串的长度很短,因此比较容易想到以它为突破口,但是在枚举的时候需要分为以下三种情况:
-
枚举好串的长度为2,4,6,8,10,对于每个长度len,枚举前一个数字nums[i],i∈[0,n),由于nums[i].size()>len2时我们可以确定好串前一半的数位和,更加方便推测后面那个串需要满足的条件,因此可以假设前一个串的长度是更大的。对于nums[i],计算出前len2的数位和s1,那么后一个数字的长度就应该是olen=len−nums[i].size(),它的数位和应该是s2=s1×2−digitSum(nums[i]),其中digitSum(x)表示x的数位和。知道有多少个nums[j]满足长度为olen,数位和为s2即可,这可以预处理出来,存储到一个哈希表counter中,counter[len][sum]表示长度为len,数位和为sum的数字串个数(累加到答案上即可)。而为了快速得到某个数字串nums[i]前x位的数位和,我们还可以预处理出一个前缀和数组s,s[i][j]表示nums[i]前j+1位的数位和,j从0开始取值。
-
同理可以计算出后一个数的长度>len2的情况,只不过s数组需要变成后缀和数组。
-
最后还需要考虑前后两个数字长度相等的情况(此时还可以自己和自己匹配),我们遍历哈希表counter,对于每个长度len,再遍历counter[len]的键值对(sum,cnt),把数位和相同的组合起来,即把cnt2累加到答案上。
复杂度分析
时间复杂度
遍历的长度为10以内的正偶数,可以看成常数O(L)。而对于每个长度,都需要遍历原始的字符串数组,时间复杂度为O(n)。预处理出counter和s需要遍历原始字符串数组中每个字符串的所有字符,时间复杂度为O(nL)。因此,整个算法的时间复杂度就是O(nL)。
空间复杂度
将字符串按照长度的奇偶分组需要额外O(n)的空间,二维前缀和数组s的空间为O(nL),哈希表counter在极限情况下,数位和可以达到90,数位长度为[1,10],相比s数组不值一提。因此,整个算法的额外空间复杂度为O(nL)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL get(vector<string>& nums) {
int n = nums.size();
vector<vector<int>> s(n, vector<int>());
vector<unordered_map<int, int>> counter(11, unordered_map<int, int>());
for(int i = 0; i < n; i++) {
int bl = nums[i].size();
s[i].resize(bl);
for(int j = 0; j < bl; j++) {
s[i][j] = (j? s[i][j - 1]: 0) + (nums[i][j] - '0');
}
int tot = s[i].back();
counter[bl][tot]++;
}
LL ans = 0;
for(int len = 1; len <= 5; len++) {
for(auto&[sum, cnt]: counter[len]) {
ans += 1LL*cnt*cnt;
}
}
// 枚举前一半
for(int len = 2; len <= 10; len += 2) {
int half = len>>1;
for(int i = 0; i < n; i++) {
int bl = nums[i].size();
if(bl > len) continue;
if(half < bl) {
int olen = len - bl; // 另一个数字的长度
int s1 = s[i][half - 1], s2 = s1*2 - s[i].back();
// 要找一个长度为olen,且数位和为s2的数字和i拼接
ans += counter[olen][s2];
}
}
}
for(int i = 1; i <= 10; i++) {
counter[i].clear();
}
for(int i = 0; i < n; i++) {
int bl = nums[i].size();
for(int j = bl - 1; j >= 0; j--) {
s[i][j] = (j + 1 < bl? s[i][j + 1]: 0) + (nums[i][j] - '0');
}
counter[bl][s[i][0]]++;
}
// 枚举后一半
for(int len = 2; len <= 10; len += 2) {
int half = len>>1;
for(int i = 0; i < n; i++) {
int bl = nums[i].size();
if(bl > len) continue;
if(half < bl) {
int olen = len - bl; // 另一个数字的长度
int s1 = s[i][bl - half], s2 = s1*2 - s[i][0];
// 要找一个长度为olen,且数位和为s2的数字和i拼接
ans += counter[olen][s2];
}
}
}
return ans;
}
int main() {
int n;
cin >> n;
vector<string> odd, even;
for(int i = 0; i < n; i++) {
string num;
cin >> num;
if(num.size()&1) {
odd.push_back(num);
}else {
even.push_back(num);
}
}
printf("%lld\n", get(odd) + get(even));
return 0;
}