ABC380(A-G)

A - 123233 ¶

题目大意

给你一个 \(6\) 位数 \(N\)，判断 \(N\) 是否满足以下所有条件：

在 \(N\) 的数位中，\(1\) 恰好出现了 \(1\) 次。
在 \(N\) 的数位中，\(2\) 恰好出现了 \(2\) 次。
在 \(N\) 的数位中，\(3\) 恰好出现了 \(3\) 次。

参考代码

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string n;
    cin >> n;
    vector<int> cnt(10);
    for(auto ch : n)
        cnt[ch - '0']++;
    if(cnt[1] == 1 && cnt[2] == 2 && cnt[3] == 3)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

B - Hurdle Parsing ¶

题目大意

有一个长度为 \(N\) 的序列 \(A = (A_1, A_2, ..., A_N)\)，某人根据序列 \(A\) 生成了一个字符串 \(S\)，生成的规则如下：

初始的时候，\(S\) 只有一个字符 |
接下来，对于每个 \(i = 1, 2, ..., N\)，执行以下操作：
- 在 \(S\) 的末尾添加 \(A_i\) 个 -
- 然后，在 \(S\) 的末尾添加一个 |

现在，给你一个生成后的字符串 \(S\)，你需要将其还原成序列 \(A\)。

参考代码

C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int cnt = 0;
    for(int i = 1; i < n; i++)
    {
        if(s[i] == '|')
        {
            cout << cnt << ' ';
            cnt = 0;
        }
        else
            cnt++;
    }
    return 0;
}

给你一个长度为 \(N(1 \le N \le 5 \times 10 ^ 5)\) 的字符串 \(S\)，\(S\) 由 0 和 1 组成。多个连续的 1 组成 1-block，例如 010011100011001 字符串一共有 \(4\) 个 1-block，即 0[1]00[111]000[11]00[1]（此处中括号 [] 仅仅是用来标记每个 1-block ）。

给你一个数字 \(K(2 \le K)\)，你需要将第 \(K\) 个 1-block，挪到第 \(K-1\) 个 1-block 的后面，其他位置保持不变。输入数据保证字符串 \(S\) 一定有至少 \(K\) 个 1-block。输出挪动后的字符串 \(S\)

参考代码

C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int i = 0, cnt = 0;
    while(cnt < k - 1)
    {
        if(s[i] == '1')
        {
            while(s[i] == '1')
                i++;
            cnt++;
        }
        else
            i++;
    }
    for(int j = i; j < n; j++)
    {
        if(s[j] == '1')
        {
            while(j < n && s[j] == '1')
            {
                s[i++] = '1';
                j++;
            }
            while(i < j)
                s[i++] = '0';
            break;
        }
    }
    cout << s << endl;
    return 0;
}

D - Strange Mirroring ¶

题目大意

给你一个字符串 \(S(1 \le |S| \le 2 \times 10 ^ 5)\)，\(S\) 由小写字母组成。

你需要在 \(S\) 上执行以下操作 \(10^{100}\) 次：

首先，创建一份字符串 \(S\) 的拷贝 \(T\)，即令 \(T = S\)，然后将 \(T\) 的所有大写字母变小写，所有小写字母变大写。
然后，令 \(S = S + T\)，其中 \(+\) 表示将两个字符串拼接。

在执行完操作后，回答 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个询问，每个询问给你一个 \(K_i(1 \le K_i \le 10 ^ {18})\)，你需要回答 \(S\) 的第 \(K_i\) 个字符是什么。

解题思路

每一次操作会让 \(S\) 的长度翻倍，所以长度一定是形如 \(2^j|S|\) 的，因为 \(K_i \le 10 ^ {18}\)，可以处理出这个范围内所有可能的长度，即 \(p[j]\) 表示操作 \(j\) 次后 \(S\) 的长度。

对于一个 \(K_i\)，一定存在一个最大的 \(j\) 使得 \(p[j] \le K_i\)，则 \(K_i\) 相当于是在后半段的上，对应前半段 \(K_i - p[j]\) 位置大小写反转后字符，按这个流程处理下去直到 \(K_i \le |S|\) 即可。

参考代码

C++

#include <cctype>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    string s;
    cin >> s;
    LL n = s.size();
    int q;
    cin >> q;
    vector<LL> p;
    for(LL x = n; x < 1E18; x <<= 1)
        p.push_back(x);
    int len = p.size();
    while (q--)
    {
        LL k;
        cin >> k;
        k--;
        bool flag = false;
        for(int i = len - 1; i >= 0; i--)
            if(k >= p[i])
            {
                flag = !flag;
                k -= p[i];
            }
        char ans = s[k];
        if(flag)
            ans = islower(ans) ? toupper(ans) : tolower(ans);
        cout << ans << ' ';
    }
    return 0;
}

E - 1D Bucket Tool ¶

题目大意

有 \(N(1 \le 5 \times 10 ^ 5)\) 个格子，第 \(i\) 个格子的初始颜色是 \(i\)。两个格子如果位置相邻且颜色相同的则连通。

给你 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个询问，询问有两种类型：

1 x c：将第 \(x\) 个格子所在的连通块都染成颜色 \(c\)。
2 c: 查询颜色是 \(c\) 的格子的数量。

解题思路

因为染色是一块一块染的，所以显然应该用并查集维护。至于操作 2，再开一个哈希表记录每种颜色的数量就好。

参考代码

C++

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

class DSU
{
public:
    explicit DSU(int n) : parent_or_size(n+1, -1), left(n+1), right(n+1), color(n+1)
    {
        for (int i = 0; i <= n; i++)
            left[i] = right[i] = color[i] = i;
    }

    void merge(int a, int b)
    {
        int x = leader(a), y = leader(b);
        if (x == y)
            return;
        if (-parent_or_size[x] < -parent_or_size[y])
            std::swap(x, y);
        left[x] = min(left[x], left[y]);
        right[x] = max(right[x], right[y]);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
    }

    int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }

    bool same(int a, int b) { return leader(a) == leader(b); }

    int size(int a) { return -parent_or_size[leader(a)]; }

    int get_left(int a) { return left[leader(a)]; }
    int get_right(int a) { return right[leader(a)]; }
    int get_color(int a) { return color[leader(a)]; }
    void set_color(int a, int c) { color[leader(a)] = c; }

private:
    vector<int> parent_or_size;
    vector<int> left, right, color;
};

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> cnt(n + 1, 1);
    DSU dsu(n);
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, c;
            cin >> x >> c;
            x = dsu.leader(x);
            int s = dsu.size(x);
            cnt[dsu.get_color(x)] -= s;
            cnt[c] += s;
            dsu.set_color(x, c);
            int l = dsu.get_left(x);
            int r = dsu.get_right(x);
            if (l - 1 && dsu.get_color(l - 1) == c)
                dsu.merge(l - 1, x);
            if (r + 1 <= n && dsu.get_color(r + 1) == c)
                dsu.merge(r + 1, x);
        }
        else
        {
            int c;
            cin >> c;
            cout << cnt[c] << endl;
        }
    }
    return 0;
}

F - Exchange Game ¶

题目大意

Takahashi 和 Aoki 在玩一个卡牌游戏，初始的时候，Takahashi 手上有 \(N\) 张牌，Aoki 手上有 \(M\) 张牌，桌子上有 \(L\) 张牌。其中 \(1 \le N + M + L \le 12\)，每一张卡牌上都写了一个 \([1, 10^9]\) 范围内的数字。

双方轮流行动，由 Takahashi 先手，轮到某人行动时，执行以下操作：

从手中挑选任意一张牌打出，设打出的牌数字是 \(X\)，然后，可以从桌子上拿一张数字小于 \(X\) 的牌，加入到自己的手牌中。

双方都知道对方的手牌有哪些，也知道桌子上有哪些牌。问：谁是必胜方？

解题思路

显然是一个简单博弈论套 DP，考虑如何编码。首先将所有牌排序之后离散化，最多 \(12\) 张牌，如果记录每一张牌当前属于谁，一共有 \(3\) 种状态，需要 \(2\) 个 bit，状态数就是 \(4^{12} = 2^{24}\) 个。如果记录每个人有哪些牌，还需要额外引入一些 bit 记录每个人手牌区的大小，状态数要多一些，所以用前一种方法就好。

参考代码

C++

#include <functional>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>

using namespace std;

int main()
{
    int n, m, l;
    cin >> n >> m >> l;
    int len = n + m + l;
    vector<int> a(n), b(m), c(l);
    vector<int> x;
    map<int, vector<int>, greater<int>> mp;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        mp[a[i]].push_back(0);
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
        mp[b[i]].push_back(1);
    }
    for (int i = 0; i < l; i++)
    {
        cin >> c[i];
        mp[c[i]].push_back(2);
    }
    int idx = 0, s = 0;
    vector<vector<bool>> greater(len, vector<bool>(len));
    for (auto [x, v] : mp)
    {
        int k = idx;
        for (auto i : v)
        {
            for (int j = 0; j < k; j++)
                greater[idx][j] = true;
            idx++;
            s = s << 2 | i;
        }
    }
    unordered_map<int, bool> dp[2];

    auto get_state = [](int s, int i) -> int
    { return s >> (2 * i) & 0b11; };

    auto set_state = [](int s, int i, int x) -> int
    { return (s & ~(0b11 << (2 * i))) | (x << (2 * i)); };

    auto DP = [&dp, &greater, &get_state, &set_state, len](auto &self, int player, int s) -> bool
    {
        auto it = dp[player].find(s);
        if (it != dp[player].end())
            return it->second;
        bool win = false;
        for (int i = 0; i < len; i++)
        {
            int belong = get_state(s, i);
            if (belong != player)
                continue;
            int ns = set_state(s, i, 2);
            if(!self(self, player ^ 1, ns))
            {
                win = true;
                break;
            }
            for(int j = 0; j < i; j++)
            {
                if(!greater[i][j])
                    break;
                if(get_state(s, j) == 2 && !self(self, player ^ 1, set_state(ns, j, player)))
                {
                    win = true;
                    break;
                }
            }
        }
        dp[player][s] = win;
        return win;
    };
    cout << (DP(DP, 0, s) ? "Takahashi" : "Aoki") << endl;
    return 0;
}

G - Another Shuffle Window ¶

题目大意

给你一个 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的排列 \(P = (P_1, P_2, ..., P_N)\) 和一个整数 \(K(1 \le K \le N)\)，你将执行一次以下操作：

首先，等概率的从 \([1, N-K+1]\) 中随机选择一个数字 \(i\)。
然后，将 \(P_i, P_{i+1}, ..., P_{i+K-1}\) 随机打乱顺序。

问：在操作一次之后，排列 \(P\) 的逆序对的数学期望是多少？答案对 \(998244353\) 取模。

解题思路

首先需要推一个小结论：对于一个长度为 \(K\) 且任意两个数字都不相同的序列，将其随机打乱之后，逆序对数的数学期望是 \(\frac{K(K-1)}{4}\)。

证明：长度为 \(K\) 的序列一共有 \(\frac{K(K-1)}{2}\) 对数，对于任意的数对，要么前者大于后者，要么后者大于前者，两者概率相等，因此逆序对数的数学期望是 \(\frac{K(K-1)}{4}\)。

下面需要将序列进行切分，对于 \(i = a\)，我们可以将序列分成 \([1, a-1], [a, a+K-1], [a+K, N]\) 三段

下面称 \([1, a-1]\) 为 \(X\) 段，\([a, a+K-1]\) 为 \(Y\) 段，\([a+K, N]\) 为 \(Z\) 段。一共有 6 处位置会产生逆序对：

\(X\) 内部的逆序对。
\(Y\) 内部的逆序对。
\(Z\) 内部的逆序对。
\(X\) 和 \(Y\) 产生的逆序对。
\(X\) 和 \(Z\) 产生的逆序对。
\(Y\) 和 \(Z\) 产生的逆序对。

假设 \(i = a\) 位置的逆序对已经求出，考虑从 \(i = a\) 如何转移到 \(i = a+1\)，这涉及到两个元素归属的变化，首先 \(P_a\) 脱离 \(Y\) 加入 \(X\)，然后 \(P_{a+K}\) 脱离 \(Z\) 加入 \(Y\)。

首先可以发现，对于逆序对 2（ \(Y\) 内部）来说，一加一减不会影响序列的大小，又因为 \(Y\) 会再打乱一次，所以根据刚刚推理的结论，\(Y\) 内部的逆序对的数学期望始终不变，即 \(\frac{K(K-1)}{4}\)。

对于其他情况，我们将转移切分成四个事件：\(P_a\) 脱离 \(Y\)，\(P_a\) 加入 \(X\)，\(P_{a+K}\) 脱离 \(Z\)，\(P_{a+K}\) 加入 \(Y\)，开始分类讨论：

\(P_a\) 脱离 \(Y\)，除了逆序对 2（\(Y\) 内部）已经固定之外，还会影响逆序对 4（\(X\) 和 \(Y\)）和逆序对 6（\(Y\) 和 \(Z\)），我们需要减去 \(P_a\) 的贡献。对于逆序对 4，需要减掉 \(X\) 中比 \(P_a\) 大的数字的数量；对于逆序对 6，需要减掉 \(Z\) 中比 \(P_a\) 小的数字的数量。
\(P_a\) 加入 \(X\)，会影响逆序对 1（\(X\) 内部）、4（\(X\) 和 \(Y\)）、5（\(X\) 和 \(Z\)），我们需要加上 \(P_a\) 的贡献。对于逆序对 1 ，需要加上 \(X\) 中比 \(P_a\) 大的数字的数量，这可以和 \(P_a\) 脱离 \(Y\) 中减掉的部分抵消；对于逆序对 4，需要加上 \(Y\) 中比 \(P_a\) 小的数字的数量；对于逆序对 5，需要加上 \(Z\) 中比 \(P_a\) 小的数字的数量，这也可以和 \(P_a\) 脱离 \(Y\) 中减掉的部分抵消。
\(P_{a+K}\) 脱离 \(Z\)，会影响逆序对 3（\(Z\) 内部）、5（\(X\) 和 \(Z\)）、6（\(Y\) 和 \(Z\)），我们需要减去 \(P_{a+K}\) 的贡献。对于逆序对 3 ，需要减掉 \(Z\) 中比 \(P_{a+K}\) 小的数字的数量；对于逆序对 5，需要减掉 \(X\) 中比 \(P_{a+K}\) 大的数字的数量；对于逆序对 6，需要减掉 \(Y\) 中比 \(P_{a+K}\) 大的数字的数量。
\(P_{a+K}\) 加入 \(Y\)，除了逆序对 2（\(Y\) 内部）已经固定之外，还会影响逆序对 4（\(X\) 和 \(Y\)）和逆序对 6（\(Y\) 和 \(Z\)）。对于逆序对 4，需要加上 \(X\) 中比 \(P_{a+K}\) 大的数字的数量，这可以和 \(P_{a+K}\) 脱离 \(Z\) 中减掉的部分抵消；对于逆序对 6，需要加上 \(Z\) 中比 \(P_{a+K}\) 小的数字的数量，这可以和 \(P_{a+K}\) 脱离 \(Z\) 中减掉的部分抵消；

综上，1 和 2 抵消了一部分，但还需要加上 \(Y\) 中比 \(P_a\) 小的数字的数量，减掉 \(Y\) 中比 \(P_{a+K}\) 大的数字的数量。因此只需要针对 \(Y\) 的部分维护一个树状数组即可。此外，初始的时候，需要求一次 \(i = 1\) 的答案，所以还需要求一遍逆序对 3 和逆序对 6，所以还需要求出 \(Z\) 的树状数组。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

const LL MOD = 998244353;

struct FenwickTree
{
    int n;
    vector<int> t;

    FenwickTree(int n) : n(n), t(n + 1) {}

    int lowbit(int x) const { return x & -x; }

    int prefix(int x) const
    {
        int sum = 0;
        for (; x; x -= lowbit(x))
            sum += t[x];
        return sum;
    }

    int query(int l, int r) const { return prefix(r) - prefix(l - 1); }

    void add(int x, int k)
    {
        for (; x <= n; x += lowbit(x))
            t[x] += k;
    }
};

pair<LL, LL> exgcd(LL a, LL b)
{
    if (b == 0)
        return {1, 0};
    auto [x, y] = exgcd(b, a % b);
    return {y, x - a / b * y};
}

LL inv(LL a)
{
    auto [x, y] = exgcd(a, MOD);
    return (x + MOD) % MOD;
}

int main()
{
    int n;
    LL k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        cin >> p[i];
    FenwickTree mid(n), suf(n);
    LL sum = 0;
    for (int i = 0; i < k - 1; i++)
        mid.add(p[i], 1);
    for (int i = k - 1; i < n; i++)
    {
        sum += suf.query(p[i] + 1, n);
        sum += mid.query(p[i] + 1, n);
        suf.add(p[i], 1);
    }
    LL fix_cnt = k * (k - 1) % MOD * inv(4) % MOD;
    LL frac = inv(n - k + 1);
    LL ans = 0;
    for (int i = 0, j = k - 1; j < n; i++, j++)
    {
        sum -= mid.query(p[j]+1, n);
        mid.add(p[j], 1);
        ans = (ans + fix_cnt + sum) % MOD;
        sum += mid.query(1, p[i]-1);
        mid.add(p[i], -1);
    }
    ans = ans * frac % MOD;
    cout << ans << endl;
    return 0;
}

最后更新: 2024-12-28
创建日期: 2024-12-28

ABC380(A-G)

A - 123233¶

B - Hurdle Parsing¶

C - Move Segment¶

D - Strange Mirroring¶

E - 1D Bucket Tool¶

F - Exchange Game¶

G - Another Shuffle Window¶

A - 123233 ¶

B - Hurdle Parsing ¶

C - Move Segment ¶

D - Strange Mirroring ¶

E - 1D Bucket Tool ¶

F - Exchange Game ¶

G - Another Shuffle Window ¶