Dashboard - Educational Codeforces Round 157 (Rated for Div. 2) - Codeforces

C. Torn Lucky Ticket

题意

给出n个长度不大于5的字符串$s_1，s_2，…，s_n$（只由数字组成）， 你需要选择其中两个串$(i，j)$ （$i$ 和$j$可以相等，并且 $(i,j)$与 $(j,i)$视为两个不同的选择）, 令$s = s_i + s_j$。 问有多少种选择，使得：

  1. s的长度为偶数
  2. s的前一半的数字的总和等于后一半的数字总和

$1\le n \le 2*10^5$

思路

我们使用string类型的一维数组dat存储原始数据。 使用二维的vector数组vec（算上vector一共三维）存储处理后的数据。

$vec[i][j]$ 中存储的元素表示长度为 i的字符串， 他的后缀s[j,i-1] 的数字的总和 减去 前缀s[0,j-1]的数字总和。

我们对所有的vector类型进行排序。以便于我们使用lower_bound和upper_bound 来在logn的复杂度下查找其中某个数的数量。

之后我们遍历所有的字符串$s_i$, 把他作为前半部分，我们考虑如下方法来寻找合适后半部分：

假设后半部分字符串为$s_j $ ，前半部分的长度为$len_i$,后半部分为$len_j$。那么如果

  1. $len_i = len_j$ ，我们需要计算出$s_i$ 中的数字和$k$，然后在长度为$len_i $的串中找总和为k的数量。也就是

upper_bound(vec[leni][0].begin(),vec[leni][0].end(),k) - lower_bound(vec[leni][0].begin(),vec[leni][0].end(),k) `

  1. $len_i < len_j$ , 我们需要从后半部分的字符串中提取出一些前缀字符（最多两个），与前半部分拼接。因此要找的是

    upper_bound(vec[lenj][t].begin(),vec[lenj][t].end(),k) - lower_bound(vec[lenj][t].begin(),vec[lenj][t].end(),k) 其中$t = \frac{len_j - len_i}{2}$

  2. $len_i > len_j$ ，此时我们需要根据$lenj$的长度来计算前半部分的前缀减去后缀的值k，然后在$vec[lenj][0]$ 中搜索k的数目。比如此时$len_i = 5$ ，而$len_j = 3$ ,那么k = $s[0]+s[1]+s[2]+s[3]-s[4]$ 。而如果$len_i=5,len_j = 1$ ，那么$k = s[0]+s[1]+s[2]-s[3]-s[4]$ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
typedef pair<int,int> PII;
vector<int> vec[7][7];//vecpre[i][j] 长度为i的串的j前缀
// vector<int> vecend[7][7];
const int MAXN = 2e5+5;
string dat[MAXN];
int t;
int find(int len,int pre){
	return upper_bound(vec[len][pre].begin(),vec[len][pre].end(),t) -\
	lower_bound(vec[len][pre].begin(),vec[len][pre].end(),t);
}
void solve(){
	int n;
	cin>>n;
	string str;
	for(int i =1;i<=n;i++){
		cin>>str;
		dat[i] = str;
		int len = str.length();
		int sum = 0;
		for(int i = 0;i<len;i++){
			sum += str[i] - '0';
		}
		int t = 0;
		vec[len][0].push_back(sum);
		for(int i =0;i<str.length()/2;i++){
			t = t + str[i] - '0';
			vec[len][i+1].push_back(sum - 2 * t);
		}
	}
	for(int i = 1;i<=5;i++){
		sort(vec[i][0].begin(),vec[i][0].end());
		for(int j = 1;j<=5;j++){
			sort(vec[i][j].begin(),vec[i][j].end());
		}
	}
	int ans = 0;
	for(int i = 1;i<=n;i++){
		if(dat[i].length() == 1){
			t = dat[i][0] - '0';
			ans += find(1,0);
			ans += find(3,1);
			ans += find(5,2);
			}
		if(dat[i].length() == 3){
			t = (dat[i][0] - '0') + (dat[i][1] - '0') + (dat[i][2] - '0');
			ans += find(3,0);
			ans += find(5,1);
			t -= 2 * (dat[i][2] - '0');
			ans += find(1,0);
			}
		if(dat[i].length() == 5){
			t = 0;
			for(int j = 0;j<5;j++) t += dat[i][j] - '0';
			ans += find(5,0);
			t -= 2 * (dat[i][4] - '0');
			ans+= find(3,0);
			t -= 2 * (dat[i][3] - '0');
			ans += find(1,0);	
		}
		if(dat[i].length() == 2){
			t = dat[i][0] - '0' + dat[i][1] - '0';
			ans += find(2,0);
			ans += find(4,1);
		}
		if(dat[i].length() == 4){
			t = 0;
			for(int j = 0;j<4;j++) t += dat[i][j] - '0';
			ans += find(4,0);
			t -= (dat[i][3] - '0') * 2;
			ans += find(2,0);
		}
	}
	cout<<ans;

}
signed main(){
	int T;
	T = 1;
	while(T--){
		solve();
	}
	return 0;
}