首页 > 代码库 > 计蒜客 UCloud 的安全秘钥（随机化+Hash）
计蒜客 UCloud 的安全秘钥（随机化+Hash）
题目链接 UCloud 的安全秘钥
对于简单的版本，我们直接枚举每个子序列，然后sort一下判断是否完全一样即可。
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)const int N = 200010;int n;int a[N], b[N], c[N];int m,q;int main(){ scanf("%d", &n); rep(i, 1, n) scanf("%d", a + i); scanf("%d", &q); while (q--){ scanf("%d", &m); rep(i, 1, m) scanf("%d", b + i); if (m > n){ puts("0"); continue; } sort(b +1, b + m + 1); int ans = 0; rep(i, 1, n - m +1){ rep(j, 1, m) c[j] = a[i + j - 1]; sort(c + 1, c + m + 1); bool fl = true; rep(j, 1, m) if (c[j] != b[j]){ fl = false; break; } if (fl) ++ans; } printf("%d\n", ans); } return 0;}
对于中等版本，这个时候不能在判断两个序列是否相似上面花太多的条件。
这个时候就想到了Hash
对$1$到$n$的每一个数，随机一个权值。
两个序列相似则有这两个序列的每个元素的Hash和相等
那么就可以维护一个Hash值的前缀和，判断的时候$O(1)$完成。
但Hash和相等只是必要条件，并不是充分条件，当数据大的时候很容易出错。
所以我随机了四组Hash值，仅当四组Hash值都与原串相等时才算相似。
这样出错概率就基本为零了
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)const int N = 50010;const long long mod = 1000007;int n;long long w1[N], w2[N], w3[N], w4[N];long long c1[N], c2[N], c3[N], c4[N];int a[N];int q, m;int b[N << 2];int main(){ srand(0); scanf("%d", &n); rep(i, 1, n) w1[i] = rand() % mod; rep(i, 1, n) w2[i] = rand() % mod; rep(i, 1, n) w3[i] = rand() % mod; rep(i, 1, n) w4[i] = rand() % mod; rep(i, 1, n) scanf("%d", a + i); scanf("%d", &q); while (q--){ int ans = 0; scanf("%d", &m); rep(i, 1, m) scanf("%d", b + i); long long st1 = 0, st2 = 0, st3 = 0, st4 = 0; rep(i, 1, m){ st1 += w1[b[i]]; st2 += w2[b[i]]; st3 += w3[b[i]]; st4 += w4[b[i]]; } memset(c1, 0, sizeof c1); memset(c2, 0, sizeof c2); memset(c3, 0, sizeof c3); memset(c4, 0, sizeof c4); rep(i, 1, n){ c1[i] = c1[i - 1] + w1[a[i]]; c2[i] = c2[i - 1] + w2[a[i]]; c3[i] = c3[i - 1] + w3[a[i]]; c4[i] = c4[i - 1] + w4[a[i]]; } rep(i, 1, n - m + 1){ long long n1 = c1[i + m - 1] - c1[i - 1]; long long n2 = c2[i + m - 1] - c2[i - 1]; long long n3 = c3[i + m - 1] - c3[i - 1]; long long n4 = c4[i + m - 1] - c4[i - 1]; if (n1 == st1 && n2 == st2 && n3 == st3 && n4 == st4) ++ans; } printf("%d\n", ans); } return 0;}
对于困难版本，如果m比较小，则枚举连续子序列的时间会很长。
那么考虑把m小的时候的答案全部塞到map里，询问的时候直接拿出来。
不过Hash的时候还是要保证至少两组，不然出错的概率相当大。
我也是调了好久才卡过去的QAQ
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b) for (int i(a); i <= (b); ++i)#define dec(i, a, b) for (int i(a); i >= (b); --i)typedef long long LL;const int L = 2;const int N = 50010;const LL mod = 1000000007;int S = 10;int n, m, q;int a[N];LL Hash[N][L << 1];LL c[N][L << 1], s[N][L << 1];LL hash_now[L << 1];map <LL, int> mp[20][L << 1];int main(){ scanf("%d", &n); rep(i, 1, n) scanf("%d", a + i); srand(time(0)); rep(op, 0, L - 1){ rep(i, 1, n){ Hash[i][op] = (LL)rand(); } } rep(i, 1, n){ rep(j, 0, L - 1){ c[i][j] = Hash[a[i]][j]; s[i][j] = s[i - 1][j] + c[i][j]; } } S = min(S, n); rep(len, 1, S){ rep(i, 1, n - len + 1){ rep(j, 0, L - 1){ ++mp[len][j][s[i + len - 1][j] - s[i - 1][j]]; } } } for (scanf("%d", &q); q--;){ scanf("%d", &m); memset(hash_now, 0, sizeof hash_now); rep(i, 1, m){ int x; scanf("%d", &x); rep(j, 0, L - 1) hash_now[j] += Hash[x][j]; } if (m <= S){ int ans = 1 << 30; rep(i, 0, L - 1) ans = min(ans, mp[m][i][hash_now[i]]); printf("%d\n", ans); continue; } if (m > n){ puts("0"); continue; } int ans = 0; rep(i, 1, n - m + 1){ bool fl = true; rep(j, 0, L - 1) if (s[i + m - 1][j] - s[i - 1][j] != hash_now[j]) fl = false; if (fl) ++ans; } printf("%d\n", ans); } return 0;}
计蒜客 UCloud 的安全秘钥（随机化+Hash）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。