Codeforces Round 926 (Div. 2)

Sasha and the Drawing

题目

输入整数 \(n\) 表示 \(n\times n\) 的正方形网格，网格总共有 \(4n-2\) 条对角线，输出最小的着色单元格数量，使得至少有 \(k\) 个对角线上存在着色的单元格。

数据范围：\(2\leq n\leq 10^{8}\)，\(1\leq k\leq 4n-2\)。

思路

最好情况下，对 \(1\) 个单元格着色，可以贡献 \(2\) 个对角线，最多有 \(2n-2\) 个单元格满足该条件，例如选择着色第一行的 \(n\) 个单元格和最后一行的中间 \(n-2\) 个单元格。剩下 \(2\) 个单元格，每着色 \(1\) 个可以贡献 \(1\) 个对角线。

代码

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    if (k <= 4 * n - 4) {
        io.println((k + 1) / 2);
    } else {
        io.println(2 * n - 2 + (k - (4 * n - 4)));
    }
}

Sasha and the Casino

题目

输入三个整数 \(k,x,a\)，表示有一个游戏每次可以选择下注 \(y\) 个硬币（\(y\leq a\)），如果赢了将获得 \(y\cdot k\) 个硬币，输了不会获得任何硬币，游戏最多连续输 \(x\) 次。输出初始有 \(a\) 个硬币时，是否存在某个方案能够获取无限数量的硬币。

数据范围：\(2\leq k\leq 30\)，\(1\leq x\leq 100\)，\(1\leq a\leq 10^{9}\)。

思路

首先，前 \(x\) 次游戏都下注 \(1\) 个硬币，最后下注 \(a-x\) 个硬币不是最优策略，因为可能会提前赢，如果赢的时候增量为负，将会输得很惨。所以对于第 \(i\) 次下注（\(1\leq i\leq x+1\)），下注大小 \(y_{i}\) 需要满足赢得游戏时 \(y_{i}\times (k-1)>\sum_{j=1}^{i-1}y_{j}\)。

代码

public static void solve() {
    int k = io.nextInt(), x = io.nextInt(), a = io.nextInt();
    int sum = 0;
    for (int i = 0; i <= x && sum <= a; i++) {
        sum += sum / (k - 1) + 1;
    }
    io.println(sum <= a ? "YES" : "NO");
}

Sasha and a Walk in the City

题目

输入一棵树，包含 \(n\) 个节点和 \(n-1\) 条边，输出存在多少个集合，使得任意简单路径都不会包含超过两个在集合中的节点，答案对 \(998244353\) 取模。

数据范围：\(2\leq n\leq 3\cdot 10^{5}\)，\(1\leq u_{i},v_{i}\leq n\)，\(u_{i}\neq v_{i}\)。

思路

假设节点 \(1\) 是树的根节点，定义 \(dp_{v}\) 表示以 \(v\) 为根的子树的非空集合个数，集合满足不存在一对节点，其中一个是另一个的祖先。假设节点 \(u_{1},u_{2},\dots,u_{k}\) 是节点 \(v\) 的子节点，则有 \(dp_{v}=\prod_{i=1}^{k}(dp_{u_{i}}+1)\)，当所有子树的集合为空时，表示只选择节点 \(v\)。最后答案为 \(\sum_{i=1}^{n}dp_{i}+1\)，可以通过以下分类讨论得到：

• 不存在祖先关系的集合个数为 \(dp_{1}+1\)，其中 \(dp_{1}\) 表示不存在祖先关系的非空集合个数，\(1\) 表示集合为空的情况。
• 存在祖先关系的集合个数为 \(\sum_{i=2}^{n}dp_{i}\)，因为对于每个节点 \(v\) 作为祖先，有 \(\sum_{i=1}^{k}dp_{u_{i}}\) 个集合存在祖先关系。

代码

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1;
        g[u].add(v);
        g[v].add(u);
    }

    long[] dp = new long[n];
    dfs(0, -1, g, dp);

    long ans = 1L;
    for (long x : dp) {
        ans = (ans + x) % MOD;
    }
    io.println(ans);
}

private static void dfs(int x, int fa, List<Integer>[] g, long[] dp) {
    dp[x] = 1;
    for (int y : g[x]) {
        if (y != fa) {
            dfs(y, x, g, dp);
            dp[x] = dp[x] * (dp[y] + 1) % MOD;
        }
    }
}

Sasha and the Wedding Binary Search Tree

题目

输入两个整数 \(n\) 和 \(c\)，表示一颗二叉搜索树，以及节点值的取值范围为 \([1,c]\)。然后输入 \(n\) 行 \(l_{i},r_{i},v_{i}\) 值，表示节点 \(i\) 的左右子节点和该节点的值。如果 \(l_{i}<0\) 或 \(r_{i}<0\)，则表示没有对应的子节点。如果 \(val_{i}<0\)，则表示不知道该节点的值是多少。输出可能的二叉搜索树个数，答案对 \(998244353\) 取模。

数据范围：\(2\leq n\leq 5\cdot 10^{5}\)，\(1\leq c\leq 10^{9}\)。

思路

首先进行中序遍历，将所有值添加到一个列表，那么可以求出每段连续负数值的方案数，将所有段的方案数相乘就是答案。对于每一段可以知道其上下限，假设段的长度为 \(m\)，取值范围为 \([lo,hi]\)，则可能的取值数量为 \(k=hi-lo+1\)。那么方案数就是将 \(m\) 个球放入 \(k\) 个盒子的方案数，盒子可以为空，公式为 \(C_{m+k-1}^{k-1}=C_{m+k-1}^{m}\)，可以参考上一场比赛的最后一题。

需要注意的是，\(k\) 的取值范围很大，我们使用等号右边的公式计算方案数，可以只循环 \(m\) 次。由于答案需要取模，循环中取模之后的值可能无法被整除，所以必须计算模乘法逆元。以及下面的代码会栈溢出，但是改写为 C++ 就不会，只能说 Java 占用的栈空间比较大么，但是也有其他人使用 Java 通过测试，真不知道为什么我的就不行。

代码

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), c = io.nextInt();
    int[] val = new int[n];
    int[][] g = new int[n][2];
    for (int i = 0; i < n; i++) {
        int l = io.nextInt() - 1, r = io.nextInt() - 1;
        val[i] = io.nextInt();
        g[i][0] = l;
        g[i][1] = r;
    }

    List<Integer> aux = new ArrayList<>();
    dfs(0, g, val, aux);
    aux.add(c);

    long ans = 1L;
    int lo = 1, cnt = 0;
    for (int x : aux) {
        if (x < 0) {
            cnt++;
            continue;
        }
        if (cnt > 0) {
            ans = ans * calc(lo, x, cnt) % MOD;
            cnt = 0;
        }
        lo = x;
    }
    io.println(ans);
}

private static void dfs(int x, int[][] g, int[] val, List<Integer> aux) {
    if (x < 0) {
        return;
    }
    dfs(g[x][0], g, val, aux);
    aux.add(val[x]);
    dfs(g[x][1], g, val, aux);
}

private static long calc(int lo, int hi, int cnt) {
    long res = 1L;
    int len = hi - lo + 1;
    for (int i = cnt + len - 1, j = 1; j <= cnt; i--, j++) {
        res = res * i % MOD * pow(j, MOD - 2) % MOD;
    }
    return res;
}

private static long pow(long x, long n) {
    long res = 1L;
    for (; n != 0; x = x * x % MOD, n >>= 1) {
        if ((n & 1) == 1) {
            res = res * x % MOD;
        }
    }
    return res;
}