CF898 F Restoring the Expression

CF898 F Restoring the Expression

CF898 F Restoring the Expression

题意

给一个由数字组成的长度$10^6$的串,要把串划分成符合整数加法的$“a+b=c”$形式

思路

因为 $a+b=c$ ,所以 $lena$、$lenb$ 至少要有一个等于 $lenc$ 或 $lenc-1$

所以枚举 $lena,lenb$,每次检验一下可不可行,如果可以就直接输出

题解代码

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
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//板子如下
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll Hash[N], p[N], Base = 10;
void Init(string si)
{
int len = si.size(); //记录长度
Hash[0] = 0;
for (int i = 0; i < len; ++i)
Hash[i + 1] = (Hash[i] * Base % mod + si[i] - '0') % mod; //处理出str的hash值
p[0] = 1;
for (int i = 0; i < len; ++i)
p[i + 1] = p[i] * Base % mod;
}
ll get(int l, int r) //得到起点为l,终点为r的子串的hash值
{
if (r < 0 || l - 1 < 0 || r - l + 1 < 0)
return 0;
return (Hash[r] - Hash[l - 1] * p[r - l + 1] % mod + mod) % mod;
}

string si;
int len, lenc;
void print(int lena, int lenb) //找到分割点就直接输出
{
for (int i = 0; i <= lena - 1; i++)
putchar(si[i]);
putchar('+');
for (int i = lena; i <= lena + lenb - 1; i++)
putchar(si[i]);
putchar('=');
for (int i = lena + lenb; i <= len - 1; i++)
putchar(si[i]);
}

bool check(int lena, int lenb) //避免hash碰撞
{
string s1 = si.substr(0, lena);
string s2 = si.substr(lena, lenb);
string s3 = si.substr(lena + lenb, len - lena - lenb);
int flag = 0, len3 = len - lena - lenb, i, j;
for (i = lena - 1, j = lenb - 1; i >= 0 && j >= 0; --i, --j) //下标从0开始,所以初始化都要减一
{
int a1 = s1[i] - '0', a2 = s2[j] - '0', a3 = a1 + a2 + flag;
if (a3 >= 10)
a3 -= 10, flag = 1; //进一
else
flag = 0;
if (a3 != s3[len3 - (lena - i)] - '0') //对比数字是否相同
return false;
}
return true;
}
bool solve(int lena, int lenb) //枚举的是a和b
{
if (lena > lenc || lenb > lenc) //加法结果位数最大
return false;
if (lena < 0 || lenb < 0) //不存在
return false;
if (si[lena] == '0' && lenb != 1) //a,b和c这三个部分都不包含前导零,除非它本身是0
return false;
if (si[lena + lenb] == '0' && len - lena - lenb != 1) //同上
return false;
if ((get(1, lena) + get(lena + 1, lena + lenb)) % mod != get(lena + lenb + 1, len)) //用hash值看看能不能成立
return false;
//return true;
return check(lena, lenb); //hash只能拒绝大部分,防止碰撞
}
int main()
{
cin >> si;
Init(si); //hash模板
len = si.size();
for (lenc = 1; lenc <= len - 2; ++lenc) //枚举a和b
{
if (solve(lenc, len - lenc * 2)) //当lenc和lena相同
{
print(lenc, len - lenc * 2);
return 0;
}
if (solve(lenc - 1, len - lenc - (lenc - 1))) //当lena比lenc少一位
{
print(lenc - 1, len - lenc - (lenc - 1));
return 0;
}
if (solve(len - lenc * 2, lenc)) //当lenc和lenb相同
{
print(len - lenc * 2, lenc);
return 0;
}
if (solve(len - lenc - (lenc - 1), lenc - 1)) //当lenb比lenc少一位
{
print(len - lenc - (lenc - 1), lenc - 1);
return 0;
}
}
return 0;
}

Hash模板解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll Hash[N], p[N], Base = 10;//Base玄学值貌似可以随意
void Init(string si)
{
int len = si.size(); //记录长度
Hash[0] = 0;
for (int i = 0; i < len; ++i)
Hash[i + 1] = (Hash[i] * Base % mod + si[i] - '0') % mod; //处理出str的hash值
p[0] = 1;
/*
这个p数组用于便于计算子串的hash值
也就是下面get函数的实现
*/
for (int i = 0; i < len; ++i)
p[i + 1] = p[i] * Base % mod;
}
ll get(int l, int r) //得到起点为l,终点为r的子串的hash值
{
if (r < 0 || l - 1 < 0 || r - l + 1 < 0)
return 0;
return (Hash[r] - Hash[l - 1] * p[r - l + 1] % mod + mod) % mod;
//为了让同样的子串输出同样的hash
}