🤖夜猫子场-Div4 Round928

Codeforces Div4 Round928※

传送门

难度适中，AC 4题。

A. https://codeforces.com/contest/1926/problem/A

思路：统计AB数量。

public class A {

    // 简单计数就行
    public static void solve() throws IOException {
        String s = in.nextLine();
        int cnt_a = 0, cnt_b = 0;
        for (char c : s.toCharArray()) {
            if (c == 'A') cnt_a++;
            else cnt_b++;
        }
        out.println(cnt_a > cnt_b ? "A" : "B");
    }

    static boolean MULTI_CASE = true;
    public static void main(String[] args) throws Exception {
        int T = MULTI_CASE ? in.nextInt() : 1;
        while (T-- > 0) {
            solve();
        }
        out.close();
    }
}

B. https://codeforces.com/contest/1926/problem/B

思路：统计存在1的行中，1的个数cnt，然后把cnt丢到set里面，最后判断set.size()是否等于1。

时间复杂度：O(N^2)

public class B {

    // 统计每行1的个数丢到set里面，最后判断set.size()是否等于1就行
    public static void solve() throws IOException {
        int n = in.nextInt();
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) {
            String s = in.nextLine();
            ss[i] = s;
        }
        var set = new HashSet<Integer>();
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (ss[i].charAt(j) == '1') {
                    cnt++;
                }
            }
            if (cnt > 0) set.add(cnt);
        }
        if (set.size() != 1) {
            out.println("TRIANGLE");
        } else {
            out.println("SQUARE");
        }
    }

    static boolean MULTI_CASE = true;
    public static void main(String[] args) throws Exception {
        int T = MULTI_CASE ? in.nextInt() : 1;
        while (T-- > 0) {
            solve();
        }
        out.close();
    }
}

C. https://codeforces.com/contest/1926/problem/C

思路：递推预处理出2e5内数字的数位和，然后询问即可。

时间复杂度：O(2e5)

public class C {
    // 预处理出1-2e5的所有数位和 递推式：dp[i] = dp[i-1] + f(i)
    static int MAX = (int) 2e5;
    static long[] dp = new long[MAX + 10];
    static {
        for (int i = 1; i <= MAX; i++) {
            dp[i] = dp[i-1] + f(i);
        }
    }

    static int f(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x = x / 10;
        }
        return s;
    }

    public static void solve() throws IOException {
        int n = in.nextInt();
        out.println(dp[n]);
    }

    static boolean MULTI_CASE = true;
    public static void main(String[] args) throws Exception {
        int T = MULTI_CASE ? in.nextInt() : 1;
        while (T-- > 0) {
            solve();
        }
        out.close();
    }
}

D. https://codeforces.com/contest/1926/problem/D

思路：a，b如果想在同一组，那么必然满足INF 异或 a = b 或者 b 异或 INF = a，并且每个组大小只能是2，因为 a ^ INF = b，后面再出现a的话就存在 a ^ INF = b，但是这个b已经跟前一个a一组了，所以当前这个a只能自己一组。遍历的时候用map计数，判断即可。

时间复杂度：O(N)

public class D {
    // 两数之和思想：a，b如果想在同一组，那么满足 INF ^ b = a
    // map计数，当前数x， map如果存在 INF ^ x，并且 cnt[INF^x] > 0的，那么可以组合为1组，否则必须单独一组
    static final int INF = Integer.MAX_VALUE;
    public static void solve() throws IOException {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = in.nextInt();
        var map = new HashMap<Integer, Integer>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(INF ^ a[i])) {
                int cnt = map.get(INF ^ a[i]);
                if (cnt > 0) { // 可以合并为1组
                    map.merge(INF ^ a[i], -1, Integer::sum); // INF ^ a[i]的使用次数-1
                    map.put(a[i], 0); // 当前a[i]不能被后面的某个数使用，因为存在 a b a这种case
                } else {
                    map.merge(a[i], 1, Integer::sum);
                    ans++;
                }
            } else {
                map.merge(a[i], 1, Integer::sum);
                ans++;
            }
        }
        out.println(ans);
    }

    static boolean MULTI_CASE = true;
    public static void main(String[] args) throws Exception {
        int T = MULTI_CASE ? in.nextInt() : 1;
        while (T-- > 0) {
            solve();
        }
        out.close();
    }
}