AGC
ARC
ABC
ABC 250
E. Prefix Equality (整數(shù)哈希)
題意
給了兩個長度為 (n) 的數(shù)組,判斷兩者前綴的集合是否相同(長度可以不一樣)。
數(shù)據(jù)范圍
(1leq N,Qleq 2 imes 10^5)
(1leq a_i,b_i leq 10^9)
(1leq x_i,y_i leq N)
思路
- 顯然需要 std::set ,考慮兩個 set 分別記錄兩個數(shù)組每個數(shù)是否出現(xiàn)
- 用兩個數(shù)組對兩個 set 進(jìn)行整數(shù)哈希,
h[i]
表示數(shù)組前 i 位上的哈希值,如果沒有新的數(shù)出現(xiàn)h[i] = h[i - 1]
.
Solution
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "
"
using namespace std;
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rd(seed1);
const int mod = 1e9 + 7;
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
vector<unsigned int> h1(n + 1), h2(n + 1);
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
cin >> b[i];
set<int> s1, s2;
h1[0] = h2[0] = 0;
map<int,ull> mp;
for(int i = 1; i <= n; i++){
h1[i] = h1[i - 1];
h2[i] = h2[i - 1];
if(!mp.count(a[i])){
mp[a[i]] = rd();
}
if(!s1.count(a[i]))
h1[i] += mp[a[i]];
if(!mp.count(b[i]))
mp[b[i]] = rd();
if(!s2.count(b[i]))
h2[i] += mp[b[i]];
s1.insert(a[i]);
s2.insert(b[i]);
}
int q;
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
(h1[x] == h2[y]) ? cout << "Yes
" : cout << "No
";
}
return 0;
}
`
本文摘自 :https://www.cnblogs.com/