2022-09-10 17:20 湖南师范大学附属中学算法工程师发布于湖南

关注

牛客挑战赛 63 解题报告

$\tag{Author : CCA}$

A

考虑从后往前填数，可以发现除了第一个位置之外每个位置都有且仅有两种选择，故答案为 $2 ^ {n - 1}$ 。

时间复杂度可以做到 $\Theta(\log n)$ 。

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int n, fac = 1;

int Pow (int a, int k) {
    int res = 1;
    for (; k; a = 1ll * a * a % mod, k >>= 1)
        if (k & 1) res = 1ll * res * a % mod;
    return res;
}

int main () {

    cin >> n;
    for (int i = 1; i <= n; i++) fac = 1ll * fac * i % mod;

    cout << 1ll * Pow(2, n - 1) * Pow(fac, mod - 2) % mod << endl;

    return 0;
}

B

先考虑 $k = 0$ 的情况。
首先可以发现，如果要最大化区域数量，那么任意三条对角线不会交于一点。
设多边形内部有 $T$ 个对角线之间的交点，并且多边形内部由对角线划分出的图形中，三角形有 $n_3$ 个，四边形有 $n_4$ 个，五边形有 $n_5$ 个 $......$
多边形内部的 $k$ 边形会有 $k$ 个顶点，并且多边形内部的每一个点都会被 $4$ 个图形作为顶点，多边形边上的每一个顶点都会被 $(n - 2)$ 个图形作为顶点，故有关系式：

$3n_3 + 4n_4 + 5n_5 + ... = 4T + n(n - 2) \tag{1}$

另外，还可以通过角度关系列出类似的关系式：

$n_3 \times 180^{\circ} + n_4 \times 360^{\circ} + n_5 \times 540^{\circ} + ... = T \times 360^{\circ} + (n - 2) \times 180 ^ {\circ} \tag{2}$

计算 $\frac{1}{2}\left[(1) - \frac{(2)}{180 ^ {\circ}}\right]$ 可得：

$n_3 + n_4 + n_5 + ... = T + \frac{(n - 1)(n - 2)}{2} \tag{3}$

考虑到从多边形的顶点中任选 $4$ 个都可以形成一个交点，所以 $T = \binom{n}{4}$ ，将其带入式 $3$ 可得：
$n_3 + n_4 + n_5 + ... = \frac{[n ^ 2 - 3n + 12](n - 1)(n - 2)}{24} \tag{4}$

然后考虑 $k \not= 0$ 的情况。
观察一下去掉一条对角线会发生什么影响，容易发现若设这条对焦点与其它对角线形成的交点数目为 $k$ ，那么去掉它会导致区域数量减少 $k + 1.$
于是可以想到每次去掉与其它对角线交点数量最少的那一个，容易发现随着去除的边数从 $1$ 到 $n$ ，每条新去掉边的 $k$ 依次为：
$n - 3, n - 4, n - 4, ... , n - 4, n - 5$

显而易见，答案可以 $\Theta(1)$ 计算。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define dep(i, r, l) for (int i = r; i >= l; i--)

const int mod = 1e9 + 7;
#define M(x) ((x) % mod)

long long n, k, ans;

int main () {

    cin >> n >> k;

    ans = M(M(M(M(M(n) * M(n) - 3 * M(n) + 12) * M(n - 1)) * M(n - 2)) * 41666667);

    if (k) ans = M(ans - M(n) + 2 + mod), k--;
    if (k == n - 1) ans = M(ans - M(n) + 4 + mod), k--;
    ans = M(ans - M(M(n - 3) * M(k)) + mod);

    cout << M(M(ans) + mod) << endl;

    return 0;
}

C

首先可以发现答案上界就是 $x$ 本身作为自然数在的位置，其值不超过 $18 \times 10 ^ {18}$ ，所以答案是可以用 `unsigned long long` 存储的（当然如果有人傻傻用了高精或 `__int128` 也是可以通过的）。
可以发现问题的关键就是确定一种划分方案，只要划分方案确定了就可以快速确定数所在的位置。
既然如此，我们先来解决掉细枝末节的地方，即给定一个数 $x$ ，确定它作为自然数出现在第几位。考虑预处理前 $10, 100, 1000, \cdots$ 个数占用的位数，可以发现剩下的数占用的位数都是相同的，于是答案可以直接计算。
接下来考虑枚举一种合法的划分方案，容易发现，如果确定了最左边和最右边的断点，就可以将问题转化为一个判定问题。分类讨论：
- 不进行划分，可以直接计算这种情况的答案。
- 划分成两段，枚举前后缀重合的长度即可简单判断，需要注意前缀是全是 $9$ 的情况。
- 划分成大于 $2$ 段，枚举中间的第一个数即可简单判断。
容易发现复杂度来源于第三种分类，可以发现合法情况是非常少的，所以可以均摊一下，发现单组询问时间复杂度只有 $\Theta(\lg ^ 3 x)$ ，并且非常跑不满。

#include <bits/stdc++.h>
using namespace std;

const int L = 20;

int q;
long long x, sub[L][L];
unsigned long long sum[L], pw10[L];

int numlen (long long x) {
    int res = 1;
    x /= 10;
    while (x) res++, x /= 10;
    return res;
}

long long numsub (long long x, int l, int r) {
    return x % pw10[l] / pw10[r - 1];
}

unsigned long long numpos (long long x) {
    int len = numlen(x - 1);
    unsigned long long res = sum[len - 1];
    res += 1ull * len * (x - pw10[len - 1]);
    return res + (len == 1) + 1;
}

bool equapre (long long x, long long num) {
    int lx = numlen(x), l = numlen(num);
    return numsub(num, l, l - lx + 1) == x;
}

bool equasuf (long long x, long long num) {
    int lx = numlen(x);
    return numsub(num, lx, 1) == x;
}

bool check (long long fir, long long S, long long T, long long M) {
    if (S && !equasuf(S, fir - 1)) return false;
    int lf = numlen(fir), l = numlen(M);
    int cnt = 0;
    for (int i = l - lf; i >= 1; i -= lf)
        if (numsub(M, i, max(i - lf + 1, 1)) != fir + (++cnt)) return false;
    if (T && !equapre(T, fir + (++cnt))) return false;
    return true;
}

int main () {

    pw10[0] = 1;
    for (int i = 1; i <= 19; i++) pw10[i] = pw10[i - 1] * 10;
    sum[1] = 10;
    for (int i = 2; i <= 18; i++)
        sum[i] = sum[i - 1] + 9ull * i * pw10[i - 1];

    scanf("%d", &q); while (q--) {
        scanf("%lld", &x);
        int len = numlen(x);
        for (int i = 1; i <= len; i++)
            for (int j = i; j <= len; j++)
                sub[i][j] = numsub(x, i, j);
        
        unsigned long long ans = numpos(x);
        int pwx = pw10[upper_bound(pw10, pw10 + 20, x) - pw10];
        if (x + 1 == pwx) {
            printf("%llu\n", numpos(x - pwx / 10) + 1);
            continue;
        }

        for (int k = 1; k < len; k++) {
            long long S = numsub(x, len, len - k + 1);
            long long T = numsub(x, len - k, 1);
            for (int l = 0; l <= min(k, len - k); l++) {
                int ls = numlen(S), lt = numlen(T);
                if (numsub(S, ls - l, 1) + 1 == pw10[upper_bound(pw10, pw10 + 20, numsub(S, ls - l, 1)) - pw10]){
                    if (numsub(S, k, k - l + 1) == numsub(T - 1, l, 1))
                        ans = min(ans, numpos((T - 1) * pw10[ls - l] + numsub(S, ls - l, 1)) + lt - l);
                } else {
                    if (numsub(S, k, k - l + 1) != numsub(T - (l == k), l, 1)) continue;
                    else {
                        if (S + 1 == pw10[upper_bound(pw10, pw10 + 20, S) - pw10]) {
                            if (l != 0) continue;
                            ans = min(ans, numpos((T - 1) * pw10[ls] + S) + lt);
                        } else ans = min(ans, numpos(T * pw10[ls - l] + numsub(S, ls - l, 1)) + lt - l);
                    }
                }
            }  
        }

        for (int l = len; l >= 1; l--)
            for (int r = l; r >= 1; r--) {
                long long S = 0, T = 0;
                if (l != len) S = numsub(x, len, l + 1);
                if (r != 1) T = numsub(x, r - 1, 1);
                for (int k = l - max(numlen(S), numlen(T)) + 1; k >= r; k--)
                    if (check(numsub(x, l, k), S, T, numsub(x, l, r))) {
                        if (l == len) ans = min(ans, numpos(numsub(x, l, k)));
                        else ans = min(ans, numpos(numsub(x, l, k) - 1) + l - k + 1 - numlen(S));
                    }
            }

        printf("%llu\n", ans);
    }

    return 0;
}

D

不妨将物品按 $v_i$ 从小到大排序。
设 $f_{i, j, R}$ 表示在前 $i$ 个物品中选择了 $j$ 个放入集合 $T$ 中，颜色的并集为 $R$ 的最大的 $S$ 的贡献。
转移时，如果选择放入集合 $T$ ，则直接转移到 $f_{i + 1, j + 1, R | col_{i + 1}}$ 。
如果选择不放入 $T$ ，那尽可能选择后面的物品，使 $S$ 中物品的数量恰好达到上界，容易发现这样的贪心是对的。
总时间复杂度 $\Theta(nm2 ^ m)$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10, M = 13;

int n, k, m, f[N][M + 1][1 << M];
pair <int, int> a[N];

int main () {

    scanf("%d%d%d", &n, &k, &m);
    for (int num, idx, i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].first, &num);
        while (num--) scanf("%d", &idx), a[i].second |= (1 << idx - 1);
    }

    sort(a + 1, a + n + 1);
    int lim = (1 << m) - 1;
    memset(f, 128, sizeof f), f[0][0][0] = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++)
            for (int S = 0; S <= lim; S++) {
                if (j < m) f[i + 1][j + 1][S | a[i + 1].second] = max(f[i + 1][j + 1][S | a[i + 1].second], f[i][j][S]);
                if (n - i <= k - j) f[i + 1][j][S] = max(f[i + 1][j][S], f[i][j][S] + a[i + 1].first);
                f[i + 1][j][S] = max(f[i + 1][j][S], f[i][j][S]);
            }

    long long ans = 0;
    for (int j = 0; j <= m; j++)
        for (int S = 0; S <= lim; S++)
            ans = max(ans, 1ll * __builtin_popcount(S) * f[n][j][S]);
    printf("%lld\n", ans);

    return 0;
}

E

考虑求出一个确定序列的代价，二分答案，然后用 $\Theta(n \log n)$ 的 $\rm DP$ 求出最小分出的段数 $L$ 和最大分出的段数 $R$ 。容易发现当前答案可行当且仅当 $L \leqslant k \leqslant R$ 。于是该算法时间复杂度 $\Theta(n \log ^ 2 n)$ 。
然后考虑置换，可以按随机顺序枚举置换。每次枚举一个新的置换就 `check` 一下当前答案是否可以在该置换上实现，这部分时间复杂度为 $\Theta(T n \log n)$ ，如果可以实现才重新二分答案。容易发现重新二分答案当且仅当这个置换的答案比之前所有置换都优，这种置换的数量有调和级数约束，所以这部分时间复杂度为 $\Theta(n \log ^ 2 n\ln T)$ 。

#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) (x & (-x))

const int N = 2e3 + 10;
const long long INF = 2e12 + 10;

int n, k, T, a[N], b[N][N], c[N], f[N], p[N];
long long sum[N], dis[N], smin[N], smax[N], t1[N], t2[N], ans = -INF;

void Modify1 (int pos, long long x) {
    for (; pos; pos -= lowbit(pos))
        t1[pos] = min(t1[pos], x);
}

void Modify2 (int pos, long long x) {
    for (; pos; pos -= lowbit(pos))
        t2[pos] = max(t2[pos], x);
}

long long Query1 (int pos) {
    long long res = INF;
    for (; pos <= n + 1; pos += lowbit(pos))
        res = min(res, t1[pos]);
    return res;
}

long long Query2 (int pos) {
    long long res = -INF;
    for (; pos <= n + 1; pos += lowbit(pos))
        res = max(res, t2[pos]);
    return res;
}

bool check (long long lim) {
    for (int i = 1; i <= n + 1; i++) t1[i] = INF, t2[i] = -INF;
    Modify1(sum[0] + 1, smin[0] = 0), Modify2(sum[0] + 1, smax[0] = 0);
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(dis, dis + n + 1, dis[sum[i]] - lim) - dis;
        Modify1(sum[i] + 1, smin[i] = Query1(pos + 1) + 1);
        Modify2(sum[i] + 1, smax[i] = Query2(pos + 1) + 1);
    }
    return (smin[n] <= k && smax[n] >= k);
}

int main() {

    cin >> n >> k >> T;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> f[i];

    for (int i = 1; i <= n; i++) b[1][i] = i;
    for (int i = 2; i <= T; i++)
        for (int j = 1; j <= n; j++)
            b[i][j] = f[b[i - 1][j]];
    for (int i = 1; i <= T; i++) p[i] = i;
    srand(time(NULL)), random_shuffle(p + 1, p + T + 1);

    for (int t = 1; t <= T; t++) {
        for (int i = 1; i <= n; i++) a[i] = c[b[p[t]][i]];
        dis[0] = sum[0] = 0;
        for (int i = 1; i <= n; i++) dis[i] = sum[i] = sum[i - 1] + a[i];
        sort(dis, dis + n + 1);
        for (int i = 0; i <= n; i++)
            sum[i] = lower_bound(dis, dis + n + 1, sum[i]) - dis;

        if (check(ans)) continue;
        long long l = ans + 1, r = INF, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            check(mid) ? r = mid - 1 : l = mid + 1;
        }
        ans = l;
    }
    printf("%lld\n", ans);

    return 0;
}

F

将计算总和转化为计算期望，最后乘以总情况数 $2 ^ {n ^ 2}$ 即为答案。
首先考虑道路建设情况确定该如何计算旅行愉悦度。可以想到一个简单的贪心，即每次选择路径 LCA 尽可能靠下的点，一条路径能被选择当且仅当其 LCA 的子树中不存在一条已经被选择的路径的 LCA 的子树中有这条路径的端点。
接下来考虑 $\rm DP$ ，设 $f_{u, x}$ 表示在以 $u$ 为根的子树中，不存在于已经被选择的路径的 LCA 的子树中的点数等于 $k$ 的概率。转移时考虑将 $f_{u, x_1}$ 和 $f_{v, x_2}$ 合并， $u$ 的子树中不存在任何一条可选择路径的概率为 $\frac{1}{2 ^ {2x_1x_2}}$ ，转移到 $f_{u, x_1 + x_2}$ ，否则转移到 $f_{u, 0}$ 。
最后将所有 $f_{i, 0}$ 求和即为所求期望，总时间复杂度 $\Theta(n ^ 2)$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 100 + 10, mod = 998244353;

int n, f[N][N], tmp[N], d[N], siz[N], pow2[N * N], inv[N * N], ans;
vector <int> to[N];

int Pow (int a, int k) {
    int res = 1;
    for (; k; a = 1ll * a * a % mod, k >>= 1)
        if (k & 1) res = 1ll * res * a % mod;
    return res;
}

void dfs (int u, int fa) {
    siz[u] = 1, f[u][0] = f[u][1] = Pow(2, mod - 2);
    if (d[u] == 1 && u != 1) return;
    for (auto v : to[u]) if (v != fa) {
        dfs(v, u);
        for (int i = 0; i <= siz[u] + siz[v]; i++) tmp[i] = 0;
        for (int i = 0; i <= siz[u]; i++)
            for (int j = 0; j <= siz[v]; j++) {
                if (!i) tmp[0] = (tmp[0] + 1ll * f[u][i] * f[v][j]) % mod;
                if (i) tmp[i + j] = (tmp[i + j] + 1ll * f[u][i] * f[v][j] % mod * inv[2 * i * j]) % mod;
                if (i) tmp[0] = (tmp[0] + 1ll * f[u][i] * f[v][j] % mod * (1 - inv[2 * i * j] + mod)) % mod;
            }
        siz[u] += siz[v];
        for (int i = 0; i <= siz[u]; i++) f[u][i] = tmp[i];
    }
}

int main () {

    scanf("%d", &n);
    for (int u, v, i = 1; i < n; i++) {
        scanf("%d%d", &u, &v), d[u]++, d[v]++;
        to[u].push_back(v), to[v].push_back(u);
    }

    pow2[0] = 1;
    for (int i = 1; i <= n * n; i++) pow2[i] = 2 * pow2[i - 1] % mod;
    inv[n * n] = Pow(pow2[n * n], mod - 2);
    for (int i = n * n - 1; i >= 0; i--) inv[i] = 2 * inv[i + 1] % mod;

    dfs(1, 0);

    for (int i = 1; i <= n; i++) ans = (ans + f[i][0]) % mod;
    printf("%lld\n", 1ll * ans * Pow(2, n * n) % mod);

    return 0;
}