AtCoder Beginner Contest 432

T0mle · 2025-11-16 11:04:00 · 个人记录

顺序：ABCDEGF

本来想倒序开的，但 zzr 说要拉爆我于是正序。

A

可以排序简单写。

int a[4];

void solve() {
    cin >> a[1] >> a[2] >> a[3];
    sort(a + 1, a + 4);
    cout << a[3] << a[2] << a[1];
}

0:36

B

csp-j2025 T1 加强版。

先输出一个非 0 的数，然后按顺序输出。

string s;
int buc[11];

void solve() {
    cin >> s;
    for (auto c : s) buc[c ^ 48]++;
    rep(i, 1, 9) {
        if (buc[i]) {
            cout << i;
            buc[i]--;
            break;
        }
    }
    rep(i, 0, 9) {
        while (buc[i]--) cout << i;
    }
}

2:16

C

最唐的一次，在 C 题时间花时间最长。

猎奇思路：

假设每个人的唐总重量是 S，第 i 个人吃了 n 个小的和 m 个大的，有：

\begin{cases} n+m=a_i\\ nx+my=S \end{cases}

解得

\begin{cases} n=\frac{a_iy-S}{y-x}\\ m=\frac{S-a_ix}{y-x} \end{cases}

由于 n,m 都是非负整数，可得所有 a_ix\bmod (y-x) 和所有 a_iy\bmod (y-x) 需相等。对于 S 需要有 S\equiv a_ix\bmod (y-x),S\in[\max\{a_ix\},\min\{a_iy\}]。然后算一算。

脑子不清醒，28:01 过的。

void solve() {
    rd(n), rd(x), rd(y);
    int sm = 0;
    rep(i, 1, n) rd(a[i]), sm += a[i];
    int gl = 1ll * a[1] * x % (y - x), LB = 0, UB = 1e18;
    rep(i, 1, n) {
        if (1ll * a[i] * x % (y - x) != gl) { puts("-1"); return; }
        if (1ll * a[i] * y % (y - x) != gl) { puts("-1"); return; }
        ckmx(LB, 1ll * a[i] * x);
        ckmn(UB, 1ll * a[i] * y);
    }
    int mod = y - x, ans;
    if (UB % mod >= gl) ans = UB - (UB % mod - gl);
    else ans = UB - (UB % mod - gl + mod);
    // cout << LB << " " << UB << "  " << ans << endl;
    if (ans < LB) { puts("-1"); return; }
    ans *= n;
    wrt((ans - sm * x) / mod);
}

D

观后感：猎奇。

注意到 N\le14，我们可以维护一些矩形，每次操作后矩形数至多翻倍，最后有 2^N 个矩形，O(4^N) 枚举矩形对然后并查集合并。

写完 50:35，怎么已经过半了。

int n, x, y;
char c;
int a, b;
struct mat { int x1, y1, x2, y2; };
vector <mat> dat;
int dsu[1 << 14], siz[1 << 14];

int find(int k) { return k == dsu[k] ? k : dsu[k] = find(dsu[k]); }
void solve() {
    cin >> n >> x >> y;
    dat.pb({0, 0, x - 1, y - 1});
    while (n--) {
        cin >> c >> a >> b;
        int siz = dat.size();
        repr(i, 0, siz) {
            if (c == 'X') {
                if (dat[i].x2 < a) {
                    dat[i].y1 -= b, dat[i].y2 -= b;
                } else if (dat[i].x1 >= a) {
                    dat[i].y1 += b, dat[i].y2 += b;
                } else {
                    dat.pb({a, dat[i].y1 + b, dat[i].x2, dat[i].y2 + b});
                    dat[i] = {dat[i].x1, dat[i].y1 - b, a - 1, dat[i].y2 - b};
                }
            } else {
                if (dat[i].y2 < a) {
                    dat[i].x1 -= b, dat[i].x2 -= b;
                } else if (dat[i].y1 >= a) {
                    dat[i].x1 += b, dat[i].x2 += b;
                } else {
                    dat.pb({dat[i].x1 + b, a, dat[i].x2 + b, dat[i].y2});
                    dat[i] = {dat[i].x1 - b, dat[i].y1, dat[i].x2 - b, a - 1};
                }
            }
        }
    }
    int n = dat.size();

    repr(i, 0, n) dsu[i] = i, siz[i] = (dat[i].x2 - dat[i].x1 + 1) * (dat[i].y2 - dat[i].y1 + 1);
    repr(i, 0, n) {
        repr(j, 0, n) {
            if (find(i) == find(j)) continue;
            int a = max(dat[i].x1, dat[j].x1), b = min(dat[i].x2, dat[j].x2), c = max(dat[i].y1, dat[j].y1), d = min(dat[i].y2, dat[j].y2);
            if (a > b && c > d) continue;
            if (a - 1 <= b && c - 1 <= d) {
                siz[find(i)] += siz[find(j)];
                dsu[find(j)] = find(i);
            }
        }
    }
    vi ans;
    repr(i, 0, n) {
        if (find(i) == i) {
            ans.pb({siz[i]});
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto x : ans) cout << x << " ";
}

上面这个东西只跑 1ms，何意味。

E

唐，放这个 E 是中场休息吗。

7min 打了个线段树。

57:38。

int n, q, a[N], op, x, y;

struct Seg {
    int l, r, sm, ct;
    #define l(p) tr[p].l
    #define r(p) tr[p].r
    #define sm(p) tr[p].sm
    #define ct(p) tr[p].ct
} tr[N << 2];
#define M (l(p) + r(p) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)

inline void pushup(int p) {
    sm(p) = sm(ls) + sm(rs);
    ct(p) = ct(ls) + ct(rs);
}
void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if (l == r) return;
    build(ls, l, M), build(rs, M + 1, r);
}
void modify(int p, int x, int k) {
    if (l(p) == r(p)) {
        ct(p) += k;
        sm(p) += x * k;
        return;
    }
    modify(x <= M ? ls : rs, x, k), pushup(p);
}
int query1(int p, int l, int r) {
    if (l > r) return 0;
    if (l <= l(p) && r >= r(p)) return ct(p);
    if (r <= M) return query1(ls, l, r);
    if (l > M)  return query1(rs, l, r);
    return query1(ls, l, r) + query1(rs, l, r);
}
int query2(int p, int l, int r) {
    if (l > r) return 0;
    if (l <= l(p) && r >= r(p)) return sm(p);
    if (r <= M) return query2(ls, l, r);
    if (l > M)  return query2(rs, l, r);
    return query2(ls, l, r) + query2(rs, l, r);
}
void solve() {
    rd(n), rd(q);
    build(1, 0, 5e5);
    rep(i, 1, n) {
        rd(a[i]);
        modify(1, a[i], 1);
    }
    while (q--) {
        rd(op), rd(x), rd(y);
        if (op == 1) {
            modify(1, a[x], -1);
            modify(1, a[x] = y, 1);
        } else {
            int l = x, r = y;
            if (l >= r) cout << n * l << endl;
            else {
                int ans = query2(1, l, r);
                ans += r * query1(1, r + 1, 5e5);
                ans += l * query1(1, 0, l - 1);
                cout << ans << endl;
            }
        }
    }
}

G

依旧 G 放 poly 板子。

令 c_x 为 x 在 B 出现次数，答案为：

\sum_{i=1}^na_i!\sum_{j=0}^{a_i}\frac{c_j}{j!}\cdot\frac1{(a_i-j)!}

void solve() {
    repr(i, fac[0] = 1, N) fac[i] = 1ll * fac[i - 1] * i % mod;
    fiv[N - 1] = qpw(fac[N - 1], mod - 2);
    per(i, N - 2, 0) fiv[i] = fiv[i + 1] * (i + 1ll) % mod;

    rd(n), rd(m);
    rep(i, 1, n) rd(a[i]);
    rep(i, 1, m) rd(b[i]), c[b[i]]++;
    rep(i, 0, 5e5) c[i] = 1ll * c[i] * fiv[i] % mod, d[i] = fiv[i];
    int tot = 1; while (tot <= 1e6) tot <<= 1;
    ntt(c, tot, 0), ntt(d, tot, 0);
    repr(i, 0, tot) c[i] = 1ll * c[i] * d[i] % mod;
    ntt(c, tot, 1);
    int ans = 0;
    rep(i, 1, n) {
        ans = (ans + 1ll * fac[a[i]] * c[a[i]]) % mod;
    }
    cout << ans;
}

66:49

F

全场最好题。

判掉 N\nmid\sum A。

对于任意一个平均值等于 \bar A 的子集，都可以用长度减一次操作调整。

我们考虑对每个状态求一个子集，子集内部可以调整。

这部分可以 sosdp 做到 O(N2^N)。

然后随便搞一下。

void dfs(int sta) {
    if (f[sta] == sta) {
        int tot = 0;
        rep(i, 1, n) {
            if (sta >> i - 1 & 1) b[++tot] = {a[i], i};
        }
        sort(b + 1, b + tot + 1, greater <pii> ());
        repr(i, 1, tot) {
            ans.pb({b[i].se, b[i + 1].se, b[i].fi - gl});
            b[i + 1].fi += b[i].fi - gl;
        }
        return;
    }
    dfs(f[sta]), dfs(sta ^ f[sta]);
}
void solve() {
    cin >> n;
    int sm = 0;
    rep(i, 1, n) cin >> a[i], sm += a[i];
    if (sm % n) { puts("-1"); return; }
    gl = sm / n;
    repr(i, 0, 1 << n) {
        f[i] = 1e9;
        if (!i) continue;
        int sm = 0, len = __builtin_popcount(i);
        rep(j, 1, n) if (i >> j - 1 & 1) sm += a[j];
        if (sm % len == 0 && sm / len == gl) {
            f[i] = i;
        }
    }
    repr(i, 0, n) {
        repr(j, 0, 1 << n) {
            if (j >> i & 1) ckmn(f[j], f[j ^ 1 << i]);
        }
    }
    dfs((1 << n) - 1);
    cout << ans.size() << endl;
    for (auto [a, b, c] : ans) cout << a << " " << b << " " << c << endl;
}