首页 > 代码库 > [BZOJ 3207] 花神的嘲讽计划Ⅰ【Hash + 可持久化线段树】
[BZOJ 3207] 花神的嘲讽计划Ⅰ【Hash + 可持久化线段树】
题目链接：BZOJ - 3207
题目分析
先使用Hash，把每个长度为 k 的序列转为一个整数，然后题目就转化为了询问某个区间内有没有整数 x 。
这一步可以使用可持久化线段树来做，虽然感觉可以有更简单的做法，但是我没有什么想法...
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int MaxN = 200000 + 5, P = 233, Mod = 3371723, MaxNode = 8000000 + 5; int n, m, k, en, TL_Index, Node_Index;int A[MaxN], B[MaxN], Root[MaxN], Lc[MaxNode], Rc[MaxNode], T[MaxNode];struct HashNode { int Pos, TL; HashNode *Next;} H[MaxN], *Ph = H, *Hash[Mod + 5];bool Cmp(int *AA, int x, int *AB, int y) { for (int i = 0; i < k; ++i) if (AA[x + i] != AB[y + i]) return false; return true;}void Insert(int &Now, int Last, int s, int t, int x) { if (Now == 0) Now = ++Node_Index; if (s == t) { T[Now] = T[Last] + 1; return; } int m = (s + t) >> 1; if (x <= m) { Rc[Now] = Rc[Last]; Insert(Lc[Now], Lc[Last], s, m, x); } else { Lc[Now] = Lc[Last]; Insert(Rc[Now], Rc[Last], m + 1, t, x); }}int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) scanf("%d", &A[i]); en = n - k + 1; int HN, TL_i; HashNode *Now; TL_Index = 0; Node_Index = 0; for (int i = 1; i <= en; ++i) { HN = 0; for (int j = i; j < i + k; ++j) { HN = HN * P + A[j]; if (HN > Mod) HN %= Mod; } Now = Hash[HN]; TL_i = 0; while (Now != NULL) { if (Cmp(A, i, A, Now -> Pos)) { TL_i = Now -> TL; break; } Now = Now -> Next; } if (TL_i == 0) { ++Ph; Ph -> Pos = i; Ph -> TL = TL_i = ++TL_Index; Ph -> Next = Hash[HN]; Hash[HN] = Ph; } Insert(Root[i], Root[i - 1], 1, n, TL_i); } int l, r, s, t, mid, x, y; for (int i = 1; i <= m; ++i) { scanf("%d%d", &l, &r); for (int j = 1; j <= k; ++j) scanf("%d", &B[j]); HN = 0; for (int j = 1; j <= k; ++j) { HN = HN * P + B[j]; if (HN > Mod) HN %= Mod; } TL_i = 0; Now = Hash[HN]; while (Now != NULL) { if (Cmp(B, 1, A, Now -> Pos)) { TL_i = Now -> TL; break; } Now = Now -> Next; } if (TL_i == 0 || r - l + 1 < k) printf("Yes\n"); else { r = r - k + 1; x = Root[l - 1]; y = Root[r]; s = 1; t = n; while (s != t) { mid = (s + t) >> 1; if (TL_i <= mid) { x = Lc[x]; y = Lc[y]; t = mid; } else { x = Rc[x]; y = Rc[y]; s = mid + 1; } } if (T[y] - T[x] > 0) printf("No\n"); else printf("Yes\n"); } } return 0;}
[BZOJ 3207] 花神的嘲讽计划Ⅰ【Hash + 可持久化线段树】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。