AtCoder Beginner Contest 365-摩杜云开发者社区

A - Leap Year (abc365 A)

题目大意

给定年份，判断该年是否是闰年。

解题思路

根据闰年的两个条件，注意判断即可。

神奇的代码

#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;
    cin >> a;
    int day = 365;
    if (a % 400 == 0 || (a % 4 == 0 && a % 100 != 0)) {
        day = 366;
    }
    cout << day << '\n';

    return 0;
}

B - Second Best (abc365 B)

题目大意

给定\(n\)个不同的数，问第二大的数的下标。

解题思路

对这\(n\)个数排序，看第二大的下标。或者两遍循环，第一次找到最大值，第二次找除最大值外的最大值。

神奇的代码

#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;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int i, int j) { return a[i] < a[j]; });
    cout << id[n - 2] + 1 << '\n';

    return 0;
}

C - Transportation Expenses (abc365 C)

题目大意

给定\(n\)个人的交通费用\(a_i\)，确定最大补贴额度 \(x\)，使得给每个人的补贴为 \(\min(x, a_i)\)，总补贴额度不超过\(m\)。

解题思路

很显然，\(x\)越高，总补贴额度越高，\(x\)越低，则补贴额度就越低，两者呈单调性。

因此可以二分\(x\)，然后计算补贴额度。计算补贴额度就直接\(for\)循环，求一遍 \(\sum \min(x, a_i)\)即可。

神奇的代码

#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 m;
    cin >> n >> m;
    vector<LL> a(n);
    for (auto& i : a)
        cin >> i;
    LL l = 0, r = m + 1;
    if (accumulate(a.begin(), a.end(), 0LL) <= m) {
        cout << "infinite" << '\n';
    } else {
        auto check = [&](LL x) {
            LL sum = 0;
            for (auto i : a)
                sum += min(i, x);
            return sum <= m;
        };
        while (l + 1 < r) {
            LL mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        cout << l << '\n';
    }

    return 0;
}

以下代码不是二分，先假定\(x\)的取值是 \(a_i\)之中，对 \(a_i\)从小到大遍历，找到最大的，总补贴度不超过 \(m\)的 \(a_i\)，但真正的\(x\)不一定在 \(a_i\)之中，因为此时还有一些多余的钱，还可以分给每个人，只是达不到\(a_{i+1}\)，因此剩余钱再均分给剩余人，得到真正的 \(x\)。

神奇的代码

#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 m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    sort(a.begin(), a.end());
    LL tot = accumulate(a.begin(), a.end(), 0LL);
    if (tot <= m) {
        cout << "infinite" << '\n';
    } else {
        int id = -1;
        LL remain = 0;
        LL presum = 0;
        for (int i = 0; i < n; ++i) {
            LL sum = presum + 1ll * a[i] * (n - i);
            if (sum <= m) {
                id = i;
                remain = m - sum;
            }
            presum += a[i];
        }
        LL ans = m / n;
        if (id != -1) {
            ans = a[id] + remain / (n - id - 1);
        }
        cout << ans << '\n';
    }

    return 0;
}

D - AtCoder Janken 3 (abc365 D)

题目大意

剪刀石头布。

给定青木\(n\)局的操作，要求确定高桥对应的操作，要求：

每一局高桥要么赢，要么平手。
高桥不能连续两局出同样的手势。

最大化高桥赢的局数。

解题思路

考虑某一局高桥能做出的手势，取决于两个

青木此局的手势，决定了高桥不能输
高桥上一局的手势，确保不会连续两局出同样的手势

由此，为了能够作出决策，我们仅需知道第\(i\)局和上一局出的手势 \(j\)即可。

设 \(dp[i][j]\)表示考虑前 \(i\)局，第\(i\)局高桥的手势是 \(j\)，高桥赢的局数的最大值。

转移则考虑高桥当前是赢还是平手（手势不与上一局相同），从\(dp[i-1][*]\)转移过来即可。

神奇的代码

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

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    map<char, int> tr{{'R', 0},
                      {'P', 1},
                      {'S', 2}};
    string t = "PSR";
    array<int, 3> dp{0, 0, 0};
    for (auto& c : s) {
        array<int, 3> dp2{-inf, -inf, -inf};
        int pid = tr[c];
        char hashi = t[pid];
        int id = tr[hashi];
        for (int i = 0; i < 3; i++) {
            if (i != id)
                dp2[id] = max(dp2[id], dp[i] + 1);
            if (i != pid)
                dp2[pid] = max(dp2[pid], dp[i]);
        }
        dp2.swap(dp);
    }
    int ans = *max_element(dp.begin(), dp.end());
    cout << ans << '\n';

    return 0;
}

E - Xor Sigma Problem (abc365 E)

题目大意

给定\(n\)个数 \(a_i\)，求\(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} a_i \oplus a_{i+1} \oplus ... \oplus a_j\)

\(\oplus\)是异或操作。

解题思路

朴素做法显而易见的\(O(n^2)\)。

由于异或操作下，二进制下每一位是相互独立的，因此我们可以考虑每一位的贡献。即考虑\(2^0,2^1,2^2,...,2^31\)在这 \(O(n^2)\)个异或表达式结果中出现的次数。

\(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} a_i \oplus a_{i+1} \oplus ... \oplus a_j = \sum_{i=0}^{31} 2^i cnt_i\)

考虑如何求\(cnt_i\)。

单独考虑每个数二进制下的第\(k\)位，如果 \(2^k\)在一个\(a_i \oplus ... \oplus a_j\)出现过，则这说明这些数的二进制下，第\(k\)位是 \(1\)的次数是奇数。

因此对于 \(k\)，我们求 \(odd_i\)表示 \(a_i\)在二进制下的第 \(k\)位是不是 \(1\)。然后考虑有多少个区间\(odd\)和是奇数。

区间异或和区间加法一样，可以表示成两个前缀和相减。因此求\(odd_i\)的前缀和 \(presum_i = odd_1 \oplus odd_2 \oplus ... \oplus odd_i\) ，则\(odd_i \oplus odd_{i+1} \oplus ... \oplus odd_j = presum_j \oplus presum_{i-1}\)。

因此我们要求有多少对 \((i,j)\)，满足 \(presum_{j} \oplus presum_{i-1} = 1\)，我们可以枚举\(j\)，然后对应的 \(i\)的数量。

如果 \(presum_j = 1\)，则 \(presum_{i-1} = 0\)
如果 \(presum_j = 0\)，则 \(presum_{i-1} = 1\)
因此我们只需在从小到大枚举\(j\)时，实时维护\(presum_i = 0\)和 \(presum_i = 1\)的数量，然后根据\(presum_j\)的取值，就知道对应的 \(i\)的数量。

得到\((i,j)\)对数\(cnt_k\)后，就得到对于当前的 \(k\)，其对答案的贡献就是 \(2^k cnt_k\)。对所有的 \(k\)累计求和即为答案。

注意上述的求法包括了 \(j = i\)的情况，而题意是 \(j > i\)，所以最后再减去所有数的和即可。

神奇的代码

#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;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    LL ans = 0;
    auto solve = [&](int bit) {
        vector<int> odd(n);
        for (int i = 0; i < n; ++i) {
            odd[i] = (a[i] >> bit) & 1;
        }
        for (int i = 1; i < n; ++i) {
            odd[i] = odd[i] ^ odd[i - 1];
        }
        map<int, int> cnt;
        cnt[0] = 1;
        LL sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += cnt[odd[i] ^ 1];
            cnt[odd[i]]++;
        }
        return sum;
    };
    for (int i = 0; i < 32; ++i) {
        ans += (1ll << i) * solve(i);
    }
    ans -= accumulate(a.begin(), a.end(), 0ll);
    cout << ans << '\n';

    return 0;
}

F - Takahashi on Grid (abc365 F)

题目大意

二维网格，\(n \times m\)，每一列有一个连续的空间是空地。每一列的空地必定相交。

回答\(q\)个问题。

每个问题，给定起点终点，每次可以上下左右走一格，问移动的最小步数。

解题思路

显而易见的朴素做法的时间复杂度为\(O(nq)\)，即对于每个询问，从\(sx \to sx+1 \to sx+2 \to ... \to tx\)，一列一列移动。

以下下标\((x,y)\)表示第\(x\)列第\(y\)行，注意与平时表示的意思不同。

考虑移动过程，其实就两个阶段：

第一阶段，能够直接平行移动，即 \((x, y) \to (x + 1, y)\)
第二阶段，不能平行移动了，得上下移动，这时一定有\((x, y) \to (x, l[x+1])\) 或\((x, r[x+1])\)。即抵达下一列的上下两个端点，然后往右边继续移动。

然后这两阶段不断重复。

对于第一阶段，可以通过预处理，在 \(O(\log n)\)的时间内找到平行移动到最右边的边界，即此时会有 \(y < l[x + 1]\)或 \(y > r[x + 1]\) ，因此用\(st\)表预处理 \(lmax[i,j]\)表示列 \([i,j]\)的 \(l\)的最大值， \(rmin[i,j]\)表示列 \([i,j]\)的\(r\)的最小值，通过二分可以找到这个平行移动的边界列。

然后是第二阶段，注意到第二阶段的开始起点只有\(2n\)个：每列要么是从上端点开始，要么从下端点开始。因此我们可以预处理出，从每个这样的起点出发，到达每一列的代价之类的东西。

具体是怎样的东西呢？注意到从这些端点出发，其实后续的路线就是固定了，所以可以用倍增的方法，预处理出从每个端点出发，走\(2^i\)步后，抵达到哪个列的上端点或下端点，代价是多少。

这里的一步指的是必须变动\(y\)的，即经过一次第二阶段，即，如果从\((x,y)\)能平行移动则一直平行移动，直到要上下移动才能抵达下一列\(s\)，这样就称之为一步，从\(x \to s\)， \(y \to l[s]\)或 \(y \to r[s]\)。

定义了一步后，就可以预处理倍增数组\(run[i][x][0/1]\)表示从第 \(x\)行的上/下端点，走 \(i\)步后抵达的 (列，上/下端点，移动次数)这么个三元组。

然后对于每个询问，通过二分求出第一阶段移动的移动次数，此时抵达到第二阶段的一个起点，再通过倍增数组得到移动到 \((tx, ty)\)的移动次数。这里可能不能直接到\((tx, ty)\)，可能最后再通过第一阶段的平行移动到 \(tx\)，再上下移动到 \(ty\)，加个判断即可。

神奇的代码

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

// usage:
//   auto fun = [&](int i, int j) { return min(i, j); };
//   SparseTable<int, decltype(fun)> st(a, fun);
// or:
//   SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
  public:
    int n;
    vector<vector<T>> mat;
    F func;

    SparseTable(const vector<T>& a, const F& f) : func(f) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        mat.resize(max_log);
        mat[0] = a;
        for (int j = 1; j < max_log; j++) {
            mat[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int from, int to) const { // [from, to]
        assert(0 <= from && from <= to && to <= n - 1);
        int lg = 32 - __builtin_clz(to - from + 1) - 1;
        return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++)
        cin >> l[i] >> r[i];
    vector<vector<vector<array<LL, 3>>>> run(
        31, vector<vector<array<LL, 3>>>(
                n, vector<array<LL, 3>>(2, array<LL, 3>{})));
    SparseTable<int> L(l, [&](int i, int j) { return max(i, j); });
    SparseTable<int> R(r, [&](int i, int j) { return min(i, j); });
    auto step = [&](int x, int y) {
        int l = x, r = n;
        while (l + 1 < r) {
            int m = (l + r) / 2;
            if (L.get(x, m) <= y && R.get(x, m) >= y) {
                l = m;
            } else {
                r = m;
            }
        }
        return l + 1;
    };
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 2; ++j) {
            int x = i, y = (j ? r[i] : l[i]);
            int nxt = step(x, y);
            if (nxt == n) {
                run[0][i][j] = {n, 0, n - i};
            } else if (l[nxt] > y) {
                run[0][i][j] = {nxt, 0, l[nxt] - y + nxt - i};
            } else {
                run[0][i][j] = {nxt, 1, y - r[nxt] + nxt - i};
            }
        }
    }

    for (int i = 1; i <= 30; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 2; ++k) {
                auto [nxt, d, cost] = run[i - 1][j][k];
                if (nxt == n) {
                    run[i][j][k] = {n, 0, cost};
                } else {
                    auto [nnxt, dd, ccost] = run[i - 1][nxt][d];
                    run[i][j][k] = {nnxt, dd, cost + ccost};
                }
            }
        }
    }

    auto solve = [&](int sx, int sy, int tx, int ty) -> LL {
        if (sx == tx) {
            return abs(ty - sy);
        }
        if (sx > tx) {
            swap(sx, tx);
            swap(sy, ty);
        }
        int nxt = step(sx, sy);
        if (nxt > tx) {
            return abs(ty - sy) + tx - sx;
        }
        int sign = (sy < l[nxt] ? 0 : 1);
        LL ret = nxt - sx + (sign ? sy - r[nxt] : l[nxt] - sy);
        sx = nxt;
        for (int i = 30; i >= 0; --i) {
            auto [nnxt, dd, ccost] = run[i][sx][sign];
            if (nnxt <= tx) {
                ret += ccost;
                sx = nnxt;
                sign = dd;
            }
        }
        ret += tx - sx + (sign ? abs(ty - r[sx]) : abs(l[sx] - ty));
        return ret;
    };

    int q;
    cin >> q;
    while (q--) {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        --sx, --tx;
        LL ans = solve(sx, sy, tx, ty);
        cout << ans << '\n';
    }

    return 0;
}

G - AtCoder Office (abc365 G)

题目大意

给定\(n\)个员工在公司的若干条时间段，回答 \(q\)个问题。

每个问题，询问两个员工 \(i,j\)同时在公司的时间。

解题思路

<++>

神奇的代码