Atcoder ABC432游记

题目

A - Permute to Maximize

题目描述

给你介于 $1$ 和 $9$ 之间的三个数字 $A,B,C$ 。

求将 $A,B,C$ 按任意顺序排列并连接而成的所有 $3$ 个整数中的最大值。

思路

语法题

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if (s[0] == '0') {
        for (int i = 1; i < s.length(); i++) {
            if (s[i] != '0') {
                swap(s[0], s[i]);
                break;
            }
        }
    }
    cout << s;
    return 0;
}

---

B.Permute to Minimize

题目描述

给你一个正整数 $X$ 。

将 $X$ （不含前导零）的十进制表示中出现的数字重新排列**，使其没有前导零**，求所有正整数中的最小值。

思路

语法题

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if (s[0] == '0') {
        for (int i = 1; i < s.length(); i++) {
            if (s[i] != '0') {
                swap(s[0], s[i]);
                break;
            }
        }
    }
    cout << s;
    return 0;
}

---

C.Candy Tribulation

题目描述

你有无限量的两种糖果：小糖果和大糖果。小糖果的重量是 $X$ 克，大糖果的重量是 $Y$ 克。大糖果比小糖果重（即 $X < Y$ ）。

有 $N$ 个孩子，编号为 $1$ 至 $N$ 。

你决定分发糖果，以满足以下条件：

• 对于 $i=1,\dots,N$ 来说， $i$ 个孩子收到的两种糖果的总重量正好是 $A_i$ 。
• 分给 $N$ 个孩子的糖果的总重量都相等。

判断是否存在满足条件的分配方法。如果存在，求大号糖果分配数量的最大可能值。

思路

使劲猜结论！

第 $i$ 个孩子分别获得$x_i, y_i$个糖果，$x_i + y_i = A_i$

把$x_i$换掉得：

$$(A_i - y_i) \cdot X + y_i \cdot Y = W$$

整理得：$A_i \cdot X + y_i \cdot (Y - X) = W$

所以$\displaystyle y_i = \frac{W - A_i \cdot X}{Y - X}$

为了使 $y_i \in \mathbb{N}$，要满足：

• $W - A_i \cdot X \geq 0$ 且是$(Y-X)$的倍数
• $0 \leq y_i \leq A_i$

由于所有孩子获得的总重量 $W$ 相同所以
$W - A_i \cdot X \equiv 0 \pmod{Y-X}$

即$A_i \cdot X \equiv W \pmod{Y-X}$

所以$A_i$ 模 $\gcd(X, Y-X)$ 必须同余，直接判完然后无脑贪心即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int x, y, n;
    cin >> n >> x >> y;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int d = __gcd(x, y - x);
    int m = (y - x) / d;
    for (int i = 1; i < n; i++) {
        if (a[i] % m != a[0] % m) {
            cout << -1;
            return 0;
        }
    }
    int ww = *min_element(a.begin(), a.end(), [&](int a1, int a2) {
        return a1 * y < a2 * y;
    }) * y;
    int w = ww - ((ww - x * a[0]) % (y - x));
    if (w < x * a[0]) {
        w += y - x;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int tp = w - x * a[i];
        if (tp % (y - x)) {
            cout << -1;
            return 0;
        }
        int l = tp / (y - x);
        if (l < 0 || l > a[i]) {
            cout << -1;
            return 0;
        }
        ans += l;
    }
    cout << ans;
    return 0;
}

---

D.Suddenly, A Tempest

题目描述

有一个无限大的二维网格。如果 $0 \leq x \leq X-1$ 和 $0 \leq y \leq Y-1$ 单元格 $(x,y)$ 的颜色为黑色，否则为白色。

$N$ 大风暴在这个网格上依次出现。 $i$ 次大风暴会根据字符 $C_i$ 和整数 $A_i, B_i$ 表示的规则更新网格中每个单元格的颜色。

在 $i$ -th大风暴中， $(x, y)$ 单元格在大风暴之后的颜色是：

• 如果 $C_i$ 是 X、
  • 如果 $x < A_i$ ，它就会变成大风暴前 $(x, y + B_i)$ 单元格的颜色；
  • 如果 $x \geq A_i$ 为 “X”，则在大风暴来临之前，它变成 $(x, y - B_i)$ 单元格的颜色。
• 如果 $C_i$ 是 “Y”、
  • 如果 $y < A_i$ ，它将成为大风暴前 $(x + B_i, y)$ 单元格的颜色；
  • 如果 $y \geq A_i$ 为 “Y”，则在大风暴来临之前，它变成了 $(x - B_i, y)$ 单元格的颜色。

当且仅当 $|x_1 - x_2| + |y_1 - y_2| = 1$ 时，两个黑色单元格 $(x_1, y_1), (x_2, y_2)$ 相邻。此外，两个黑色单元格 $c_1, c_2$ 是相连的，当且仅当可以通过重复移动到相邻的黑色单元格来从单元格 $c_1$ 移动到单元格 $c_2$ 时。

当且仅当 $S$ 满足以下条件时，一个非空的黑色单元格集合 $S$ 才是一个相连的单元格：

• $S$ 中的任意两个单元格都是相连的。
• 不发生了所有 $N$ 大风暴后的网格，请找出连接部分的数量，并按升序**输出每个连接部分中的单元格数量。

思路

不想写了 暴力1ms跑完了

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
    int x1, x2, x3, x4;
    node(int _x1, int _x2, int _y1, int _y2) : x1(_x1), x2(_x2), x3(_y1), x4(_y2) {}
};
bool ch(int a1, int a2, int b1, int b2)
{
    return max(a1, b1) <= min(a2, b2);
}
bool check(node r1, node r2) {
    if (r1.x2 + 1 == r2.x1 || r2.x2 + 1 == r1.x1) {
        if (ch(r1.x3, r1.x4, r2.x3, r2.x4)) {
            return 1;
        }
    }
    if (r1.x4 + 1 == r2.x3 || r2.x4 + 1 == r1.x3) {
        if (ch(r1.x1, r1.x2, r2.x1, r2.x2)) {
            return 1;
        }
    }
    return 0;
}
signed main()
{
    int n, x, y;
    cin >> n >> x >> y;
    vector<pair<char, pair<int, int>>> v1;
    for (int i = 0; i < n; i++) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        v1.push_back({c, {a, b}});
    }
    vector<node> v2;
    v2.push_back({0, x - 1, 0, y - 1});
    for (int i = 0; i < v1.size(); i++) {
        char c = v1[i].first;
        int a = v1[i].second.first, b = v1[i].second.second;
        vector<node> tp;
        for (node r : v2) {
            if (c == 'X') {
                if (r.x1 <= min(r.x2, a - 1)) {
                    tp.push_back({r.x1, min(r.x2, a - 1), r.x3 - b, r.x4 - b});
                }
                if (max(r.x1, a) <= r.x2) {
                    tp.push_back({max(r.x1, a), r.x2, r.x3 + b, r.x4 + b});
                }
            } else {
                if (r.x3 <= min(r.x4, a - 1)) {
                    tp.push_back({r.x1 - b, r.x2 - b, r.x3, min(r.x4, a - 1)});
                }
                if (max(r.x3, a) <= r.x4) {
                    tp.push_back({r.x1 + b, r.x2 + b, max(r.x3, a), r.x4});
                }
            }
        }
        v2 = move(tp);
    }
    if (v2.empty()) {
        cout << 0;
        return 0;
    }
    vector<int> v3;
    for (int i = 0; i < v2.size(); i++) {
        int w = v2[i].x2 - v2[i].x1 + 1;
        int h = v2[i].x4 - v2[i].x3 + 1;
        v3.push_back(w * h);
    }
    vector<bool> vis(v2.size(), 0);
    vector<int> ans;
    for (int i = 0; i < v2.size(); i++) {
        if (!vis[i]) {
            stack<int> st;
            st.push(i);
            vis[i] = 1;
            int cnt = v3[i];
            while (!st.empty()) {
                int u = st.top();
                st.pop();
                for (int j = 0; j < v2.size(); j++) {
                    if (!vis[j] && check(v2[u], v2[j])) {
                        vis[j] = 1;
                        cnt += v3[j];
                        st.push(j);
                    }
                }
            }
            ans.push_back(cnt);
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

---

E.Clamp

题目描述

给你一个长度为 $N$ 的整数序列 $A=(A_1, A_2, \dots, A_N)$ 。

给你 $Q$ 个查询，你要按顺序处理这些查询。每个查询的格式如下：

• 1 x y ：将 $A_x$ 的值改为 $y$ 。
• 2 l r：查找 $\displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i))$ 的值。

思路

考虑贡献：

• $<l$ 的元素贡献 $l \times \text{cnt}$
• $>r$ 的元素贡献 $r \times \text{cnt}$
• $\in [l,r]$ 区间的元素贡献它自己

所以答案$= l \times \text{count}(A_i < l) + r \times \text{count}(A_i > r) + \text{sum}(l \leq A_i \leq r)$

用两个树状数组求小于等于$k$元素的和与个数即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct fenwick
{
    vector<int> tree;
    fenwick() : tree(555555, 0) {}
    void update(int x, int k) {
        int idx = x + 1;
        while (idx < 555555) {
            tree[idx] += k;
            idx += idx & (-idx);
        }
    }
    int query(int x) {
        if (x < 0) return 0;
        if (x > 555555) x = 555555;
        int idx = x + 1;
        int res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & (-idx);
        }
        return res;
    }
};
signed main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    fenwick bit1, bit2;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        bit1.update(a[i], 1);
        bit2.update(a[i], a[i]);
    }
    while (q--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int x, y;
            cin >> x >> y;
            x--;
            bit1.update(a[x], -1);
            bit2.update(a[x], -a[x]);
            a[x] = y;
            bit1.update(a[x], 1);
            bit2.update(a[x], a[x]);
        } else if (ch == 2) {
            int l, r;
            cin >> l >> r;
            if (l > r) {
                cout << n * l << '\n';
            } else {
                int q1 = bit1.query(l);
                int q2 = bit1.query(r - 1);
                int q3 = bit2.query(l);
                int q4 = bit2.query(r - 1);
                int ans = l * q1 + r * (n - q2) + (q4 - q3);
                cout << ans << '\n';
            }
        }
    }
    return 0;
}

G.Sum of Binom(A, B)

题目描述

给你两个长度分别为 $N,M$ 的整数序列 $A=(A_1, A_2, \dots, A_N)$ 和 $B=(B_1, B_2, \dots, B_M)$ 。

求 $\displaystyle \sum_{i=1}^N \sum_{j=1}^M \binom{A_i}{B_j}$ 对 $998244353$ 取模的结果。

思路

$$\sum_{i=1}^N \sum_{j=1}^M \binom{A_i}{B_j} = \sum_{i=1}^N \sum_{j=1}^M \frac{A_i!}{B_j!(A_i-B_j)!}$$

$$= \sum_{j=1}^M \frac{1}{B_j!} \sum_{i=1}^N \frac{A_i!}{(A_i-B_j)!}$$

令$cnt1[x]$ 表示序列 $A$ 中值为 $x$ 的元素个数，$cnt2[y]$ 表示序列 $B$ 中值为 $y$ 的元素个数。

即求：

$$\sum_{y=0}^{\max(B)} cnt2[y] \cdot \frac{1}{y!} \sum_{x=y}^{\max(A)} cnt1[x] \cdot \frac{x!}{(x-y)!}$$

设 $f[x] = cnt1[x] \cdot x!$，$g[y] = cnt2[y] \cdot \frac{1}{y!}$

即求：

$$\sum_{y=0}^{\max(B)} g[y] \sum_{x=y}^{\max(A)} f[x] \cdot \frac{1}{(x-y)!}$$

令 $h[z] = \frac{1}{z!}$

$$\sum_{x=y}^{\max(A)} f[x] \cdot h[x-y] = \sum_{i+j=x, i \geq y} f[i] \cdot h[j]$$

比C简单因为是套路

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int G = 3;
int fastpow(int a, int b, int m = mod) {
    int res = 1;
    while (b) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}
void change(vector<int> &a, int len) {
    for (int i = 1, j = len / 2; i < len - 1; i++) {
        if (i < j) swap(a[i], a[j]);
        int k = len / 2;
        while (j >= k) {
            j -= k;
            k /= 2;
        }
        if (j < k) {
            j += k;
        }
    }
}
void ntt(vector<int> &a, int len, int x) {
    change(a, len);
    for (int h = 2; h <= len; h <<= 1) {
        int omega = fastpow(G, (mod - 1) / h, mod);
        if (x == -1) {
            omega = fastpow(omega, mod - 2, mod);
        }
        for (int i = 0; i < len; i += h) {
            int w = 1;
            for (int j = i; j < i + h / 2; j++) {
                int u = a[j];
                int v = a[j + h / 2] * w % mod;
                a[j] = (u + v) % mod;
                a[j + h / 2] = (u - v + mod) % mod;
                w = (w * omega) % mod;
            }
        }
    }
    if (x == -1) {
        int inv = fastpow(len, mod - 2, mod);
        for (int i = 0; i < a.size(); i++) {
            a[i] = (a[i] * inv) % mod;
        }
    }
}
vector<int> convo(vector<int> a, vector<int> b) {
    if (a.empty() || b.empty()) {
        return {0};
    }
    int m = 1;
    int sz = a.size() + b.size() - 1;
    while (m < sz) {
        m <<= 1;
    }
    a.resize(m, 0);
    b.resize(m, 0);
    ntt(a, m, 1);
    ntt(b, m, 1);
    for (int i = 0; i < m; i++) {
        a[i] = a[i] * b[i] % mod;
    }
    ntt(a, m, -1);
    a.resize(sz);
    return a;
}
vector<int> fact(555555 + 1), invf(555555 + 1);
void init()
{
    fact[0] = 1;
    for (int i = 1; i <= 555555; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    invf[555555] = fastpow(fact[555555], mod - 2, mod);
    for (int i = 555555 - 1; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % mod;
    }
}
signed main()
{
    init();
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    vector<int> cnt1(555555 + 1, 0), cnt2(555555 + 1, 0);
    for (int i = 0; i < a.size(); i++) {
        cnt1[a[i]]++;
    }
    for (int i = 0; i < b.size(); i++) {
        cnt2[b[i]]++;
    }
    vector<int> g(555555 + 1, 0), h(555555 + 1, 0);
    for (int i = 0; i <= 555555; i++) {
        g[i] = cnt2[i] * invf[i] % mod;
        h[i] = invf[i];
    }
    auto gh = convo(g, h);
    if (gh.size() > 555555 + 1) {
        gh.resize(555555 + 1);
    }
    int ans = 0;
    for (int i = 0; i <= 555555; i++) {
        ans = (ans + (cnt1[i] * fact[i]) % mod * gh[i]) % mod;
    }
    cout << ans;
    return 0;
}

---

复盘

没有 哈哈哈