Prefix Equality 【DP | 哈希】

E - Prefix Equality

题意：给出两段整数序列a,b，接着是q次询问，询问给出两个整数x,y，问a的前x位数字和b的前y位数字种类是否完全相同。

DP的思想！

• 我们只关心a前x位数字储存的信息和b前y位储存的信息
• 信息储存什么东西呢？对于这个题，数字可能相同，我们只关心数字第一次出现的位置，储存到prea里面
• ansa表示对于a的前x个数字，b相应数字出现的坐标的最大值，如果a的前x数字中b中不存在某数，则设为inf。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
int a[200010], b[200010];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    std::map<int, int> prea,preb;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if(!prea.count(a[i]))prea[a[i]] = i;
    }
    for (int i = 1; i <= n; i ++ ) {
        cin >> b[i];
        if(!preb.count(b[i]))preb[b[i]] = i;
    }
    std::vector<int> ansa(n + 1, 0), ansb(n + 1, 0);
    for (int i = 1; i <= n; i ++ ) {
        ansa[i] = max(ansa[i - 1], preb.count(a[i]) ? preb[a[i]] : inf);
        ansb[i] = max(ansb[i - 1], prea.count(b[i]) ? prea[b[i]] : inf);   
    }
 
    int t;
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        cout << ((ansb[y] <= x && ansa[x] <= y) ? "Yes" : "No") << '\n';
    }   
    return 0;
}

哈希

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll a[200010], b[200010];
set<ll> se;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    ll s = 0;
    for (int i = 1; i <= n; i ++ ) {
        ll x;
        cin >> x;
        if(se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        a[i] = s;
        se.insert(x);
    }
    se.clear();
    s = 0;
    for (int i = 1; i <= n; i ++ ) {
        ll x;
        cin >> x;
        if(se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        b[i] = s;
        se.insert(x);
    }
    int t;
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        if(a[x] == b[y]) {
            cout << "Yes\n";
        }
        else cout << "No\n";
    }   
    return 0;
}