abc367

A.

模拟

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 7;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(b < c) {
        if(a > c || a < b) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else {
        if(a < c || a > b) {cout << "No" << endl;}
        else cout << "Yes" << endl;
    }
    return 0;
}

B.

模拟

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 7;
int main() {
    string s;
    cin >> s;
    int flag = 1, p;
    for(int i = s.size() - 1; i >= 0; i --) {
        if(s[i] != '0' && flag) {
            flag = 0;
            p = i;
        }
    }
    if(s[p] == '.') p --;
    for(int i = 0; i <= p; i ++) cout << s[i];
    return 0;
}

C.

D.

很典的题，先破环成链，然后可以处理前缀和然后使用 map，可以只使用 \([n + 1, 2n]\) 注意去一下重。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 7;
int a[N];
map<int, int> mp;
int ans;
signed main() {
    int n, m;
    cin >> n >> m;
    int nw = 0;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = n + 1; i <= n * 2; i ++) a[i] = a[i - n];
    for(int i = 1; i <= n; i ++) {
        nw = nw + a[i];
        nw %= m;
        mp[nw] ++;
    }
    int p = nw;
    int o = 0;
    for(int i = n + 1; i <= n * 2; i ++) {
        nw += a[i];
        o = (o + a[i]) % m;
        nw %= m;
        mp[nw] ++;
        mp[o % m] --;
        ans += mp[nw] - 1;
    }   
    cout << ans << endl;
}

E.

考虑跳 \(i\) 次会跳到哪里，可以使用倍增维护。再进行二进制拆分，若 \(k\) 的第 \(i\) 位为1，则要跳 \(2^i\) 次。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 7;
int x[N], a[N];
int f[N][64];
int ans[N];
signed main() {
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> x[i];
    for(int i = 1; i <= n; i ++) f[i][0] = a[i], ans[i] = i;
    for(int j = 1; j <= 63; j ++) {
        for(int i = 1; i <= n; i ++) {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    int p = 0;
    while(k) {
        if(k & 1) {
            for(int i = 1; i <= n; i ++) ans[i] = f[ans[i]][p];
        }
        k >>= 1;
        p ++;
    }
    for(int i = 1; i <= n; i ++) cout << x[ans[i]] << " ";
    return 0;
}

F.

。。

给 \(1\) 到 \(n\) 每个数随即映射到一个整数 \(v_i\)，判断 \(\sum v_{a_i}\) 是否等于 \(\sum v_{b_i}\) 即可。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 7;
int a[N], b[N];
ull h[N], a1[N], b1[N];

mt19937 rng(random_device{}());

int main() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];   
    for(int i = 1; i <= n; i ++) h[i] = rng();
    for(int i = 1; i <= n; i ++) a1[i] = a1[i - 1] + h[a[i]], b1[i] = b1[i - 1] + h[b[i]];
    for(int i = 1; i <= q; i ++) {
        int l, r, L, R;
        cin >> l >> r >> L >> R;
        if(a1[r] - a1[l - 1] == b1[R] - b1[L - 1]) {
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
    return 0;
}