Contestant. Rank 4776. Rating -20 (+30 -50).

A. Parallel Projection

题意

给定一个长方体，在长方体的顶部和底部各取一个点，一只蚂蚁只能在平面上向平行于边的方向移动，求出蚂蚁从一个点移动到另一个点的最短路径。

思路

从四个方向分别模拟一下求最小值即可。

时间复杂度：\(O(1)\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t -- > 0){
            int w = scanner.nextInt(), d = scanner.nextInt(), h = scanner.nextInt();
            int a = scanner.nextInt(), b = scanner.nextInt(), f = scanner.nextInt(), g = scanner.nextInt();
            int p1 = Math.min(a + f + Math.abs(g - b), b + g + Math.abs(f - a));
            a = w - a;
            b = d - b;
            f = w - f;
            g = d - g;
            int p2 = Math.min(a + f + Math.abs(g - b), b + g + Math.abs(f - a));
            System.out.println(h + Math.min(p1, p2));
        }
    }
}

还是用蚂蚁理解更加经典（（

B. Going to the Cinema

题意

给定数组 \(a\)，对于任意 \(i\)，提出一个要求：“我只在 不算上我的前提下 至少有 \(a_i\) 个人陪我一起去 的前提下去电影院，否则我会难过。”

注意考虑逆否命题：“我不去电影院，而且只有不到 \(a_i\) 个人抛下我去电影院，我依然是开心的，否则我也会难过。”

输出所有不让任何人伤心的安排的总数。

思路

首先，显然我们一定得让 \(a_i=0\) 的人全都去电影院，不然逆否命题一定不成立。

接着，我们遍历剩下按升序排序的 \(a_i\)，同理找出必须去的人，在找出第一个不一定要去的人的时候停止遍历。

然后，我们遍历后面可以不选上的人，并在选上后判断后者是否必须去。

最后，所有可以不选上的人的个数即为答案，因为若在递增序列里间隔选人，会导致命题不成立。

时间复杂度：\(O(n)\)

对应AC代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = scanner.nextInt();
            Arrays.sort(a);
            int c = 0, i = 0, ans = 0;
            for(;i<n;i++){
                if(a[i] == 0) c ++;
                else if(a[i] <= c) c ++;
                else break;
            }
            ans++;
            while (i++ < n) {
                c++;
                if (a[i] <= c) {
                    ans++;
                    while (i < n && a[i] <= c) {
                        i++;
                        c++;
                    }
                }
            }
            System.out.println(ans);
        }
    }
}

云里雾里

C. Equal Frequencies

题意

给定一个字符串 \(s\)，定义一次操作为替换 \(s_i\) 为任意其他字母，输出操作数最少的结果，使结果中所有字母出现的次数均相同。

思路

考虑到小写字母只有 \(26\) 个，我们不妨枚举所有可能的段数，找出操作数最少的情况然后输出即可。

如何判断操作数最少呢？对于每个字母 \(c\)，我们不难发现：\(\min(\frac{n}{k},freq_c)\) 即为当前需要保留的数量。因此，去除保留的数量，剩余即为操作数。

确定段数之后，我们先将字符串中各个字母按照出现次数降序排序，然后从头开始遍历每一个字母，若字母数量过多，那么将多出来的位置留空，如果过少，那么在留空的位置填上缺少的字母。最后将序列输出即可。

时间复杂度：\(O(n^2)\)

对应AC代码

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt();
            char[] o = scanner.next().toCharArray();
            List<Pair<Integer, List<Integer>>> f = new ArrayList<>();
            for(int i=0;i<26;i++) f.add(new Pair<>(i, new ArrayList<>()));
            for(int i=0;i<n;i++) f.get(o[i] - 'a').B.add(i);
            f.sort(Comparator.comparingInt(o1 -> -o1.B.size()));
            int best = 0, cnt = 1, cur;
            for(int i=1;i<=26;i++){
                if(n % i > 0) continue;
                cur = 0;
                for(int j=0;j<i;j++) cur += Math.min(n / i, f.get(j).B.size());
                if(best < cur){
                    best = cur;
                    cnt = i;
                }
            }
            System.out.println(n - best);
            List<Integer> extra = new ArrayList<>();
            char[] res = new char[n];
            for(int i=0;i<cnt;i++){
                for(int j=0;j<n/cnt;j++){
                    if(j < f.get(i).B.size()){
                        res[f.get(i).B.get(j)] = (char) ('a' + f.get(i).A);
                    }else{
                        extra.add(f.get(i).A);
                    }
                }
            }
            int p = 0;
            for(int i=0;i<n;i++){
                System.out.printf("%c", res[i] == 0 ? (char) ('a' + extra.get(p ++)) : res[i]);
            }
            System.out.println();
        }
    }

    //实现cpp里的pair 此处略去
    //public static class Pair<A, B>{}

}

没想到暴力直接取段数

D. Many Perfect Squares

题意

给定数组 \(a\)，输出将整个数组加上任意非负数 \(x\) 后完全平方数的最多个数。

思路

首先，答案绝对是 \(\geq1\) 的，那么我们来考虑 \(> 1\) 的情况，也就是在该情况下枚举所有 \(a_i,a_j\)，满足 \(a_i+x=p^2,a_j+x=q^2\)，然后再枚举所有数，统计完全平方数个数即可。

那么我们来考虑下如何枚举 \(x\)：

显然，\(a_j - a_i = q^2 - p^2 = (q - p)(q + p)\)，那么 \(q-p\) 即为 \(a_j-a_i\) 的因数，因为数据范围不大，直接暴力枚举所有因数是可行的。

设因数为 \(d\)，我们可以得到下面的式子

\(\begin{cases} q - p = d \\ q + p = \frac{a_j - a_i}{d} \end{cases}\)

继续化简，得到

\(\begin{cases} p = \frac{1}{2}(\frac{a_j - a_i}{d} - d) \\ q = \frac{1}{2}(\frac{a_j - a_i}{d} + d) \\ \end{cases}\)

也就是说，只要括号内的式子是偶数，那么 \(d\) 即为一种可行解。

时间复杂度：\(O(n^2f(x)),f(x)为差值的因数个数\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

#define int long long

int a[60];

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i=0;i<n;i++) cin >> a[i];
        int ans = 1;
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++) {
                int d = a[j] - a[i], x;
                for (int p=1;p<=d/p;p++) {
                    if(d % p == 0){
                        if((d / p - p) % 2 == 1 || (d / p + p) % 2 == 1) continue;
                        x = ((d / p - p) / 2) * ((d / p - p) / 2) - a[i];
                        if(x < 0) continue;
                        int cnt = 0;
                        for(int e=0;e<n;e++){
                            int s = floor(sqrt(a[e] + x));
                            if(s * s == a[e] + x) cnt ++;
                        }
                        ans = max(ans, cnt);
                    }
                }
            }
        cout << ans << '\n';
    }
}

好一个暴力枚举