AtCoder Beginner Contest 194

比赛链接

D Journey

Description

题目链接

Solution

如果一个实验成功的概率为 $\frac{1}{p}$，那么重复实验直到实验成功的期望实验次数为 $p$。对于 $N$ 个节点的图，设已经联通了 $i$ 个点，要联通 $i+1$ 个点，则会从不在当前联通块中的 $N-i$ 个点中随机选取一个，其概率为 $\frac{N-i}{N}$，期望次数为 $\frac{N}{N-i}$。把 $i=1...N-1$ 的各个阶段的期望加起来即可得答案为 $\sum \limits_{i=1}^{N-1} \frac{N}{i}$。

Code

Journey

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

int n;
double ans;

signed main() {
    cin >> n;
    for (int i = 1; i <= n - 1; i++) ans += 1.0 * n / i;
    cout << setprecision(6) << fixed << ans;
    return 0;
}

E Mex Min

Description

题目链接

Solution

静态区间 $mex$ 参考这道题目：题目链接

如果不强制在线的话，可以对区间按 $r$ 排序后，用值域线段树记录每个数最后出现的位置，区间 $mex$ 最后出现位置应该小于 $l$。如果强制在线的话把值域线段树换成可持久化线段树即可。

实际上，本题还有一个比较简单的做法。转化一下题意，题目即求最小的数，使得存在一个长度大于等于 $m$ 的区间不包含这个数。因此我们对每个数维护一个 $vector$，记录其所有出现的位置，同时对每个 $vector$ 插入 $0$ 和 $n+1$。接下来按数值从小到大遍历每个 $vector$，判断是否有前一个位置和后一个位置差大于 $m$ 即可。

Code

Mex Min

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1.5E6 + 5;
const int MOD = 1E9 + 7;
int n, m, a[MAXN];
vector<int> v[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i <= n; i++) v[i].push_back(0);
    for (int i = 1; i <= n; i++) cin >> a[i], v[a[i]].push_back(i);
    for (int i = 0; i <= n; i++) v[i].push_back(n + 1);
    for (int i = 0; i <= n; i++)
        for (int j = 1; j < v[i].size(); j++)
            if (v[i][j] - v[i][j - 1] > m) return cout << i, 0;
    return 0;
}

F Digits Paradise in Hexadecimal

Description

题目链接

Solution

设 $dp[i][j]$ 表示考虑前 $i$ 位，能构造的满足以下约束条件的数的个数：

• 恰由 $j$ 个不同的数构成。
• 不全为 $0$。
• 严格小于 $N$ 的前 $i$ 位。

考虑第 $i+1$ 位，有如下两种情况：

• 选自前 $i$ 位中的某一个，有 $dp[i+1][j] \leftarrow dp[i][j]*j$。
• 和前 $i$ 位都不同，有 $dp[i+1][j+1] \leftarrow dp[i][j]*(16-j)$。

由定义可知，$dp[i+1][j+1]$ 和 $dp[i+1][j]$ 仍满足约束条件。

容易发现，有两种情况未包含在上述状态转移方程中，即：

• 前 $i$ 位全为 $0$，则第 $i+1$ 位可以在 $1$ 到 $F$ 任取，此时有 $dp[i+1][1] \leftarrow 15$。
• 前 $i$ 位等于 $N$ 的前 $i$ 位，则第 $i+1$ 位应小于 $N$ 的第 $i+1$ 位。容易统计出前 $i$ 位中有多少个不同的数，记为 $tot$，那么对于小于 $N_{i+1}$ 的每一个数，如果它在之前没有出现过，则有 $dp[i+1][tot+1] \leftarrow 1$；否则有 $dp[i+1][tot] \leftarrow 1$。

Code

Digits Paradise in Hexadecimal

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, k, tot;
char c[MAXN];
LL dp[MAXN][17];
int cnt[17], vis[17];

int f(char c) { return ((c >= 'A' && c <= 'F') ? c - 'A' + 10 : c - '0'); }

void add(LL& a, LL b) { a = ((a + b) % MOD + MOD) % MOD; }

signed main() {
    scanf("%s%d", c + 1, &k);
    n = strlen(c + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 16; j++) {
            add(dp[i][j], dp[i - 1][j] * j);
            if (j >= 2) add(dp[i][j], dp[i - 1][j - 1] * (16 - j + 1));
        }
        if (i >= 2) add(dp[i][1], 15);
        if (tot) add(dp[i][tot], cnt[f(c[i])]);
        if (f(c[i])) add(dp[i][tot + 1], f(c[i]) - cnt[f(c[i])] - (i == 1));
        if (!vis[f(c[i])]) {
            vis[f(c[i])] = 1;
            tot++;
            for (int j = f(c[i]) + 1; j <= 16; j++) cnt[j]++;
        }
    }
    add(dp[n][k], tot == k);
    printf("%lld", dp[n][k]);
    return 0;
}