AtCoder Beginner Contest 367

A – Shout Everyday (abc367 A)

题目大意

高桥从\(A\)睡到 \(B\)，如果在 \(C\)时，他醒着，他则会对章鱼烧发癫，问他今天是否发癫。

解题思路

由于只有\(24\)小时，直接枚举 \(A \to B\)，看看是否遍历到 \(C\)即可。

神奇的代码

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b, c;
    cin >> a >> b >> c;
    bool ok = true;
    for (; a != b; a = (a + 1) % 24) {
        if (a == c) {
            ok = false;
            break;
        }
    }
    if (ok)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

---

B – Cut .0 (abc367 B)

题目大意

给定一个小数，将末尾零删掉，如果小数部分删掉则把小数部分删掉。

解题思路

按照题意模拟即可。

神奇的代码

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    while (s.back() == '0')
        s.pop_back();
    if (s.back() == '.')
        s.pop_back();
    cout << s << '\n';

    return 0;
}

---

C – Enumerate Sequences (abc367 C)

题目大意

输出所有符合要求的数组\(a\)，满足

• \(a\)的和是 \(k\)的倍数
• \(a_i\)的范围是 \(1 \sim r_i\)

解题思路

用\(dfs\)枚举所有的情况即可。

神奇的代码

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    vector<int> ans(n);
    auto dfs = [&](auto&& self, int pos) -> void {
        if (pos == n) {
            if (accumulate(ans.begin(), ans.end(), 0) % k == 0) {
                for (auto i : ans)
                    cout << i << " ";
                cout << '\n';
            }
            return;
        }
        for (int i = 1; i <= a[pos]; ++i) {
            ans[pos] = i;
            self(self, pos + 1);
        }
    };
    dfs(dfs, 0);

    return 0;
}

---

D – Pedometer (abc367 D)

题目大意

环形湖的\(n\)个点，给定 \(a_i\)表示从第 \(i\)个点顺时针走到第 \(i+1\)个点的时间。

问对数 \((s,t)\)，满足从 \(s\)顺时针 \(\to t\)，使得其时间是\(m\)的倍数。

解题思路

考虑\(s \leq t\)的情况，其实就可以假象在一条数轴上，从左走到右的时间，这个时间其实就是 \(\sum_{i=s}^{t-1} a_i\)，这里可以预处理出 \(a_i\)的前缀和，其实就是换算成下标 \(pos_i\)，那么从 \(s \to t\)，就是 \(pos_t – pos_s\)，其差值是 \(m\)的倍数 ，这个就意味着\(pos_t \% m == pos_s \% m\)。所以统计 \((s,t)\)的对数，其实就是统计 \(pos_i \% m\)的个数问题。

枚举 \(t\)，然后考虑有多少的 \(s \leq t\)符合要求，而符合要求的 \(s\)就是满足 \(pos_t \% m == pos_s \% m\)，所以用 \(cnt\)维护\(pos_s \% m\)的个数，那么枚举 \(t\)，符合要求的 \(s\)的数量就是 \(cnt[pos_t \% m]\)。

而对于，考虑 \(s > t\)的情况 可以把环形解成链再翻倍一下，即\(1，2, 3, 4, 1, 2, 3, 4\)，后面的\(1\)的位置就是\(pos_1 + \sum pos_i\)，即偏移了一圈的距离。然后在枚举第二圈的\(t\)时，\(cnt\)维护的是第一圈的\(t+1 \sim\)第一圈的 \(n\)的 \(pos_i \% m\)的数量。

神奇的代码

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    vector<int> cnt(m, 0);
    LL ans = 0;
    LL presum = 0;
    for (int i = 0; i < n; ++i) {
        ans += cnt[presum % m];
        cnt[presum % m]++;
        presum += a[i];
    }
    LL sum = presum;
    presum = 0;
    for (int i = 0; i < n; ++i) {
        cnt[presum % m]--;
        ans += cnt[sum % m];
        sum += a[i];
        presum += a[i];
    }
    cout << ans << '\n';

    return 0;
}

---

E – Permute K times (abc367 E)

题目大意

给定数组\(x,a\)，进行 \(k\)次操作。

每次操作，求数组 \(b_i = a_{x_i}\)，然后 \(b=a\)。

问 \(k\)次操作后的数组 \(a\)。

解题思路

题目其实可以抽象成，给定基环内向森林，点有点权。问从每个点出发，走了\(k\)步后的点的点权。

其中边是\(i \to x_i\)，点权 \(a_i\)。

由于图是固定的，问第 \(k\)步后到达的点，预处理倍增数组 \(run[i][j]\)表示从点 \(j\)出发走了 \(2^i\)步后到达的点。

然后对于每个点用倍增数组求 \(k\)次后的结果即可。

神奇的代码

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    LL k;
    cin >> n >> k;
    vector<vector<int>> run(64, vector<int>(n));
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        --v;
        run[0][i] = v;
    }
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    for (int i = 1; i < 64; i++) {
        for (int j = 0; j < n; j++) {
            run[i][j] = run[i - 1][run[i - 1][j]];
        }
    }
    for (int i = 0; i < n; i++) {
        LL cnt = k;
        int cur = i;
        for (int j = 0; j < 64; j++) {
            if (cnt & (1LL << j)) {
                cur = run[j][cur];
            }
        }
        cout << a[cur] << " \n"[i == n - 1];
    }

    return 0;
}

---

F – Rearrange Query (abc367 F)

题目大意

给定两个数组\(a,b\)，回答 \(q\)个问题。

每个问题给定 \(l,r,L,R\)，问 \(a[l..r]\)能否通过重排，等于 \(b[L..R]\)。

解题思路

如果\(a[l..r]\)能通过重排 \(b[L..R]\)，首先得 \(r-l == R – L\)，然后看每个数的出现次数是否一致。显然这判断代价很大。

一个计算代价小的的必要条件是\(suma[l..r] == sumb[L..R]\)，但不是充分条件，会有误判的概率，会被精心构造的数据卡掉。

因为我们只要求数量相等，如果我们事先对所有数进行一个随机映射，这个误判的概率将极大减小。

神奇的代码

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

unsigned rnd() {
    static unsigned A = 1 << 16 | 3, B = 33333331, C = 2341;
    return C = A * C + B;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<LL> a(n);
    vector<LL> b(n);
    map<int, LL> tr;
    for (auto& x : a) {
        cin >> x;
        if (tr.find(x) == tr.end()) {
            tr[x] = rnd();
        }
    }
    for (auto& x : b) {
        cin >> x;
        if (tr.find(x) == tr.end()) {
            tr[x] = rnd();
        }
    }
    auto presum = [&](vector<LL>& a) {
        int n = a.size();
        vector<LL> s1(n + 1);
        for (int i = 0; i < n; ++i) {
            s1[i + 1] = (s1[i] + tr[a[i]]);
        }
        return s1;
    };

    auto sa1 = presum(a);
    auto sb1 = presum(b);

    auto sum = [&](vector<LL>& s, int l, int r) { return (s[r] - s[l - 1]); };
    auto check = [&](int l, int r, int L, int R) {
        auto SA = sum(sa1, l, r);
        auto SB = sum(sb1, L, R);
        return SA == SB;
    };

    while (q--) {
        int l, r, L, R;
        cin >> l >> r >> L >> R;
        if (r - l == R - L && check(l, r, L, R)) {
            cout << "Yes" << '\n';
        } else {
            cout << "No" << '\n';
        }
    }

    return 0;
}

---

G – Sum of (XOR^K or 0) (abc367 G)

题目大意

给定\(n\)个数的数组\(a\)，问 \(a\)所有的\(2^n-1\)个非空子序列\(b\)的价值和。

一个序列 \(b\)的价值定义如下：

• 如果个数是 \(m\)的倍数，则价值是 \((\oplus b_i)^k\)
• 否则价值是 \(0\)。

解题思路

只会\(m=1\)和 \(k=1\)。

神奇的代码

---