AtCoder Beginner Contest 322

2023-10-01 00:27 由 ~Lanly~ 发表于 #其他

A - First ABC 2 (abc322 A)

题目大意

给定一个字符串，找到最先出现ABC的位置。

解题思路

直接查找判断即可。

神奇的代码

#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;
    int pos = s.find("ABC");
    if (pos == string::npos)
        pos = -2;
    cout << pos + 1 << '\n';

    return 0;
}

B - Prefix and Suffix (abc322 B)

题目大意

给定字符串 s和t，问s是不是t的前缀和后缀。

解题思路

根据前后缀定义判断即可。这里试了下python

神奇的代码

n, m = map(int, input().split(' '))
s = input()
t = input()
prefix = t.startswith(s)
suffix = t.endswith(s)
if prefix and suffix:
    print(0)
elif prefix and not suffix:
    print(1)
elif not prefix and suffix:
    print(2)
else:
    print(3)

C - Festival (abc322 C)

题目大意

\(n\)天，有\(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> day(m);
    for (auto& i : day)
        cin >> i;
    int cur = 0;
    for (int i = 1; i <= n; ++i) {
        if (i > day[cur])
            ++cur;
        cout << day[cur] - i << '\n';
    }

    return 0;
}

D - Polyomino (abc322 D)

题目大意

给定三个多米诺骨牌，问能否不重叠地摆成\(4 \times 4\)的方格。

解题思路

数不大，直接暴力搜索。

考虑搜索方式，虽然给了个\(4 \times 4\)的多米诺骨牌的表示形式，但我们就枚举这个 \(4 \times 4\) 的方格的位置。

设想我们的画布就是一个\(4 \times 4\)的方格，然后枚举一个多米诺骨牌盖章左上角的位置（可以在这个画布之外），以及旋转的角度，然后一盖，在该区域的多米诺骨就被保留下来。最后我们就看该区域是否填满了，且没重叠，且无多米诺骨牌在外面。

代码实现里没有真正的盖，只取了盖在画布上的格子，方法类似于

神奇的代码

#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<string, 4>, 3> tu;
    int cnt = 0;
    for (auto& i : tu)
        for (auto& j : i) {
            cin >> j;
            cnt += count(j.begin(), j.end(), '#');
        }
    array<array<char, 4>, 4> page{};
    int dx1[2] = {1, -1};
    int dy1[2] = {1, -1};
    int dx2[2] = {1, -1};
    int dy2[2] = {-1, 1};
    auto fit1 = [&](int k, int x, int y, int d) {
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j) {
                int nx = x + dx1[d] * i, ny = y + dy1[d] * j;
                if (tu[k][i][j] == '#') {
                    if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
                        if (page[nx][ny] == '#') {
                            return false;
                        }
                        page[nx][ny] = '#';
                    } else {
                        return false;
                    }
                }
            }
        return true;
    };
    auto fit2 = [&](int k, int x, int y, int d) {
        for (int i = 0; i < 4; ++i)
            for (int j = 0; j < 4; ++j) {
                int nx = x + dx2[d] * j, ny = y + dy2[d] * i;
                if (tu[k][i][j] == '#') {
                    if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
                        if (page[nx][ny] == '#') {
                            return false;
                        }
                        page[nx][ny] = '#';
                    } else {
                        return false;
                    }
                }
            }
        return true;
    };
    function<bool(int)> ok = [&](int k) {
        if (k == 3) {
            return true;
        }
        auto bak = page;
        for (int x = -3; x <= 7; ++x)
            for (int y = -3; y <= 7; ++y) {
                for (int d = 0; d < 2; ++d) {
                    if (fit1(k, x, y, d)) {
                        if (ok(k + 1))
                            return true;
                    }
                    page = bak;
                    if (fit2(k, x, y, d)) {
                        if (ok(k + 1))
                            return true;
                    }
                    page = bak;
                }
            }
        return false;
    };
    if (cnt == 16 && ok(0))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

E - Product Development (abc322 E)

题目大意

一个产品，有\(k\)个性能参数，初始为\(0\)，要求进行一些提升计划，使得每个性能参数不小于 \(p\)，且代价最小。

每个提升计划包含一个代价，以及对这\(k\)个性能参数提升的数值。

解题思路

注意到\(k,p\)最大都只有 \(5\)。考虑搜索状态，我们可以设 \(dp[i][a1][a2][a3][a4][a5]\)表示前 \(i\)个提升计划，使得最终性能参数分别为 \(a1,a2,a3,a4,a5\)的最小代价。转移就考虑当前提升计划选或不选即可。

但这里的 \(p\)不一定是 \(5\)，也就是说这个 \(dp\)的维度不是固定的，但由于每一维度的取值只有 \(0 \sim p\)共 \(6\)种情况，最多 \(k=5\)维，因此我们可以把这最后的 \(k\)维压缩成一维的 \(6\)进制数表示。

由于 \(dp[i]\)只依赖于 \(dp[i-1]\)，因此第一维可以滚动数组优化掉。

神奇的代码

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

const LL inf = 1e18;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k, p;
    cin >> n >> k >> p;
    int base = p + 1;
    const int sz = int(pow(base, k));
    vector<LL> dp(sz, inf);
    dp[0] = 0;
    auto dtr = [&](int x) {
        vector<int> ret(k);
        for (int i = k - 1; i >= 0; --i) {
            ret[i] = x % base;
            x /= base;
        }
        return ret;
    };
    auto tr = [&](const vector<int>& x) {
        int ret = 0;
        for (int i = 0; i < k; ++i) {
            ret = ret * base + x[i];
        }
        return ret;
    };
    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c;
        vector<int> x(k);
        vector<LL> dp2 = dp;
        for (auto& i : x)
            cin >> i;
        for (int j = 0; j < sz; ++j) {
            auto now = dtr(j);
            for (int i = 0; i < k; ++i)
                now[i] = min(p, now[i] + x[i]);
            auto nxt = tr(now);
            dp2[nxt] = min(dp2[nxt], dp[j] + c);
        }
        dp.swap(dp2);
    }
    LL ans = dp.back();
    if (ans == inf)
        ans = -1;
    cout << ans << '\n';

    return 0;
}

F - Vacation Query (abc322 F)

题目大意

给定一个\(01\)串\(s\)。维护两种操作。

\(1, l,r\)，将\(s[l..r]\)的数字翻转。
\(2,l,r\)，问\(s[l..r]\)中最长的连续的\(1\)的长度。

解题思路

不考虑修改，仅考虑查询。

考虑如何求解，对于每个\(r\)，我们要找最小的 \(l\)满足 \(sum[r] - sum[l] = r - l\)，其中 \(sum[i]\)表示 \(s[1..i]\)中 \(1\)的个数。

但这涉及到特定区间的信息，感觉难以维护。

注意到问的是连续的，还有一种思路是考虑区间信息的合并，即一个区间的最长连续段，要么在左区间，要么在右区间，要么是左区间的后缀和右区间的前缀合并起来。与此相关的其他信息（区间最长连续 \(1\)的前缀、后缀长度、是否全是\(1\)，这些信息都可以合并），因此可以用线段树维护区间的上述信息，对于每个区间答案，合并\(\log\)次区间信息即可得到。

考虑修改，事实上就是把\(1\)看成 \(0\)， \(0\)看成 \(1\)。因此我们分别对 \(0,1\)这两个数维护上述信息，修改时交换一下这两个信息即可。

神奇的代码

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

const int N = 5e5 + 8;

class segment {
#define lson root << 1
#define rson root << 1 | 1

    struct node {
        struct info {
            int ans, l, r;
            bool all;
        } _info[2];
        bool flip;

        node operator+(const node& o) {
            node ret;
            ret.flip = 0;
            for (int i = 0; i < 2; ++i) {
                const auto &L = _info[i], R = o._info[i];
                ret._info[i].ans = max({L.ans, R.ans, L.r + R.l});
                ret._info[i].l = L.l;
                ret._info[i].r = R.r;
                if (L.all)
                    ret._info[i].l = L.l + R.l;
                if (R.all)
                    ret._info[i].r = L.r + R.r;
                ret._info[i].all = (L.all && R.all);
            }
            return ret;
        }

        void swap_info() { swap(_info[0], _info[1]); }

        int ans() { return _info[1].ans; }
    } a[N << 2];

  public:
    void build(int root, int l, int r, const string& s) {
        if (l == r) {
            a[root].flip = 0;
            for (int i = 0; i < 2; ++i) {
                auto& info = a[root]._info[i];
                info.l = info.r = info.all = info.ans = (s[l - 1] == '0' + i);
            }
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid, s);
        build(rson, mid + 1, r, s);
        a[root] = a[lson] + a[rson];
    }

    void pushdown(int root) {
        if (a[root].flip) {
            a[lson].flip ^= 1;
            a[lson].swap_info();
            a[rson].flip ^= 1;
            a[rson].swap_info();
            a[root].flip = 0;
        }
    }

    void update(int root, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            a[root].flip ^= 1;
            a[root].swap_info();
            return;
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        if (ll <= mid)
            update(lson, l, mid, ll, rr);
        if (rr > mid)
            update(rson, mid + 1, r, ll, rr);
        a[root] = a[lson] + a[rson];
    }

    node query(int root, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            return a[root];
        }
        pushdown(root);
        int mid = (l + r) >> 1;
        node L, R;
        if (ll <= mid)
            L = query(lson, l, mid, ll, rr);
        if (rr > mid)
            R = query(rson, mid + 1, r, ll, rr);
        if (ll > mid)
            return R;
        else if (rr <= mid)
            return L;
        else
            return L + R;
    }
} seg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    seg.build(1, 1, n, s);
    while (q--) {
        int c, l, r;
        cin >> c >> l >> r;
        if (c == 1) {
            seg.update(1, 1, n, l, r);
        } else {
            auto ans = seg.query(1, 1, n, l, r);
            cout << ans.ans() << '\n';
        }
    }

    return 0;
}

G - Two Kinds of Base (abc322 G)

题目大意

<++>

解题思路

<++>

神奇的代码