526互联

AtCoder Beginner Contest 327

发布时间 2023-11-04 21:47:25作者: ~Lanly~

A - ab (abc327 A)

题目大意

给定一个字符串\(s\)，问是否包含 ab或ba。

解题思路

遍历判断即可。

神奇的代码 
#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;
    string s;
    cin >> n >> s;
    bool ok = false;
    for (int i = 1; i < n; ++i) {
        ok |= (s[i] == 'a' && s[i - 1] == 'b');
        ok |= (s[i - 1] == 'a' && s[i] == 'b');
    }
    if (ok)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

B - A^A (abc327 B)

题目大意

给定\(b\)，问是否存在 \(a\)使得 \(a^a = b\)。

解题思路

由于指数爆炸的缘故，\(a\)的范围不会很大，枚举\(a\)，看\(b \% a\)是否为 \(0\)，然后用\(b\)不断除以 \(a\) ，看最后除的次数是否等于\(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);
    LL b;
    cin >> b;
    int ans = -1;
    for (int i = 2; i <= 20; ++i) {
        if (b % i != 0)
            continue;
        LL x = b;
        int cnt = 0;
        while (x > 1) {
            x /= i;
            ++cnt;
        }
        if (cnt == i) {
            ans = i;
            break;
        }
    }
    if (b == 1)
        ans = 1;
    cout << ans << '\n';

    return 0;
}

C - Number Place (abc327 C)

题目大意

给定一个\(9 \times 9\)的网格，问是否符合数独局面。

数独局面，即每行 \(1-9\)，每列 \(1-9\)，每个 \(3 \times 3\)的格子有 \(1-9\)。

解题思路

按照条件，逐行、逐列、逐格子分别判断即可。

神奇的代码 
#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);
    array<array<int, 9>, 9> a;
    for (auto& i : a)
        for (auto& j : i)
            cin >> j;
    auto ok = [&]() {
        for (auto& i : a) {
            if (set<int>(i.begin(), i.end()).size() != 9)
                return false;
        }
        for (int i = 0; i < 9; ++i) {
            set<int> cnt;
            for (int j = 0; j < 9; ++j) {
                cnt.insert(a[j][i]);
            }
            if (cnt.size() != 9)
                return false;
        }
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                set<int> cnt;
                for (int x = 0; x < 3; ++x)
                    for (int y = 0; y < 3; ++y) {
                        cnt.insert(a[i * 3 + x][j * 3 + y]);
                    }
                if (cnt.size() != 9)
                    return false;
            }
        }
        return true;
    };
    if (ok())
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

D - Good Tuple Problem (abc327 D)

题目大意

给定两个数组长度为\(m\)，仅包含\(1-n\)的\(a,b\)，问它们是否是一对好数组。

若两个数组是一对好数组，则存在一个长度为\(n\)的\(01\)数组 \(x\)，使得 \(x_{a_i} \neq x_{b_i}, \forall i \in [1, m]\)。

解题思路

将条件抽象成图，相当于是点\(a_i\)和点\(b_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, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for (auto& i : a) {
        cin >> i;
        --i;
    }
    for (auto& i : b) {
        cin >> i;
        --i;
    }
    vector<vector<int>> edge(n);
    for (int i = 0; i < m; ++i) {
        edge[a[i]].push_back(b[i]);
        edge[b[i]].push_back(a[i]);
    }
    vector<int> col(n, -1);
    bool ok = true;
    auto BFS = [&](int st) {
        queue<int> team;
        team.push(st);
        col[st] = 0;
        while (!team.empty()) {
            int u = team.front();
            team.pop();
            int target = (col[u] ^ 1);
            for (auto& v : edge[u]) {
                if (col[v] == -1) {
                    col[v] = target;
                    team.push(v);
                } else if (col[v] != target) {
                    ok = false;
                    return;
                }
            }
        }
    };
    for (int i = 0; i < n && ok; ++i) {
        if (col[i] == -1)
            BFS(i);
    }
    if (ok)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

E - Maximize Rating (abc327 E)

题目大意

给定\(n\)场比赛的表现分\(p_i\)，现在选择一些场比赛，使得这些场比赛的 \(rating\)最大。

如果选择了 \(k\)场比赛 \((q_1, q_2, ..., q_k)\)，则 \(rating\)为

\[\frac{\sum_{i=1}^{k}(0.9)^{k-i}q_i}{\sum_{i=1}^{k}(0.9)^{k-i}} - \frac{1200}{\sqrt{k}} \]

注意这里的\(q\)要按照原来的顺序排列。

解题思路

枚举\(k\)，有几项就变成常数，唯一的变数就是最大化\(\sum_{i=1}^{k}(0.9)^{k-i}q_i\)，这其实就是个经典的背包问题。

设\(dp[i][j]\)表示前 \(i\)场比赛，我选择了\(j\)场的\(\sum_{i=1}^{k}(0.9)^{k-i}q_i\)的最大值。

转移就是考虑当前比赛选或不选，则\(dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] * 0.9 + p_i)\)

初始条件就是\(dp[0][0] = 0\)。

答案就是\(\max(\frac{dp[n][k]}{\sum_{i=1}^{k}(0.9)^{k-i}} - \frac{1200}{\sqrt{k}})\)

时间复杂度是\(O(n^2)\)

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const double inf = numeric_limits<double>::max();

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<double> dp(n + 1, -inf);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        vector<double> dp2 = dp;
        int p;
        cin >> p;
        for (int j = 1; j <= i + 1; ++j) {
            dp2[j] = max(dp2[j], dp[j - 1] * 0.9 + p);
        }
        dp2.swap(dp);
    }
    double ans = -inf;
    double bottom = 1;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dp[i] / bottom - 1200 / sqrt(i));
        bottom = bottom * 0.9 + 1;
    }
    cout << fixed << setprecision(10) << ans << '\n';

    return 0;
}

F - Apples (abc327 F)

题目大意

二维平面，给定若干个点，问一个长宽为\(d \times w\)的矩形所能覆盖的点的数量的最大值。

解题思路

枚举一个维度\(i\)（时间），问题就是在\([i, i + d)\)的范围内的另一维度（地点）的宽度为\(w\)的点数的最大值。

设数组\(a[i]\)表示 \(sum[i, i + w)\)，即当前时间范围内的一个区间的点数，随着时间的流逝，会有新的点加入，会有旧的点删去。其影响的都是一个长度为 \(w\)的\(a\)区间，用线段树维护这个数组 \(a\)即可。

时间复杂度为\(O(n\log n)\)

神奇的代码 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 2e5 + 8;

class segtree {
#define lson (root << 1)
#define rson (root << 1 | 1)

    int max[N << 2], lazy[N << 2];

    inline void pushdown(int root) {
        if (lazy[root]) {
            lazy[lson] += lazy[root];
            max[lson] += lazy[root];
            lazy[rson] += lazy[root];
            max[rson] += lazy[root];
            lazy[root] = 0;
        }
    }

    void update(int root, int l, int r, int L, int R, LL val) {
        if (L <= l && r <= R) {
            lazy[root] += val;
            max[root] += val;
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (L <= mid)
            update(lson, l, mid, L, R, val);
        if (R > mid)
            update(rson, mid + 1, r, L, R, val);
        max[root] = std::max(max[lson], max[rson]);
    }

    int query(int root, int l, int r) { return max[root]; }

  public:
    int n;
    void update(int L, int R, LL val) { update(1, 1, n, L, R, val); }

    int query() { return query(1, 1, n); }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d, w;
    cin >> n >> d >> w;
    vector<array<int, 2>> apple(n);
    for (auto& i : apple)
        cin >> i[0] >> i[1];
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    ranges::sort(id, [&](int a, int b) { return apple[a][0] < apple[b][0]; });
    segtree seg;
    seg.n = N - 8;
    auto it = id.begin();
    int ans = 0;
    for (auto& i : id) {
        while (it != id.end() && apple[*it][0] + d <= apple[i][0]) {
            seg.update(max(1, apple[*it][1] - w + 1), apple[*it][1], -1);
            it = next(it);
        }
        seg.update(max(1, apple[i][1] - w + 1), apple[i][1], 1);
        ans = max(ans, seg.query());
    }
    cout << ans << '\n';

    return 0;
}

G - Many Good Tuple Problems (abc327 G)

题目大意

若两个数组是一对好数组，则存在一个长度为\(n\)的\(01\)数组 \(x\)，使得 \(x_{a_i} \neq x_{b_i}, \forall i \in [1, m]\)。

问所有的长度为\(m\)，仅包含 \(1-n\)的共 \(n^{2m}\)对数组中，好数组的数量。

解题思路

注意到一对数组是好数组，我们将每一位的数字连一条边，这意味着它们所形成的图是一张二分图。

考虑对这个二分图计数。

首先枚举左边部分的点的数量\(k\)，注意到点取值多少不影响结果，因此方案数有 \(C_n^k\)。

然后考虑连边情况，每一条边都是从左边\(k\)个点选一个点，右边 \(n-k\)个点选一个点，然后连边。

但这里要考虑到边的顺序——因为数组有下标顺序，如果不考虑这个顺序的话，方案数就是 \(O((k(n-k))^m)\)，但是这里面有很多重复的情况。考虑如何不计重。然后来写题解了

神奇的代码