Permutation Printing

题目

输入一个整数 \(n\)，输出长度为 \(n\) 的排列，满足不存在两个不同的索引 \(1\leq i,j< n\)，使得 \(p_{i}\) 整除 \(p_{j}\) 且 \(p_{i+1}\) 整除 \(p_{j+1}\)。

数据范围：\(3\leq n\leq 10^{5}\)。

思路

可以构造排列 \(1,n,2,n-1,\dots,\lceil\frac{n+1}{2}\rceil\)。如果 \(i<j\)，则有 \(p_{i+1}>p_{j+1}\)，必定不能整除，反之亦然。

代码

1
2
3
4
5
6
7
8
9
10
11
12

public static void solve() {
    int n = io.nextInt();
    int l = 1, r = n;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            io.print(l++ + " ");
        } else {
            io.print(r-- + " ");
        }
    }
    io.println();
}

Lexicographically Largest

题目

输入长度为 \(n\) 的数组 \(a\)，初始时有一个空集 \(S\)，执行以下三步操作恰好 \(n\) 次：

• 选择一个索引 \(i\)，\(1\leq i\leq |a|\)。
• 将 \(a_{i}+i\) 插入集合 \(S\)。
• 从 \(a\) 中删除 \(a_{i}\)，\(a_{i}\) 之后的所有元素的索引将减少 \(1\)。

将得到的集合 \(S\) 中的元素按照递减顺序排列，输出能够得到的字典序最大的排列。

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

思路

可以发现字典序最大的排列总是包含 \(n\) 个元素。暴力的想法是，可以首先将所有 \(a_{i}+i\) 从小到大排序，我们总是优先选择最大的元素，如果有多个元素最大，就优先选择其中索引 \(i\) 最小的元素，从而可以保证得到字典序最大的排列。通过观察可以发现，如果从小到大排列 \(a_{i}+i\)，然后倒序遍历数组，我们可以得到的最大元素为 \(\min(a[i],a[i+1]-1)\)，对所有 \(1\leq i< n\) 都成立。比赛时没发现，使用的是更复杂的方法，其实不难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        a[i] += i + 1;
    }
    Arrays.sort(a);
    for (int i = n - 2; i >= 0; i--) {
        a[i] = Math.min(a[i], a[i + 1] - 1);
    }
    for (int i = n - 1; i >= 0; i--) {
        io.print(a[i] + " ");
    }
    io.println();
}

Sum over all Substrings (Hard Version)

题目

输入长度为 \(n\) 的二进制字符串 \(s\)，输出 \(\sum_{i=1}^{n}\sum_{j=i}^{n}f(s_{i}s_{i+1}\cdots s_{j})\)。对于某个二进制模式串 \(p\)，\(f(p)\) 表示满足以下条件的二进制字符串 \(q\)，其中 \(1\) 的最小可能数量：假设 \(p\) 和 \(q\) 的长度均为 \(m\)，对于所有 \(1\leq i\leq m\)，存在 \(l\) 和 \(r\)（\(1\leq l\leq i\leq r\leq m\)），使得 \(p_{i}\) 在 \(q_{l}q_{l+1}\cdots q_{r}\) 中的出现次数至少为 \(\lceil \frac{m}{2}\rceil\)。

数据范围：\(1\leq n\leq 10^{6}\)。

思路

暴力的想法是枚举所有子串，然后对于每个子串计算 \(f\) 值。现在思考对于给定的 \(p\)，如何计算 \(f\) 值。正序遍历子串，基本算法如下：如果 \(p_{i}=0\)，则直接在 \(q_{i}\) 放置 \(0\)；如果 \(p_{i}=1\)，则可以在 \(q_{i+1}\) 放置 \(1\)，\(q_{i}\) 和 \(q_{i+2}\) 放置 \(0\)，从而不论 \(p_{i+1}\) 和 \(p_{i+2}\) 是什么，都存在满足条件的 \(l\) 和 \(r\)（在区间 \([i,i+2]\) 范围内）。时间复杂度为 \(O(n^{3})\)，如果在遍历的同时计算子串，则时间复杂度为 \(O(n^{2})\)。可以使用动态规划将时间复杂度降低为 \(O(n)\)，定义 \(dp_{i}\) 表示 \(\sum_{j=i}^{n}f(s_{i}s_{i+1}\cdots s_{j})\)，转移方程见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void solve() {
    int n = io.nextInt();
    char[] s = io.next().toCharArray();

    long ans = 0L;
    long[] dp = new long[n + 3];
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == '1') {
            dp[i] = dp[i + 3] + n - i;
        } else {
            dp[i] = dp[i + 1];
        }
        ans += dp[i];
    }
    io.println(ans);
}

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\) 个对角线。

代码

1
2
3
4
5
6
7
8

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}\)。

代码

1
2
3
4
5
6
7
8

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}}\) 个集合存在祖先关系。

代码

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

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 通过测试，真不知道为什么我的就不行。

代码

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

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;
}

ABC 都是简单模拟题。D 题很经典，利用哈希表求同余的下标对数。E 题需要观察到答案只和元素的位数有关。F 题给出元素的偏序，判断是否存在全序，可以将顺序建模成有向图，然后使用拓扑排序判断是否存在环。G 题需要观察到如下性质，1 和 2 的数量不能相差超过一，3 和 4 放置的方案数相互独立，计算组合数的方式类似将 m 个球放入 n 个可以为空的盒子，公式为 \(C_{n+m-1}^{n-1}=C_{n+m-1}^{m}\)，可以看看灵神的视频。