VP了一场

1279A New Year Garland

有三种东西，分别$a,b,c$个，问能不能组成相同物品不相邻的一列。

挑最大的把其他插到最大的间隔里就行，$O(1)$。

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int q;
    cin >> q;
    while (q--) {
        int a[3];
        cin >> a[0] >> a[1] >> a[2];
        sort(a, a + 3);
        if (a[0] + a[1] < a[2] - 1) puts("No");
        else puts("Yes");
    }
    return 0;
}

1279B Verse For Santa

有$n$个物品，各自有长度，依次的放在长$s$内，现在可以省略一个，问最多放几个。

贪心比较，如果有必要省略必定省去最长的，否则不省略，$O(n)$。

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
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
 
int a[N];
 
int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, k, ans = 0;
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        ll sum = 0, la = 0;
        for (int i = 1; i <= n; ++i) {
            if (la < a[i]) {
                sum += la;
                la = a[i];
                if (sum > k) break;
                ans = i;
            } else sum += a[i];
            if (sum > k) break;
        }
        if (k - sum >= la) ans = 0;
        cout << ans << endl;
    }
    return 0;
}

1279C Stack of Presents

有一个长$n$的排列，从右到左压到栈里，现在要取出$m$个数，如果这个数上面有$k$个数，需要花$2k+1$秒，但在放回$k$个数时，可以按任意顺序放回，问取出$m$个数的最小耗时。

在取出一个较深的数的时候，前面的数我们可以按照被取的顺序，倒序放回，这样取它的时候就会在栈顶。那么维护一个最深操作的深度，在操作比这个位置深得数的代价就是$2k+1$，否则代价是$1$，$O(n+m)$

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

const int N = 3e5 + 5;

int pos[N];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, m, la = 0;
        cin >> n >> m;
        for (int i = 1, t; i <= n; ++i) {
            cin >> t;
            pos[t] = i;
        }
        ll ans = 0;
        for (int i = 1, t; i <= m; ++i) {
            cin >> t;
            if (pos[t] < la) ++ans;
            else ans += 2 * (pos[t] - i) + 1;
            la = max(la, pos[t]);
        }
        cout << ans << endl;
    }
    return 0;
}

1279D Santa’s Bot

圣诞老人用机器人发礼物，有$n$个小孩，每个小孩有$k_i$个愿望。但是机器人会随机的选一个小孩$x$，再随机选他的一个愿望$y$，再随机发给某个小孩$z$，假如$y$确实是$z$的愿望之一，那么这样的一个三元组$(x,y,z)$就是正确的，问机器人选出正确三元组的概率。

因为愿望最多不超过$10^6$，所有我们枚举愿望。选中一个孩子的概率是$\frac 1n$，选他的一个愿望被选中的概率是$\frac 1{k_i}$，统计想要这个礼物的孩子个数$cnt[j]$，那么发送正确的概率是$\frac {cnt[j]}n$，因为每个情况独立，可以相加，$O(\sum k_i)$。

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

const int mod = 998244353;
const int N = 1e6 + 5;

vector<int> gift[N];
ll cnt[N], inv[N];

void init() {
    inv[1] = 1;
    for (int i = 2; i <= 1e6; ++i) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
}

int main() {
    init();
    int n;
    cin >> n;
    for (int i = 0, t; i < n; ++i) {
        cin >> t;
        gift[i].resize(t);
        for (int &j : gift[i]) {
            cin >> j;
            ++cnt[j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int tmp = 0;
        for (int j : gift[i]) tmp += cnt[j];
        ans = (ans + inv[gift[i].size()] * tmp % mod) % mod;
    }
    ans = ans * inv[n] % mod * inv[n] % mod;
    cout << ans << endl;
    return 0;
}

1279E New Year Permutations

题意比较难描述，建议看原文/翻译

首先考虑一个长$n$的大环有多少排列，因为$n$一定是开头，$1$一定是$n$的前驱，之后剩下的$n-2$个点可以任意排，即$(n-2)!$。现在设$dp[i]$表示长为$i$的串有多少种合法排列，转移方程即：

然后我们可以通过从字典序由小到大枚举，得到第$k$大的排列由哪些长度小序列组成。根据这一步得到的结果，问题被分解成了长为$l$的环，$l$位置固定，$1$固定是$l$前驱，字典序的第$x$个环是哪个（在按位枚举字典序的时候其实就是空闲位的阶乘，枚举的过程中要保证不能形成小环，即长度必须是上一步算出的结果）,那么拼起来就可以得到最终答案，$O(n^2)$

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;

int ans[55], fa[55], vis[55];
ll dp[55], fac[55];

inline ll calc(int x) {
    x -= 2;
    if (x < 0) return 1;
    return fac[x];
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < 20; ++i)
        fac[i] = fac[i - 1] * i;
    for (int i = 20; i <= 50; ++i)
        fac[i] = 1e18;

    dp[0] = 1;
    for (int i = 1; i < 22; ++i) {
        for (int j = 0; j < i; ++j)
            dp[i] += dp[j] * calc(i - j);
    }
    for (int i = 22; i <= 50; ++i) {
        dp[i] = 1e18;
    }
}

int fi(int x) {
    if (x != fa[x])
        return fa[x] = fi(fa[x]);
    return x;
}

void permute(int l, int r, ll rk) {
    ans[l] = r;
    vis[r] = 1;
    int x = r - l - 2;
    for (int i = l + 1; i <= r; ++i) {
        for (int j = l; j <= r; ++j) {
            if (i == r && !vis[j]) {
                ans[i] = j;
                break;
            }
            if (vis[j] || fi(i) == fi(j)) continue;
            if (x < 0) x = 0;
            if (fac[x] >= rk) {
                --x;
                ans[i] = vis[j] = j;
                fa[fi(j)] = fi(i);
                break;
            } else
                rk -= fac[x];
        }
    }
}

int main() {
    init();
    int q;
    cin >> q;
    while (q--) {
        int n;
        ll k;
        cin >> n >> k;
        if (k > dp[n]) {
            cout << -1 << endl;
            continue;
        }
        for (int i = 1; i <= n; ++i) {
            vis[i] = 0;
            fa[i] = i;
        }
        for (int l = 1, r; l <= n; l = r + 1) {
            for (r = l; r <= n; ++r) {
                ll term = calc(r - l + 1) * dp[n - r];
                if (term >= k)
                    break;
                k -= term;
            }
            ll rk = (k - 1) / dp[n - r] + 1;
            k = (k - 1) % dp[n - r] + 1;
            permute(l, r, rk);

        }
        for (int i = 1; i <= n; ++i)
            cout << ans[i] << ' ';
        cout << endl;
    }
    return 0;
}

1279F New Year and Handle Change

有一个字符串，含有大小写字母，每次操作可以把长为$l$的一段字母全变成大写或小写，问最后能得到的$min$（大写字母，小写字母）的值。

挂个链，有缘回来看。题解