👨‍💻 AcWing·在线竞赛

🏆 第 1 场周赛

3. 数字移动

🎖️ 并查集

import java.util.*;

public class Main {
    static int[] p;
    static int[] size;
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            p = new int[n + 1];
            size = new int[n + 1];
            for (int i = 1; i <= n; ++ i) {
                p[i] = i;
                size[i] = 1;
            }

            for (int i = 1; i <= n; ++ i) {
                int j = sc.nextInt();
                if (find(i) != find(j)) {
                    size[find(j)] += size[find(i)];
                    p[find(i)] = find(j);
                }
            }
            for (int i = 1; i <= n; ++ i) System.out.print(size[find(i)] + " ");
            System.out.println();
        }
    }

    private static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]); 
        return p[x];
    }
}

类似题型：算法基础课 - 连通块中点的数量

🏆 第 2 场热身赛

2. 双端队列

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Map<Integer, Integer> map = new HashMap<>();
        int left = 0, right = -1;
        int q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; ++ i) {
            String[] s = br.readLine().split(" ");
            int num = Integer.parseInt(s[1]);
            if ("L".equals(s[0])) {
                map.put(num, -- left);
            }
            else if ("R".equals(s[0])) {
                map.put(num, ++ right);
            }
            else {
                int idx = map.get(num);
                bw.write(Math.min(idx - left, right - idx) + "\n");
            }
        }
        br.close();
        bw.close();
    }
}

3. 最长非递减子序列⭐

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        String[] s = br.readLine().split(" ");
        int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
        for (int i = 0; i < s.length; ++ i) {
            if ("1".equals(s[i])) {
                s1 ++;
                s3 = Math.max(s3 + 1, s2 + 1);
            } else {
                s2 = Math.max(s1 + 1, s2 + 1);
                s4 = Math.max(s3 + 1, s4 + 1);
            }
        }
        bw.write(Math.max(s3, s4) + "\n");
        bw.close();
        br.close();
     }
}

🍹y总笔记🍹