Atcoder Beginner Contest 367

老规矩此处略过前三题，不过B值得关注一下。

D题 Pedometer

思路肥肠煎蛋，只需要搞一个前缀额然后看前面的前缀和是否有跟当前的前缀和同余的情况(%M)

暴力求解这步是O(n^2)的，因此需要优化。这里就用到了一个技巧——哈希表消除分支。

所谓的哈希表消除分支其实就是mp[pre_s]存一下看前面有多少个和为pre_s前缀和。

如果当前的前缀和是S % M，那么只需要去前面找mp[S % M]。

对于一个环状的情况，可以将数组复制两份——破环成链！！！

#include<iostream>
#include<cstring>
#define int long long

using namespace std;
const static int N = 1000010;
int a[N], b[N];

signed main(){
    memset(b, 0, sizeof b);
    int n, k;
    cin >> n >> k;
    b[0] = 1;
    int s = 0;
    int ans = 0;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n - 1; i++){    
        s += a[i];
        ans += b[s % k];
        b[s % k]++;
    }
    
    int s1 = 0;
    for(int i = n - 1; i > 0; i--){
        b[s % k]--;
        s -= a[i - 1];
        s1 += a[i];
        ans += b[(k - (s1 % k)) % k];
    }
    cout << ans << endl;
    return 0;
}

E题 Permute K times

这个题非常经典，首先注意到数据范围——操作次数K的范围在1e18，显然我们不能枚举每次操作。

这个时候就需要用到倍增。st[i][j]表示从下标i开始，进行2^j次操作后的下标。那么对于1e18次操作，我们只需要大约60次枚举就行。

因此，对于每一个下标，直接进行枚举就完美解决问题了。

#include<iostream>
#define int long long

using namespace std;

const static int N = 200010, M = 63;
int n, k;
int a[N], X[N], st[N][M];

signed main(){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)cin >> X[i];
    for(int i = 1; i <= n; i++)cin >> a[i], st[i][0] = X[i];
    
    //枚举步数
    for(int j = 1; j < M; j++){
        for(int i = 1; i <= n; i++){
            st[i][j] = st[st[i][j - 1]][j - 1];
        }
    }

    for(int i = 1; i <= n; i++){
        int x = i, t = k;
        for(int j = M - 1; j >= 0; j--){
            if(t >= (1ll << j)){
                t -= (1ll << j);
                //跳2^j步
                x = st[x][j];
            }
        }
        cout << a[x] << ' ';
    }
    return 0;
}

F题 Rearrange Query

问题很简单，对于每次询问，就是回答A[L，R]和B[L，R]之间的元素是否能够一一对应，即我们要快速维护每个数频率。这个时候就考验你对已学知识的掌握了。字符串哈希的思想。

我们只需要找到一个大质数(类似大数取模哈希)，然后分别为每一个值分配一个哈希值。因为数组元素的范围为，因此我们可以直接枚举1 ~ N，为每一个数分配一个权值，类似十进制给每个数位分配权值。

然后查询就直接用前缀和比较两个子数组的映射值是否相同即可。

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
const static ull M = 9982443537;

void solve() {

    int n, q, v;
    cin >> n >> q;
    vector<ull> P(n + 1), a(n + 1), pre(n + 1);
    P[0] = 1;
    for(int i = 1; i <= n; i++) {
        P[i] = P[i - 1] * M;
    }
    for(int i = 1; i <= n; i++) {
        cin >> v;
        a[i] = a[i - 1] + P[v];
    }
    
    for(int i = 1; i <= n; i++) {
        cin >> v;
        pre[i] = pre[i - 1] + P[v];
    }

    while(q--) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        //直接比较两个子数组的映射值
        if(a[y1] - a[x1 - 1] == pre[y2] - pre[x2 - 1]) {
            cout<< "Yes" << endl;
        } else {
            cout<< "No" << endl;
        }
    }
    return;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while(t--) {
        solve();
    }
    return 0;
}

有同学会问这个大质数怎么来的，wa两发就出来了[doge]

本文到此结束。