2023年第六届传智杯程序设计挑战赛（个人赛）B组赛后复盘

传智杯赛后复盘

大家好我是寸铁👊
2023年第六届传智杯程序设计挑战赛（个人赛）B组赛后复盘
喜欢的小伙伴可以点点关注 💝

1. 字符串拼接

细节：一定要清楚nextLine()和next()的区别
nextLine()是遇到回车会停下来
next是遇到空格会停下来
很明显这里必须得选nextLine()
踩坑实录…

java">import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();
        StringBuffer s1 = new StringBuffer(str1);
        StringBuffer s2 = new StringBuffer(str2);
		 s1.append(s2);
        System.out.println(s1);
    }
}

2. 差值

java">import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象用于接收输入
        Scanner in = new Scanner(System.in);

        // 输入战士数量
        int n = in.nextInt();
        int[] strengths = new int[n];
        for (int i = 0; i < n; i++) {
            strengths[i] = in.nextInt();
        }

        // 对战士战斗力进行排序 以便比较相邻两位战士的战力之差
        Arrays.sort(strengths);

        // 初始化最小差值为一个较大的值
        int minDif = 0x3f3f3f3f;

        // 枚举相邻两名战士战斗力之差的最小值 
        for (int i = 0; i < n - 1; i++) {
            int currentDif = strengths[i + 1] - strengths[i];
            //更新战力之差的最小值
            if (currentDif < minDif) {
                minDif = currentDif;
            }
        }
        System.out.println(minDif);
        in.close();
    }
}

3. . 红色和紫色

很有趣的一题，奇数和偶数的区别

java">import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        //方格数量为偶数则yukari赢 因为yukari总会染成紫色
        if(n % 2 == 0 || m % 2 == 0){
            System.out.println("yukari");
        }
        else{
        //方格数量为奇数则akai赢 因为最后akai不能染成紫色    
            System.out.println("akai");
        }
    }
}

4. abb

dp 举出后面相同的字符就+1

java">import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            String str = in.next();
            int[][] dp = new int[n + 1][26];
            Arrays.fill(dp[n], 0);
            for (int i = n - 1; i >= 1; i--) {
                char ch = str.charAt(i);
                for (int j = 0; j < 26; j++) {
                    if (ch - 'a' == j) {
                        dp[i][j] = dp[i + 1][j] + 1;
                    } else {
                        dp[i][j] = dp[i + 1][j];
                    }
                }
            }
            long res = 0;
            for (int i = 1; i <= n; i++) {
                char c = str.charAt(i - 1);
                for (int j = 0; j < 26; j++) {
                    if (c - 'a' != j && dp[i][j] >= 2) {
                        res += dp[i][j] * (dp[i][j] - 1) / 2;
                    }
                }
            }
            System.out.println(res);
        }
    }
}

5. kotorti和素因子

dfs + 质数筛

java">import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    static final int maxn = 1005;
    static final int INF = 0x3f3f3f3f;

    static int n, m, sum, min_, X;
    static ArrayList<Integer>[] e = new ArrayList[maxn];
    static boolean[] vis = new boolean[maxn];
    static boolean flag;

    static boolean isPrime(int n) {
        if (n == 1)
            return false;
        for (int i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    static void prime(int n, int x) {
        for (int i = 1; i <= Math.floor(Math.sqrt(n)); i++) {
            if (n % i == 0) {
                if (isPrime(i))
                    e[x].add(i);
                if (i * i != n && isPrime(n / i))
                    e[x].add(n / i);
            }
        }
    }

    static void dfs(int y) {
        if (y == X) {
            flag = true;
            min_ = Math.min(min_, sum);
            return;
        }
        for (int i = 0; i < e[y].size(); i++) {
            if (!vis[e[y].get(i)]) {
                sum += e[y].get(i);
                vis[e[y].get(i)] = true;
                dfs(y + 1);
                vis[e[y].get(i)] = false;
                sum -= e[y].get(i);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        for (int i = 0; i < maxn; i++) {
            e[i] = new ArrayList<>();
        }

        X = 0;
        for (int i = 0; i < n; i++) {
            m = scanner.nextInt();
            prime(m, X++);
        }

        min_ = INF;
        dfs(0);

        if (flag)
            System.out.println(min_);
        else
            System.out.println(-1);
    }
}

6. 红和蓝

赛后补题

java">import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int N = 2 * 100000 + 10;
    static int[] e = new int[N];
    static int[] h = new int[N];
    static int[] ne = new int[N];
    static int idx;

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
        e[idx] = a;
        ne[idx] = h[b];
        h[b] = idx++;
    }

    static int n;
    static int cnt;
    static int[] colour = new int[N];
    static boolean flag;
    
    static void dfs1(int x, int fa) {
        int son = 0;
        for (int i = h[x]; i != -1; i = ne[i]) {
            int ver = e[i];
            if (ver == fa)
                continue;
            son++;
            dfs1(ver, x);
        }
        if (son == 0 || colour[x] == 0) {
            if (colour[fa] != 0 || fa == 0) {
                flag = true;
                return;
            }
            colour[x] = colour[fa] = ++cnt;
        }
    }

    static int[] clo = new int[N];
    
    static void dfs2(int x, int fa) {
        for (int i = h[x]; i != -1; i = ne[i]) {
            int ver = e[i];
            if (ver == fa)
                continue;
            if (colour[ver] == colour[x])
                clo[ver] = clo[x];
            else
                clo[ver] = clo[x] ^ 1;
            dfs2(ver, x);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        Arrays.fill(h, -1);
        for (int i = 1; i < n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            add(x, y);
        }
        dfs1(1, 0);
        if (flag) {
            System.out.println("-1");
            return;
        }
        dfs2(1, 0);
        for (int i = 1; i <= n; i++)
            System.out.print(clo[i] != 0 ? "B" : "R");
    }
}

总结

ACM模式，大部分题目是从牛客题库、寒假训练营抽出来的，Dfs、DP、图论、质数筛的混合考察比较多，平时多练习多debug
ACM注意罚时的重要性，考虑一些细节不对，提交报错则罚时严重。
拿到题目，先把题目全部扫一遍，不要一股脑只是做题，应该先把题目先过一遍，确定考点后，由易入难。
确保会的都写对，不会的尝试一下，多debug