Educational Codeforces Round 115

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘
G(数学,KMP,string hash)

CF tracker

Edu List

https://codeforces.com/contest/1598

G. The Sum of Good Numbers

十进制下没有0的是好数字

a = 好数字 数组

且其中 a[i]+a[i+1] == x 也是好数字

s = a的字符串拼接

问，输入s和x, 求a[i] 和 a[i+1] 在s中的位置

范围

|s| 5e5

|x| 2e5

2s

256mb

我的思路

两个数字加起来 = x

那么至少一个 >= x/2

所以有一个的长度 = |x| 或 |x-1|(这还需要x的首位是1)

那么可以枚举这个长度

问题变成s[j...j+len]是一个数， 那么它的后临 或 前临 是否是 x-它

这样直接暴力肯定不行, 如何快速计算和比对?

直接数字化 然后 mod 不同的值来算hash?

长度 怎么参与考虑

有个严重的问题就是，做加法或者减法会有进位和借位，所以这似乎就跟字符串算法不太能联系起来了

没有特别想懂 这里没有0的意义, 没有0有什么特殊性质吗? , 27+67 = 94, 依然有进位

然后如果 x 是由两个len = |x|的加起来, 那么可以考虑hash一下所有长度|x|的, 再枚举连接处

x首位>1 则有一个和它首位 差不超过1,

始终感觉没有 把 相邻和求和之间建立任何联系

题解

一样的考虑大的长度

a+b =x, a>=b

|a| = |x|-1 或 |a|=|x|

if $|a| = |x|-1$ then $|b| = |x|-1$ ohhhhhhhhhhhhhhhhhhh !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

这就是我觉得应该有意义的0的意义,但是我自己没找出来的

因为如果 $|a| = |x|-1, |b| < |x|-1$

$a + b >= 1.1 * 10^t$ (没有0的作用

$a < 10^t$

$b < 10^{t-1}$

$a \ge 1.1 * 10^t - 10^{t-1}$

$a \ge 10^t$ 矛盾

if $|a| = |x|$, 考虑$a,x$的最长公共前缀$lcp(a,x)$, 同样的原理 因为不能出现0

$|b| = |x| - lcp(a,x)$ 或 $|b| = |x| - lcp(a,x) -1$

所以(a,b) 的位置只会有O(n) 种， 剩下就是多质数 hash

那这里lcp就直接无脑kmp就可以做

代码

https://codeforces.com/contest/1598/submission/193656762

题解里的质数wa 116了，我又加了个质数

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
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(int)(n);i++)
#define per(i,a,n) for(int i=(n);i-->(int)(a);)

int read(){int r;scanf("%d",&r);return r;}

const int N = 500 * 1000 + 13;
const int K = 4;
const array<int, K> MOD = { 597804841, 618557587, 998244353, 19260817 }; // 可以多点大prime

using hs = array<int, K>;

int add(int x, int y, int mod) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  return x;
}

int mul(int x, int y, int mod) { return x * 1LL * y % mod; }

hs val(const int& x) {
  hs c;
  rep(i,0,K) c[i] = x;
  return c;
}

hs operator +(const hs& a, const hs& b) {
  hs c;
  rep(i,0,K) c[i] = add(a[i], b[i], MOD[i]);
  return c;
}

hs operator -(const hs& a, const hs& b) {
  hs c;
  rep(i,0,K) c[i] = add(a[i], -b[i], MOD[i]);
  return c;
}

hs operator *(const hs& a, const hs& b) {
  hs c;
  rep(i,0,K) c[i] = mul(a[i], b[i], MOD[i]);
  return c;
}

hs sum[N]; // 1-index
hs pw[N]; // pw[p]= 10^p 在hash意义下

// [l,r)
hs get(int l, int r) { return sum[r] - sum[l] * pw[r-l]; }

vector<int> kmp(char *s) { // kmp
  int n = strlen(s);
  vector<int> z(n);
  int len=0;
  rep(i,1,n){
    while(s[i] != s[len] and len != 0) len=z[len-1];
    z[i] = (s[i] == s[len])?++len:len;
  }
  // 转换成前缀
  vector<int> lcp(n);
  rep(i,1,n) if(z[i]) lcp[i-z[i]+1] = max(lcp[i-z[i]+1],z[i]);
  return lcp;
}

char s[500010];
char sx[700010]; // 2e5+5e5+1
int main() {
  scanf("%s",s);
  int n = strlen(s);
  scanf("%s",sx);
  int m = strlen(sx);
  sx[m]='#';
  rep(i,0,n) sx[m+1+i] = s[i];

  // 10^p
  pw[0] = val(1);
  rep(i,0,N-1) pw[i+1] = pw[i] * val(10);
  // s
  sum[0] = val(0);
  rep(i,0,n) sum[i+1] = sum[i] * val(10) + val(s[i]-'0'); // 1-index
  // x
  hs x = val(0);
  rep(i,0,m) x = x * val(10) + val(sx[i]-'0');
  auto o=[](int a,int b,int c,int d){ return printf("%d %d\n%d %d\n",a,b,c,d)*0; };

  if (m > 1) rep(i,0,n-2*(m-1)+1){ // |m-1| + |m-1| = |m|
    // [i...i+m-1) + [i+m-1,i+2(m-1))
    if(get(i,i+m-1)+get(i+m-1,i+2*(m-1))==x)return o(i+1,i+m-1,i+m,i+2*(m-1));
  }

  auto z = kmp(sx);

  rep(i,0,n-m+1){
    int lcp = z[m+1+i];
    for(int len: {m-lcp-1,m-lcp}) if(len >= 1){
      // [i~i+m) + [i+m..i+m+len)
      if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) return o(i+1,i+m,i+m+1,i+m+len);
      // [i-len,i) + [i,i+m)
      if (i >= len && get(i - len, i) + get(i, i + m) == x) return o(i-len+1,i,i+1,i+m);
    }
  }
  assert(false);
  return 0;
}

总结

1h20min 内做了A~E, F做了1h有点久,没啥思路问题，都是编码bug

G. 现场似乎只有tourist和noimi出了这个题

没有智慧, 感觉要去找这个没有0的用途，但是没有找到， 应该找点小数据看看的，优雅的小数据打表应该就能发现了

对于加减的判断也是hash没问题, 还是在这里如何使用0去做长度推演上出了问题

参考

官方