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

Grouping Increases

题目

输入长度为 \(n\) 的数组 \(a\)，将数组 \(a\) 分割为两个子序列（可能为空），输出两个子序列中满足 \(b_{i}<b_{i+1}\) 的下标 \(i\) 的数量之和的最小值。

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

思路

贪心。假设将数组 \(a\) 分割为数组 \(b\) 和 \(c\)，从空数组开始，将 \(a\) 中的元素添加到 \(b\) 或 \(c\)。假设 \(b\) 和 \(c\) 的最后一个元素分别为 \(x\) 和 \(y\)（\(x\leq y\)），如果 \(a_{i}\leq x\) 或 \(a_{i}>y\)，则将 \(a_{i}\) 添加到 \(b\)，否则添加到 \(c\)。

Two Divisors

题目

输入两个整数 \(a\) 和 \(b\)，它们是 \(x\) 的最大除数，满足 \(1\leq a\leq b<x\)。输出 \(x\) 的值。

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

思路

首先 \(b\) 肯定等于 \(x\) 除以最小的质因数，然后 \(a\) 可能等于 \(x\) 除以两次最小的质因数，或者等于 \(x\) 除以次小的质因数。这可以根据 \(b\bmod a\) 是否等于 \(0\) 来确定，如果是则 \(x=b\times\frac{b}{a}\)，否则 \(x=b\times\frac{a}{\gcd(a,b)}\)。

Mathematical Problem

题目

输入奇数 \(n\)，输出 \(n\) 个不同的数，它们都是整数的平方，并且 \(n\) 个数的数位构成的多重集合都相同。

数据范围：\(1\leq n\leq 99\)。

思路

只需要在 \(169,196,961\) 的基础上添加 \(0\) 就可以构造出满足条件的 \(n\) 个数，方法直接看题解或者代码吧，反正 \(169\) 和 \(961\) 这两个数比较特殊，真不知道大家怎么做出来的。