P1117 [NOI2016]优秀的拆分 [Hash]

本文主要是介绍P1117 [NOI2016]优秀的拆分 [Hash]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

比较容易想到的是, l[i], r[i] 表示 i 的左右 有多少个 AA 串

那么答案就是  , 于是已经可以 n^2 过 95 了

我们考虑批量处理长度为 L 的AA串, 每隔 L 个位置打一个标记

然后对于两两标记之间前后求一个 LCP(Hash + 二分)

画个图, 就可以看出, 哪些区间是有贡献的, 差分一下就可以了

#include<bits/stdc++.h>
#define N 300050
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int Base = 131;
int T, n; char s[N];
ull Hash[N], Mul[N];
int l[N], r[N];
ull Get(int l, int r){return Hash[r] - Hash[l-1] * Mul[r - l + 1];
}
int LCS(int i, int j){int l = 0, r = i;while(l < r){int mid = (l+r+1) >> 1;if(Get(i - mid + 1, i) == Get(j - mid + 1, j)) l = mid;else r = mid - 1;} return l;
}
int LCP(int i, int j){int l = 0, r = n - j + 1;while(l < r){int mid = (l+r+1) >> 1;if(Get(i, i + mid - 1) == Get(j, j + mid - 1)) l = mid;else r = mid - 1;} return l;
}
int main(){scanf("%d", &T);while(T--){memset(l, 0, sizeof(l));memset(r, 0, sizeof(r));scanf("%s", s+1); n = strlen(s+1);Mul[0] = 1;for(int i=1; i<=n; i++) Mul[i] = Mul[i-1] * Base;for(int i=1; i<=n; i++){Hash[i] = Hash[i-1] * Base + s[i] - 'a';}for(int L=1; L<=n*2; L++){for(int i=1; i<=n; i+=L){int j = i + L;int len1 = min(L, LCS(i, j)); // leftint len2 = min(L, LCP(i, j)); // rightif(len1 + len2 >= L){int res = len1 + len2 - L;r[i - len1 + 1]++; r[i - len1 + res + 1]--;l[j + len2]--; l[j + len2 - res]++;}}}for(int i=1; i<=n; i++) l[i] += l[i-1], r[i] += r[i-1];ll ans = 0;for(int i=1; i<n; i++) ans += 1ll * l[i] * r[i+1];printf("%lld\n", ans);} return 0;
}

 

这篇关于P1117 [NOI2016]优秀的拆分 [Hash]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---