Rectangle Cutting

题目

输入两个整数 \(a\) 和 \(b\)，表示矩形 \(a\times b\)，判断是否能将矩形切割一次再拼接得到不同的矩形，切割线要求平行于某条边且得到的矩形边长为整数。

数据范围：\(1\leq a,b\leq 10^{9}\)。

思路

以下讨论总是假设 \(a\leq b\)：

• 首先我们总是应该对半切，如果不对半切，并且想要拼接得到矩形，那么只能切割更长的边 \(b\)，得到 \(a\times a\) 和 \(a\times(b-a)\)，但是不论怎么拼接都和原矩形相同。
• 如果 \(a\) 是偶数，可以总是对半切 \(a\)，然后拼接得到不同的矩形 \(\frac{a}{2}\times 2b\)。
• 如果 \(a\) 是奇数，\(b\) 必须是偶数，否则无法对半切。此时只能对半切 \(b\)，拼接得到矩形 \(2a\times\frac{b}{2}\)，当 \(a\neq\frac{b}{2}\) 时，得到的矩形和原矩形不同。

代码

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

public static void solve() {
    int a = io.nextInt(), b = io.nextInt();
    if (a > b) {
        int t = a;
        a = b;
        b = t;
    }
    if (a % 2 == 0 || b % 2 == 0 && b != 2 * a) {
        io.println("Yes");
    } else {
        io.println("No");
    }
}

Equalize

题目

输入长度为 \(n\) 的数组 \(a\)，可以选择一个 \([1,n]\) 的任意排列 \(p\)，执行 \(a_{i}=a_{i}+p_{i}\) 操作。输出执行操作之后，能够得到的数组 \(a\) 中相同元素最大出现次数的最大值。

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

思路

将数组加上任意排列，肯定是更小的数对应更大的数，才能使相同元素的最大出现次数最大化。我们可以将数组 \(a\) 排序同时去重，之所以去重是因为相同元素加上排列之后必定不相同，然后将排列看作固定的递减数组。只要数组 \(a\) 中的两个数的差值小于 \(n\)，那么这两个数之间的元素必定可以在操作之后变成相同的元素。问题就转化为求区间的最大长度，同时最大值和最小值的差值小于 \(n\)，可以使用滑动窗口求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static void solve() {
    int n = io.nextInt();
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < n; i++) {
        set.add(io.nextInt());
    }

    int m = set.size(), idx = 0;
    int[] a = new int[m];
    for (var x : set) {
        a[idx++] = x;
    }

    int ans = 1;
    for (int i = 0, j = 1; j < m; j++) {
        while (a[j] - a[i] >= n) {
            i++;
        }
        ans = Math.max(ans, j - i + 1);
    }
    io.println(ans);
}

Physical Education Lesson

题目

输入两个整数 \(n\) 和 \(x\)，求 \(k\) 的个数，使得对于编号为 \(1\) 到 \(k\) 的位置，满足第 \(n\) 个位置的编号为 \(x\)。第 \(n\) 个位置是按往返来计算的，例如 \(1,2,\dots,k-1,k,k-1,\dots,2,1\)，第 \(1\) 和 \(1+2k-2\) 个位置的编号都为 \(1\)。当 \(k>1\) 时，编号循环的周期就是 \(2k-2\)。题目限制 \(k>1\)。

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

思路

\(k\) 必须满足 \(k\geq x\)，同时 \((2k-2)\cdot t+x=n\) 或 \((2k-2)\cdot t+k+k-x=n\)，变形得到 \(n-x=2\cdot(k-1)\cdot t\) 或 \(n+x-2=2\cdot(k-1)\cdot(t+1)\)。求 \(k\) 的个数，可以首先求出 \(\frac{n-x}{2}\) 和 \(\frac{n+x-2}{2}\) 的约数，约数加一就是满足等式的 \(k\) 值，最后限制 \(k\geq x\)，得到答案。其实也可以不使用集合去重，只需要特判 \(x=1\) 和 \(k=x\) 的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void solve() {
    int n = io.nextInt(), x = io.nextInt();
    Set<Integer> set = new HashSet<>();
    calc(n - x, x, set);
    calc(n + x - 2, x, set);
    io.println(set.size());
}

private static void calc(int x, int y, Set<Integer> set) {
    if (x % 2 != 0) {
        return;
    }
    x /= 2;
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            if (i + 1 >= y) {
                set.add(i + 1);
            }
            if (x / i != i && x / i + 1 >= y) {
                set.add(x / i + 1);
            }
        }
    }
}

Lonely Mountain Dungeons

题目

输入三个整数 \(n,b,x\)，以及长度为 \(n\) 的数组 \(c\)。有 \(n\) 种生物，每种生物的数量为 \(c_{i}\)。你需要将所有生物分为 \(k\) 组，位于不同组的每对同种生物会使总分增加 \(b\)，同时总分会减少 \((k-1)\cdot x\)。输出能够得到的最大分数。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)，\(1\leq b\leq 10^{6}\)，\(0\leq x\leq 10^{9}\)，\(1\leq c_{i}\leq 2\cdot 10^{5}\)，\(\sum_{i=1}^{n}c_{i}\leq 2\cdot 10^{5}\)。

思路

首先需要知道，对于某种生物 \(i\) 和固定的 \(k\)，将 \(c_{i}\) 尽量平均分配是最优的，不过我也不知道该怎么证明。当 \(k>c_{i}\) 时，得分总是为 \(C_{c_{i}}^{2}\cdot y^{2}\)。当 \(k\leq c_{i}\) 时，就需要将 \(c_{i}\) 分为，\(c_{i}\bmod k\) 组包含 \(y=\lceil\frac{c_{i}}{k}\rceil\) 个该种生物，\(k-c_{i}\bmod k\) 组包含 \(y^{\prime}=\lfloor\frac{c_{i}}{k}\rfloor\) 个该种生物。得分为：

根据以上讨论，很容想到暴力枚举组数 \(k\)，然后内层循环计算该组数下的最大得分，总时间复杂度为 \(O(\max(c_{i})\cdot n)\)。由于题目限制 \(\sum_{i=1}^{n}c_{i}\leq 2\cdot 10^{5}\)，我们可以预处理得到所有 \(c_{i}\) 在组数为 \([1,c_{i}]\) 下的最大得分之和，从而可以将暴力枚举的内循环优化为 \(O(1)\) 时间复杂度。

代码

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

public static void solve() {
    int n = io.nextInt(), b = io.nextInt(), x = io.nextInt();

    int m = 0;
    int[] c = new int[n];
    for (int i = 0; i < n; i++) {
        c[i] = io.nextInt();
        m = Math.max(m, c[i]);
    }

    long[] f = new long[m + 1];
    long[] g = new long[m + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= c[i]; j++) {
            f[j] += calc(c[i], j);
        }
        g[c[i]] += calc(c[i], c[i]);
    }

    long ans = 0L;
    for (int i = 1; i <= m; i++) {
        ans = Math.max(ans, (f[i] + g[i - 1]) * b - (long) (i - 1) * x);
        g[i] += g[i - 1];
    }
    io.println(ans);
}

private static long calc(int n, int k) {
    int a = n / k, b = n % k;
    long res = (long) (k - b) * (k - b - 1) / 2 * a * a;
    res += (long) b * (b - 1) / 2 * (a + 1) * (a + 1);
    res += (long) (k - b) * b * a * (a + 1);
    return res;
}

给定操作次数内使剩余元素的或值最小

题目

输入长度为 \(n\) 的整数数组 \(nums\) 和整数 \(k\)，输出执行至多 \(k\) 次操作之后，将数组中所有剩余元素按位或的最小值。每次操作可以选择一个下标 \(i\)，满足 \(0\leq i<n\)，将 \(nums[i]\) 和 \(nums[i+1]\) 替换为它们按位与的结果。注意，是两个数替换为一个数。

数据范围：\(1\leq n\leq 10^{5}\)，\(0\leq nums[i]<2^{30}\)，\(0\leq k< n\)。

思路

要使按位或的结果最小，肯定是从高位到低位消除。但是高位消除的方式会影响低位消除的方式，它们是相关的，不能单独计算每一位的操作次数。如果暴力枚举所有位的组合，会有 \(2^{30}\) 种情况，肯定会超时。如何计算？其实，只需要考虑从高位到低位的组合方式。从高位开始，能够消除的位总是应该被消除，然后判断加上更低的一位是否能被消除（保留相关性），如果不能，则该低位就永远不会被消除，以此类推。那么如何判断某个位的组合是否能被消除？从前往后遍历数组，贪心的将数组分割为若干按位与结果为 0 的子数组（假设为 \(m\)），则当前组合消除所需的操作次数为 \(n-m\)。具体可以看下灵茶山的题解和小羊的题解。

移除后集合的最多元素数

题目

输入长度为偶数 \(n\) 的数组 \(a\) 和 \(b\)，输出从 \(a\) 和 \(b\) 中分别选择一半元素构成的集合的最大大小。

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

思路

要使集合尽可能大，肯定优先选择除 \(a\) 和 \(b\) 交集以外的元素，假设分别为 \(x\) 和 \(y\)，则可以选择 \(s=\min(x,\frac{n}{2})+\min(y,\frac{n}{2})\) 个不同元素。此时还有 \(n-s\) 个元素待选，假设交集的大小为 \(z\)，则答案为 \(s+\min(n-s,z)\)。

执行操作后的最大分割数量

题目

输入长度为 \(n\) 的字符串 \(s\) 和一个整数 \(k\)，输出至多改变一个字符时，执行操作能够得到的最大分割数。每次操作可以分割 \(s\) 的最多包含 \(k\) 个不同字符的最长前缀。

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

思路

首先，很容易想到暴力做法，枚举每个位置的所有改变情况，然后通过遍历求分割数，时间复杂度为 \(O(n^{2}|\Sigma|\log{|\Sigma|})\)。显然，可以优化的部分就是最后遍历求分割数的 \(O(n\log{|\Sigma|})\)。然后观察修改字符相比不修改字符会产生什么变化，可以发现修改字符所在的分割段的长度可能发生变化，而前缀的分割数是固定的。可以想到预处理原字符串每个位置 \(i\) 的后缀分割数，问题就剩下如何快速求得修改字符所在段的右端点。由于字符数随着长度的增加而增加，所以可以通过二分求得该段的右端点，这还需要花费 \(O(n|\Sigma|)\) 的时间提前预处理出字符数的前缀和。最后，分割数为前缀 + 中间 + 后缀的段数。代码实现时，还有很多其他细节需要注意，强烈建议自己实现一下。