可终于连胜了

1342A Road To Zero

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        ll a, b, x, y;
        cin >> x >> y >> a >> b;

        ll ans = 0;
        if (a * 2 >= b) {
            int t = min(y, x);
            x -= t, y -= t;
            ans = t * b + (x + y) * a;
        } else
            ans = (x + y) * a;
        cout << ans << endl;
    }
    return 0;
}

1342B Binary Period

如果只有$0$或$1$出现，周期是$1$输出原串。
否则周期至少为$2$，按$01$或$10$循环输出即可。

B.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    string s;
    while (q--) {
        cin >> s;
        string ans = s;
        ans.resize(unique(s.begin(), s.end())-s.begin());
        if (ans.size() == 1) {
            cout << s << endl;
            continue;
        }
        if (s[0] == s[1]) {
            s[1] = (s[0] ^ '1') + '0';
        }
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            cout << s[0] << s[1];
        }
        cout << endl;
    }
    return 0;
}

1342C Yet Another Counting Problem

记$g$为$gcd(a,b)$，$a< b$。这里称$[1,g]$为一个循环，每个循环内不满足要求的是前$b-1$个和第$g$个，也就是说有$g-b$个满足要求，计算一下有几个循环以及剩余几个就行了。

C.cpp
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int g, a, b;

ll calc(ll x) {
    ll ret = x / g * (g - b);
    ret += max(0ll, x % g - b + 1);
    return ret;
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> a >> b >> t;
        if (a > b) swap(a, b);
        g = a * b / __gcd(a, b);
        while (t--) {
            ll l, r;
            cin >> l >> r;
            cout << calc(r) - calc(l - 1) << ' ';
        }
        cout << endl;
    }
    return 0;
}

1342D Multiple Testcases

思考一下就可以想到这题可以贪心，从大的向小的处理，每个队伍的元素个数肯定是越多越好。
那么满足$c_{x+1}$也就满足$c_x$，因此每次选当前队中元素个数最少的队，检查能否把当前枚举到的数插入它。如果不行，意味着必须要新申请一个队。（就贪就完事了）

D.cpp
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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> m(n), c(k + 1);
    for (int &i: m) cin >> i;
    sort(m.begin(), m.end());
    for (int i = 1; i <= k; ++i)
        cin >> c[i];
    
    vector<list<int>> ans;
    priority_queue<pii, deque<pii>, greater<>> Q;
    Q.emplace(0, 0);
    ans.resize(1);
    while (!m.empty()) {
        int a = m.back();
        pii u = Q.top();
        Q.pop();
        if (u.first == c[a]) {
            Q.emplace(u);
            u = {1, ans.size()};
            ans.emplace_back();
        } else
            ++u.first;
        Q.emplace(u);
        ans[u.second].emplace_back(a);
        m.pop_back();
    }
    
    cout << ans.size() << endl;
    for (auto &i : ans) {
        cout << i.size() << ' ';
        for (int &j : i)
            cout << j << ' ';
        cout << endl;
    }
    return 0;
}

1342E Placing Rooks

这个题学到了第二类斯特林数这个点。以$S(n,m)$表示$n$个球放入$m$个不同盒子，每个盒子不为空的方案数。

本题的一系列要求转化一下就是每行/每列都需要棋子，两种情况因此答案$\times 2$，但当$k=0$时是重复的。由于只有面对面的棋子冲突，因此$k>=n$时，答案为$0$。
将冲突的棋子连边，那么会产生$n-k$个联通分量，也就是$S(n,n-k)$，假设当前要求每行都有一个棋子，那么只有$n-k$列有棋子，从$n$列里选$n-k$列来排列一下，也就是$A_n^{n-k}$。
因此最终答案为$S_n^{n-k}A_n^{n-k}$，再根据情况乘系数。$O(n\log n)$

E.cpp
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 5e5 + 5;

ll qpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

ll fac[N], inv[N];

int main() {
    fac[0] = 1;
    for (int i = 1; i < N; ++i)
        fac[i] = fac[i - 1] * i % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; --i)
        inv[i] = inv[i + 1] * (i + 1) % mod;
    auto C = [&](int n, int m) {
        if (m < 0 | m > n) return 0ll;
        return fac[n] * inv[m] % mod * inv[n - m] % mod;
    };

    int n;
    ll k;
    cin >> n >> k;
    if (k >= n)
        cout << 0 << endl;
    else if (k == 0)
        cout << fac[n] << endl;
    else {
        ll ans = 0;
        for (int i = 0; i <= n - k; ++i) {
            ll t = C(n - k, i) * qpow(n - k - i, n);
            if (i & 1) ans = (ans - t) % mod;
            else ans = (ans + t) % mod;
        }
        if (ans < mod) ans += mod;
        ans = ans * inv[n - k] % mod;
        ans = 2 * ans * C(n, n - k) % mod * fac[n - k] % mod;
        cout << ans << endl;
    }
    return 0;
}