AtCoder Beginner Contest 341

A - Print 341 (abc341 A)

题目大意

给定\(n\),输出 \(n\)\(0\)\(n+1\)\(1\)交替的字符串。

解题思路

\(101010...\)循环输出即可。

神奇的代码
n = input()
s = "10" * int(n) + "1"
print(s)


B - Foreign Exchange (abc341 B)

题目大意

货币兑换。

\(A\)国货币每 \(x_a\)钱可兑换 \(B\)国货币 \(y_a\)钱。
\(B\)国货币每 \(x_b\)钱可兑换 \(C\)国货币 \(y_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);
    int n;
    cin >> n;
    vector<LL> a(n);
    for (auto& x : a)
        cin >> x;
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        a[i + 1] += a[i] / x * y;
    }
    cout << a[n - 1] << '\n';

    return 0;
}



C - Takahashi Gets Lost (abc341 C)

题目大意

二维平面\(H \times W\),有.#。其中#不能占人。

给定一个操作序列\(T\)

问高桥的初始位置的数量,使得进过上述操作序列,不会经过#

解题思路

枚举位置,然后模拟操作序列判断是否经过#,时间复杂度为\(O(HW|T|)\),为 \(O(500^3)\),可过。

神奇的代码
#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 h, w, n;
    cin >> h >> w >> n;
    string t;
    cin >> t;
    vector<string> s(h);
    for (auto& i : s)
        cin >> i;
    int ans = 0;
    auto land = [&](int x, int y) {
        return 0 <= x && x < h && 0 <= y && y < w && s[x][y] != '#';
    };
    auto ok = [&](int x, int y) {
        if (!land(x, y))
            return false;
        int nx, ny;
        for (auto& i : t) {
            if (i == 'L') {
                nx = x;
                ny = y - 1;
            } else if (i == 'R') {
                nx = x;
                ny = y + 1;
            } else if (i == 'U') {
                nx = x - 1;
                ny = y;
            } else if (i == 'D') {
                nx = x + 1;
                ny = y;
            }
            if (!land(nx, ny))
                return false;
            x = nx;
            y = ny;
        }
        return true;
    };
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (ok(i, j))
                ++ans;
        }
    }
    cout << ans << '\n';

    return 0;
}



D - Only one of two (abc341 D)

题目大意

给定\(n,m,k\),问从只被n或m整除的数中找出第 \(k\)小的数,

解题思路

为方便考虑,可先简化问题,即假设\(n,m\)互质。

注意到我们找出来的数是形如 \(xn\)\(xm\), 我们考虑枚举这个\(x\)

显然枚举出的\(xn\)其是第几个数具有单调性,因此我们可以二分枚举这个 \(x\)

先考虑\(xn\)的形式,我们要判断 \(xn\)是第几小的数。

注意到只被n或m整除的数都是形如\(yn,ym\)的。

在形如\(yn\)类别的数中,\(xn\)的排名是 \(x-cost1\),其中 \(cost1\)\(yn \% m = 0\)\(y\)的数量,其中\(y \in [1, x]\)。有多少呢?因为上述假设了\(n,m\)互质,那么\(yn \% m = 0\)当且仅当 \(y \% m = 0\),即\(cost1 = \frac{x}{m}\)

在形如\(ym\)类别的数中,\(xn\)的排名是 \(\frac{xn}{m} - cost2\),其中 \(cost2\)\(ym \% n = 0\)\(y\)的数量,其中\(y \in [1, \frac{xn}{m}],\)有多少呢?因为上述假设了\(n,m\)互质,那么\(ym \% n = 0\)当且仅当 \(y \% n = 0\),即\(cost2 = \frac{xn / m}{n}\)

上述的除法均为整除。

那最终\(xn\)的排名就是两类别中排名的相加,即为\(x - cost1 + \frac{xn}{m} - cost2\)。与 \(k\)比较,就可以得知该 \(x\)是偏大了还是偏小了,可以二分了。

上述是假设了 \(n,m\)互质,而如果不互质时,会变得就只有 \(cost1\)\(cost2\)。假设 \(n^\prime = \frac{n}{gcd(n,m)}, m^\prime = \frac{m}{gcd(n,m)}\)。考虑 \(cost1\)如何算。

\(cost1\)\(y gcd(n,m) n^\prime \% gcd(n,m) m^\prime = 0\)\(y\)的数量,由于 \(n^\prime\)\(m^\prime\)互质,那其数量就等价于 \(y \% m^\prime = 0\)\(y\)的数量。 即\(cost1 = \frac{x}{m^\prime}\)

同理也可以求的 \(cost2 = \frac{xn / m}{n^\prime}\)

如此就可以二分求出第\(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, m;
    LL k;
    cin >> n >> m >> k;
    if (n > m)
        swap(n, m);
    int gg = gcd(n, m);
    LL ans = -1;
    auto calc = [&](LL n, LL m, __int128 a) {
        __int128 ldi = n / gg;
        __int128 rdi = m / gg;
        __int128 lcnt = a;
        __int128 rcnt = a * n / m;
        __int128 cnt = lcnt - (lcnt / rdi) + rcnt - (rcnt / ldi);
        return cnt;
    };
    auto solve = [&](int n, int m) {
        __int128 l = 0, r = 1e18;
        while (l + 1 < r) {
            __int128 mid = (l + r) / 2;
            __int128 rank = calc(n, m, mid);
            if (rank >= k)
                r = mid;
            else
                l = mid;
        }
        if (calc(n, m, r) == k && r * n % m != 0) {
            ans = r * n;
        }
    };
    solve(n, m);
    solve(m, n);
    cout << ans << '\n';

    return 0;
}



E - Alternating String (abc341 E)

题目大意

给定一个\(01\)\(s\),进行以下两种操作:

  • 1 l r,将\(s[l,r]\)\(01\)翻转
  • 2 l r,问\(s[l,r]\)是否是\(01\)交替的。

解题思路

一个串是\(01\)交替的,就是每一位与下一位的值都不同。

考虑数组 \(x[i]=(s[i] != s[i + 1])\) ,如果\(\sum_{i=l}^{r-1}x[i] == r - l\),那说明 \(s[l,r]\)\(01\)交替的。

注意到操作一对该数组的影响仅仅是两个单点修改,而操作二是一个区间查询,用树状数组或线段树维护数组\(x\)即可。

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

// starting from 0
template <typename T> class fenwick {
  public:
    vector<T> fenw;
    int n;

    fenwick(int _n) : n(_n) { fenw.resize(n); }

    void modify(int x, T v) {
        while (x < n) {
            fenw[x] += v;
            x |= (x + 1);
        }
    }

    T get(int x) {
        T v{};
        while (x >= 0) {
            v += fenw[x];
            x = (x & (x + 1)) - 1;
        }
        return v;
    }
    T sum(int l, int r) {
        T tot = get(r);
        if (l != 0) {
            tot -= get(l - 1);
        }
        return tot;
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    fenwick<int> sum(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        sum.modify(i, s[i] != s[i + 1]);
    }
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            --l, --r;
            if (l != 0) {
                sum.modify(l - 1, sum.sum(l - 1, l - 1) == 1 ? -1 : 1);
            }
            if (r != n - 1) {
                sum.modify(r, sum.sum(r, r) == 1 ? -1 : 1);
            }
        } else {
            int l, r;
            cin >> l >> r;
            --l, --r;
            if (sum.sum(l, r - 1) == r - l)
                cout << "Yes" << '\n';
            else
                cout << "No" << '\n';
        }
    }

    return 0;
}



F - Breakdown (abc341 F)

题目大意

给定一张无向图,点有点权\(w_i\)。一开始有些点有一些碎片\(a_i\)

问进行的操作的最大次数。

操作为,选择一个有碎片的点\(x\),拿走碎片,并从其邻居中选择一些点,满足\(\sum w_y < w_x\),在每一个点放一个碎片。

解题思路

注意到操作里,碎片总是往点权小的点跑,这里有个方向性。我们可以先求权值小的点,那考虑权值大的点时,其考虑放置碎片的点的答案都求出来了,因此可以求出该点的答案。考虑\(dp\)

按点权小到大的顺序求解,假设\(dp[i]\)表示点\(i\)有一个碎片带来的最大操作次数,那考虑求解当前点\(dp[i]\)时,就是考虑其 \(w_y < w_i\)的所有 \(y\)选哪些 \(y\),其 \(\sum dp[y]\)最大,且 \(sum w_y < w_i\),其中这个 \(dp[y]\)已经求出来了。

注意到上述的问题就是一个\(01\)背包问题,因此就按照点权小到大的顺序求解 \(n\)\(01\)背包问题即可。

最后答案就是\(\sum dp[i] \times a[i]\)

考虑其时间复杂度,每次 \(01\)背包的复杂度是 \(O(nw)\),乍一看以为是 \(O(n^2w)\),但考虑到每次 \(01\)背包中的 \(O(n)\)是邻居数量,所有的 \(01\)背包的邻居数量的和其实是和 \(O(m)\)同数量级的,因此总的时间复杂度是 \(O(mw)\)

神奇的代码
#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<vector<int>> edge(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int> w(n);
    for (auto& x : w)
        cin >> x;
    int up = *max_element(w.begin(), w.end());
    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 x, int y) { return w[x] < w[y]; });
    vector<int> cost(n);
    LL ans = 0;
    for (auto i : id) {
        vector<array<int, 2>> goods;
        for (auto j : edge[i]) {
            if (w[j] < w[i])
                goods.push_back({w[j], cost[j]});
        }
        if (goods.empty()) {
            cost[i] = 1;
        } else {
            vector<int> dp(w[i], 0);
            for (auto& [x, y] : goods) {
                for (int j = w[i] - 1; j >= x; j--) {
                    dp[j] = max(dp[j], dp[j - x] + y);
                }
            }
            cost[i] = 1 + *max_element(dp.begin(), dp.end());
        }
        ans += 1ll * a[i] * cost[i];
    }
    cout << ans << '\n';

    return 0;
}



G - Highest Ratio (abc341 G)

题目大意

给定一个数组,对于每一个左端点\(l\),求右端点\(r\),其\([l,r]\)的平均值最大。

解题思路

<++>

神奇的代码



热门相关:明朝好丈夫   名门贵妻:暴君小心点   明朝败家子   虎狼之师   花都保镖