1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    vi cnt(26);
    rep(i, 0, n - 1) cnt[s[i] - 'a']++;
    int tem = *max_element(all(cnt));
    if (tem > (n + 1) / 2) {
        cout << "No" << endl;
        return;
    }
    priority_queue<pii, vector<pii>, less<>> q;
    rep(i, 0, 25) {
        if (cnt[i]) q.emplace(cnt[i], i);
    }
    cout << "Yes" << endl;
    string res = "";
    while (sz(q) >= 2) {
        auto [x1, y1] = q.top();
        q.pop();
        auto [x2, y2] = q.top();
        q.pop();
        res.push_back((char)('a' + y1));
        res.push_back((char)('a' + y2));
        if (x1 > 1) q.emplace(x1 - 1, y1);
        if (x2 > 1) q.emplace(x2 - 1, y2);
    }
    if (!q.empty()) res.push_back((char)(q.top().second + 'a'));
    cout << res << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

constexpr int MOD = 998244353;
constexpr int MX = 1e6 + 1;
ll F[MX];      // 预处理阶乘
ll INV_F[MX];  // 预处理逆元
ll qpow(ll x, int n) {
    ll res = 1;
    for (; n; n >>= 1) {
        if (n % 2) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}
auto init = [] {
    F[0] = 1;
    for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % MOD;  // 预处理阶乘
    INV_F[MX - 1] = qpow(F[MX - 1], MOD - 2);
    for (int i = MX - 1; i; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;
    }  // 预处理逆元
    return 0;
}();
// 计算C(n,m),即从n个数中取m个数
ll comb(ll n, ll m) {
    if (n < m) return 0;
    ll res = 1;
    rep(i, 0, m - 1) { res = res * ((n - i) % MOD) % MOD; }
    res = res * INV_F[m] % MOD;
    return res;
}
void solve() {
    int n;
    cin >> n;
    vi pa(n);
    vvi ma(n);
    rep(i, 1, n - 1) {
        cin >> pa[i];
        pa[i]--;
        ma[pa[i]].push_back(i);
        ma[i].push_back(pa[i]);
    }
    vl c(n);
    rep(i, 0, n - 1) cin >> c[i];
    vl d(n);
    rep(i, 0, n - 1) cin >> d[i];
    ll ans = 1;
    auto dfs = [&](this auto&& dfs, int x, int pa) -> ll {
        ll tem = c[x];
        for (int& p : ma[x]) {
            if (p == pa) continue;
            tem += dfs(p, x);
        }
        ans = ans * comb(tem, d[x]) % MOD;
        return tem - d[x];
    };
    dfs(0, -1);
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

void solve() {
    int n;
    cin >> n;
    vl a(n);
    rep(i, 0, n - 1) cin >> a[i];
    stack<pll> s;
    rep(i, 0, n - 1) {
        s.emplace(1, a[i] - i + n);
        while (sz(s) >= 2) {
            auto [x1, y1] = s.top();
            s.pop();
            auto [x2, y2] = s.top();
            s.pop();
            ll tem = (y2 + x2 - 1) / x2;
            ll tem2 = y1 / x1;
            if (tem > tem2) {
                s.emplace(x1 + x2, y1 + y2);
            } else {
                s.emplace(x2, y2);
                s.emplace(x1, y1);
                break;
            }
        }
    }
    ll ans = 0;
    vector<pll> tem;
    while (!s.empty()) {
        tem.push_back(s.top());
        s.pop();
    }
    ranges::reverse(tem);
    ll pre1 = 0;
    ll pre2 = 0;
    int idx = 0;
    for (auto& [x, y] : tem) {
        ll tem2 = y / x;
        ll re = y % x;
        rep(i, 0, x - 1) {
            ll tem3 = tem2 + (i >= x - re);
            pre1 += a[idx];
            pre2 += tem3 - n + idx;
            if (idx != n - 1) ans += pre1 - pre2;
            idx++;
        }
    }
    cout << ans << endl;
    return;
}