洛谷P1117 优秀的拆分【Hash】【字符串】【二分】【好难不会】

题目描述

如果一个字符串可以被拆分为

例如，对于字符串

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令

现在给出一个长度为

以下事项需要注意：

出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
在一个拆分中，允许出现
字符串本身也是它的一个子串。

输入输出格式

输入格式：

每个输入文件包含多组数据。

输入的第一行只有一个整数

接下来

输出格式：

输出

输入输出样例

输入样例#1：复制

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

输出样例#1：复制

说明

我们用 $S_{i,j}Si,j表示字符串 SS第 ii个字符到第jj个字符的子串（从11开始计数）。$

第一组数据中，共有

$S_{1,4}=aabbS1,4=aabb，优秀的拆分为A=aA=a，B=bB=b；$

$S_{3,6}=bbbbS3,6=bbbb，优秀的拆分为 A=bA=b，B=bB=b；$

$S_{1,6}=aabbbbS1,6=aabbbb，优秀的拆分为 A=aA=a，B=bbB=bb。$

而剩下的子串不存在优秀的拆分，所以第一组数据的答案是

第二组数据中，有两类，总共

对于子串 $S_{1,4}=S_{2,5}=S_{3,6}=ccccS1,4=S2,5=S3,6=cccc，它们优秀的拆分相同，均为A=cA=c，B=cB=c，但由于这些子串位置不同，因此要计算33 次；$

对于子串 $S_{1,6}=ccccccS1,6=cccccc，它优秀的拆分有 22种：A=cA=c，B=ccB=cc和 A=ccA=cc，B=cB=c，它们是相同子串的不同拆分，也都要计入答案。$

所以第二组数据的答案是

第三组数据中， $S_{1,8}S1,8和 S_{4,11}S4,11 各有 22 种优秀的拆分，其中S_{1,8}S1,8 是问题描述中的例子，所以答案是2+2=42+2=4。$

第四组数据中， $S_{1,4},S_{6,11},S_{7,12},S_{2,11},S_{1,8}S1,4,S6,11,S7,12,S2,11,S1,8 各有 11种优秀的拆分，S_{3,14}S3,14 有22 种优秀的拆分，所以答案是 5+2=75+2=7。$

对于全部的测试点,保证

我们假定

暴力Hash 80分TLE

枚举子串，枚举A的长度，hash比较

 1 #include <iostream>
 2 #include <set>
 3 #include <cmath>
 4 #include <stdio.h>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 using namespace std;
11 typedef long long LL;
12 #define inf 0x7f7f7f7f
13 
14 const int maxn = 3e4 + 5;
15 
16 int t;
17 char s[maxn];
18 unsigned long long h[maxn], p[maxn];
19 int get_hash(int i, int j)
20 {
21     return h[j] - h[i - 1] * p[j - i + 1];
22 }
23 
24 
25 int main()
26 {
27     scanf("%d", &t);
28     p[0] = 1;
29     for(int i = 1; i < maxn; i++){
30         p[i] = p[i - 1] * 131;
31     }
32     while(t--){
33         scanf("%s", s + 1);
34         int len = strlen(s + 1);
35         for(int i = 1; i <= len; i++){
36             h[i] = h[i - 1] * 131 + s[i] - 'a' + 1;
37         }
38 
39         int ans = 0;
40         for(int i = 1; i <= len; i++){
41             for(int j = i + 1; j <= len; j += 2){
42                 int l = j - i + 1;
43                 for(int x = 1; x <= l / 2 - 1; x++){
44                     int y = l / 2 - x;
45                     if(get_hash(i, i + x - 1) == get_hash(i + x, i + 2 * x - 1)
46                        && get_hash(i + 2 * x, i + 2 * x + y - 1) == get_hash(i + 2 *  x + y, i + l - 1)){
47                         ans++;
48                     }
49                 }
50             }
51         }
52         printf("%d
", ans);
53     }
54 
55     return 0;
56 }

View Code

稍微优化了一下的暴力Hash 95分TLE

用l[i]表示以i为结尾的满足AA串的个数， r[i]表示以i+1为开头的满足BB串的个数

 1 #include <iostream>
 2 #include <set>
 3 #include <cmath>
 4 #include <stdio.h>
 5 #include <cstring>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <map>
10 using namespace std;
11 typedef long long LL;
12 #define inf 0x7f7f7f7f
13 
14 const int maxn = 3e4 + 5;
15 
16 int t;
17 char s[maxn];
18 unsigned long long h[maxn], p[maxn];
19 int l[maxn], r[maxn];
20 int get_hash(int i, int j)
21 {
22     return h[j] - h[i - 1] * p[j - i + 1];
23 }
24 
25 
26 int main()
27 {
28     scanf("%d", &t);
29     p[0] = 1;
30     for(int i = 1; i < maxn; i++){
31         p[i] = p[i - 1] * 131;
32     }
33     while(t--){
34         scanf("%s", s + 1);
35         int len = strlen(s + 1);
36         for(int i = 1; i <= len; i++){
37             h[i] = h[i - 1] * 131 + s[i] - 'a' + 1;
38         }
39 
40         int ans = 0;
41         for(int i = 1; i <= len; i++){
42             l[i] = r[i] = 0;
43             for(int j = i / 2; j >= 1; j--){
44                 if(get_hash(i - 2 * j + 1, i - j) == get_hash(i - j + 1, i)){
45                     l[i]++;
46                 }
47             }
48             for(int j = (len - i) / 2; j >= 1; j--){
49                 if(get_hash(i + 1, i + j) == get_hash(i + j + 1, i + 2 * j)){
50                     r[i]++;
51                 }
52             }
53         }
54         for(int i = 1; i <= len; i++){
55             ans += l[i] * r[i];
56         }
57         printf("%d
", ans);
58     }
59 
60     return 0;
61 }

View Code

还需要继续优化一下找l和r数组的过程，枚举AA串的一半长度L，把整个字符串都分成长为L的好几段。

比如我们现在看第i段的起始点，第i段和第i-1段找一个最长公共前缀，i-1段和第i-2段找一个最长公共后缀。

如果lcs和lcp的长度大于L的话，说明是存在这样一个AA串的【画个图就能理解了】

如果lcs+lcp=L，那么恰好有这么一个串，如果大于L，那么重叠多少，就有多少个这样的串。

用差分的思想进行统计。本来是这个区间都需要++的，现在只给这个区间的开头++，最后求和。那么区间结尾之后的都是多加了的，就给他--

要注意head应该是在[i-l~i]区间， tail在[i-i+L]区间，最后答案要使用longlong

还有题目给的数据范围3e4是不够的，会RE。

  1 #include <iostream>
  2 #include <set>
  3 #include <cmath>
  4 #include <stdio.h>
  5 #include <cstring>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <queue>
  9 #include <map>
 10 using namespace std;
 11 typedef long long LL;
 12 #define inf 0x7f7f7f7f
 13 
 14 const int maxn = 5e4 + 5;
 15 
 16 int t;
 17 char s[maxn];
 18 unsigned long long h[maxn], p[maxn];
 19 LL u[maxn], v[maxn];
 20 unsigned long long get_hash(int i, int j)
 21 {
 22     return h[i] - h[j] * p[j - i];
 23     //return h[j] - h[i - 1] * p[j - i + 1];
 24 }
 25 
 26 
 27 int main()
 28 {
 29     scanf("%d", &t);
 30     p[0] = 1;
 31     for(int i = 1; i < maxn; i++){
 32         p[i] = p[i - 1] * 131;
 33     }
 34     while(t--){
 35         //memset(u, 0, sizeof(u));
 36         //memset(v, 0, sizeof(v));
 37         scanf("%s", s + 1);
 38         int len = strlen(s + 1);
 39         h[len + 1] = 0;
 40         for(int i = len; i >= 1; i--){
 41             u[i] = v[i] = 0;
 42             h[i] = h[i + 1] * 131 + s[i] - 'a' + 1;
 43         }
 44         /*for(int i = 1; i <= len; i++){
 45             u[i] = v[i] = 0;
 46             h[i] = h[i - 1] * 131 + s[i] - 'a' + 1;
 47         }*/
 48 
 49         for(int l = 1; l * 2 <= len; l++){//枚举A的长度
 50             for(int i = l + l; i <= len; i += l){//分块
 51                 if(s[i] != s[i - l]){
 52                     continue;
 53                 }
 54                 //与上上个块求最长公共后缀
 55                 int st = 1, ed = l, last = i - l, pos = 0;
 56                 while(st <= ed){
 57                     int mid = (st + ed) / 2;
 58                     if(get_hash(last - mid + 1, last + 1) == get_hash(i - mid + 1, i + 1)){
 59                         st = mid + 1;
 60                         pos = mid;
 61                     }
 62                     else{
 63                         ed = mid - 1;
 64                     }
 65                 }
 66                 int head = i - pos + 1;
 67 
 68                 //与上一个块求最长公共前缀
 69                 st = 1;ed = l; pos = 0;
 70                 while(st <= ed){
 71                     int mid = (st + ed) / 2;
 72                     if(get_hash(last, last + mid) == get_hash(i, i + mid)){
 73                         st = mid + 1;
 74                         pos = mid;
 75                     }
 76                     else{
 77                         ed = mid - 1;
 78                     }
 79                 }
 80                 int tail = i + pos - 1;
 81                 head = max(head + l - 1, i);
 82                 tail = min(tail, i + l - 1);
 83                 if(head  <= tail){
 84                     u[head - l * 2 + 1]++;
 85                     u[tail + 1 - 2 * l + 1]--;
 86                     v[head]++;
 87                     v[tail + 1]--;
 88                 }
 89             }
 90         }
 91 
 92         LL ans = 0;
 93         for(int i = 1; i <= len; i++){
 94             u[i] += u[i - 1];
 95             v[i] += v[i - 1];
 96         }
 97         for(int i = 1; i < len; i++){
 98             ans += v[i] * u[i + 1];
 99         }
100         printf("%lld
", ans);
101     }
102 
103     return 0;
104 }