Codeforces898F Restoring the Expression

原题链接:Codeforces898F

题目大意:给定一个只含有数字的字符串 $s$,将其划分成从左到右三部分 $a,b,c$ 且 $a,b,c$ 不能含有前导 $0$。求一种划分,使得 $a+b=c$。

字符串哈希

解法

思路难,代码简单。

做法:如果确定了 $c$ 的长度,那么 $a,b$ 的长度都不可能超过 $c$;又要满足数值上 $a+b=c$,那么 $a,b$ 中至少有一个长度为 $|c|-1$( $|c|$ 表示 $c$ 的长度)。枚举 $c$ 的长度 $[\frac{|s|}{3},\frac{|s|}{2}]$,然后根据上面的两个约束,只需要判断 $4$ 种划分( $\rm Line43\text{~}44$ )是否合法,用哈希值判断。

坑点:划分不能含有前导 $0$,哈希使用的进制必须为十进制。

代码

 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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, base = 10, mod = 19491001;

int n;
char str[N];
LL h[N], p[N];

LL get(int l, int r) {
    return ((h[r] - h[l - 1] * p[r - l + 1]) % mod + mod) % mod;
}

bool check(int a, int b, int c) {
    if (b >= 2 && str[a + 1] == '0') return false;
    if (c >= 2 && str[a + b + 1] == '0') return false;
    LL A = get(1, a), B = get(a + 1, a + b), C = get(a + b + 1, n);
    if ((A + B) % mod == C) {
        for (int i = 1; i <= a; i++) putchar(str[i]);
        putchar('+');
        for (int i = a + 1; i <= a + b; i++) putchar(str[i]);
        putchar('=');
        for (int i = a + b + 1; i <= n; i++) putchar(str[i]);
        puts("");
        return true;
    }
    return false;
}

int main() {
    scanf("%s", str + 1);
    n = strlen(str + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] * base % mod; 
    for (int i = 1; i <= n; i++) h[i] = (h[i - 1] * base + str[i] - '0') % mod;
    for (int c = n / 3; c <= n / 2; c++) {
        if (check(c, n - c * 2, c) || check(c - 1, n - c * 2 + 1, c) || 
            check(n - c * 2, c, c) || check(n - c * 2 + 1, c - 1, c))
            break;
    }
    return 0;
}
updatedupdated2020-05-112020-05-11
加载评论
点击刷新