👩‍🏫每日一题·夏季

3732. 矩阵复原

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

public class Main{
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while (t -- > 0) {
            String[] s = br.readLine().split(" ");
            int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n; ++ i) {
                s = br.readLine().split(" ");
                for (int j = 0; j < m; ++ j)
                    map.put(Integer.parseInt(s[j]), j); // key为元素的值 value为对应的列
            }
            int[][] ans = new int[n][m];
            int p;
            for (int i = 0; i < m; ++ i) {
                s = br.readLine().split(" ");
                p = map.get(Integer.parseInt(s[0]));
                for (int j = 0; j < n; ++ j)
                    ans[j][p] = Integer.parseInt(s[j]);
            }

            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < m; ++ j)
                    bw.write(ans[i][j] + " ");
                bw.write("\n");
            }
        }
        br.close();
        bw.close();
    }
}

3731. 序列凑零

🧩 思维题

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
            int[] b = work(a);
            for (int i = 0; i < n; ++ i)
                System.out.print(b[i] + " ");
            System.out.println();
        }
    }

    // 令
    // b[i] = -a[i + 1];
    // b[i + 1] = a[i];
    // 即可
    private static int[] work(int[] a) {
        int n = a.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i += 2) {
            b[i] = -a[i + 1];
            b[i + 1] = a[i];
        }
        return b;
    }
}

3730. 寻找序列

import java.util.*;

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

            if (a[n - 1] != p[n - 2] && a[n - 1] != p[0]) p[n - 1] = a[n - 1];
            else if (b[n - 1] != p[n - 2] && b[n - 1] != p[0]) p[n - 1] = b[n - 1];
            else p[n - 1] = c[n - 1];

            for (int i = 0; i < n; ++ i) {
                System.out.print(p[i] + " ");
            }
            System.out.println();
        }
    }
}

3725. 卖罐头

🧩 思维题

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            if (r < 2 * l) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

3729. 改变数组元素

🧩 差分

import java.util.*;

public class Main {
    static int[] p;

    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 + 2];
            for (int i = 1; i <= n; ++ i) {
                int x = sc.nextInt();
                insert(Math.max(1, i - x + 1), i, 1);
            }
            for (int i = 1; i <= n; ++ i) {
                p[i] += p[i - 1];
                if (p[i] == 0) System.out.print("0 ");
                else System.out.print("1 ");
            }
            System.out.println();
        }
    }

    private static void insert (int l, int r, int x) {
        p[l] += x;
        p[r + 1] -= x;
    }
}

3720. 数组重排

🧩 枚举

import java.util.*;

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

            boolean flag = true;
            for (int i = 0; i < n; ++ i) {
                if (a[i] + b[n - 1 - i] > x) {
                    flag = false;
                    break;
                }
            }
            System.out.println(flag ? "Yes" : "No");
        }
    }
}

3711. 方格涂色

🧩 枚举

import java.util.*;

public class Main{
    static int n;
    static int u, r, p, l;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            n = sc.nextInt();
            u = sc.nextInt(); r = sc.nextInt();
            p = sc.nextInt(); l = sc.nextInt();
            boolean flag = false;
            for (int i = 0; i < 1 << 4; ++ i) {
                if (check(i)) {
                    flag = true;
                    break;
                }
            }
            System.out.println(flag ? "YES" : "NO");
        }
    }

    private static boolean check(int state) {
        int a = (state >> 0) & 1, b = (state >> 1) & 1;
        int c = (state >> 2) & 1, d = (state >> 3) & 1;
        if (!(a + b <= u && u <= a + b + n - 2)) return false;
        if (!(b + c <= r && r <= b + c + n - 2)) return false;
        if (!(c + d <= p && p <= c + d + n - 2)) return false;
        if (!(d + a <= l && l <= d + a + n - 2)) return false;
        return true;
    }
}

3705. 子集mex值

import java.util.*;

public class Main{
    public static void main (String[] args) {
        int N = 100;
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            boolean[] a = new boolean[N + 1];
            boolean[] b = new boolean[N + 1];
            for (int i = 0; i < n; ++ i) {
                int num = sc.nextInt();
                if (a[num]) b[num] = true;
                else a[num] = true;
            }
            int x = 0, y = 0;
            for (x = 0; x <= N && a[x]; ++ x);
            for (y = 0; y <= N && b[y]; ++ y);
            System.out.println(x + y);
        }
    }
}

3697. 回文子序列

🧩 注意子串和子序列的区别

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t =  sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
            if (work(a)) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static boolean work(int[] a) {
        int n = a.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++ i) {
            int idx = map.getOrDefault(a[i], -1);
            if (idx != -1) {
                if (i - idx >= 2) {
                    return true;
                }
            } else map.put(a[i], i);
        }
        return false;
    }
}

3686. 移动序列

import java.util.*;

// 移动的次数就是第一个 1 和最后 1 个 1 中间 0 的个数
public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            int cnt1 = 0; // 1 的个数
            for (int i = 0; i < n; ++ i) {
                a[i] = sc.nextInt();
                if (a[i] == 1) ++ cnt1;
            }
            int i = 0, j = n - 1;
            while (a[i] == 0) ++ i;
            while (a[j] == 0) -- j;
            System.out.println(j - i + 1 - cnt1);
        }
    }
}

3682. 素数矩阵

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < n; ++ j) {
                    if (i == j || j == (i + 1) % n)
                        System.out.print("1 ");
                    else 
                        System.out.print("0 ");
                }
                System.out.println();
            }
        }
    }
}

3664. 数组补全

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt(), p = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
        int sum = 0, lt = 0, ge = 0; // lt为小于中位数y的数, ge为大于等于y的数
        for (int i = 0; i < k; ++ i) {
            int num = sc.nextInt();
            sum += num;
            if (num < y) lt ++;
            else ge ++;
        }

        int r = Math.max(n / 2 + 1, ge), l = n - r;
        if (lt > l)
            System.out.println("-1");
        else {
            sum += (l - lt) * 1 + (r - ge) * y;
            if (sum > x) System.out.println("-1");
            else {
                for (int i = lt; i < l; ++ i)
                    System.out.print("1 ");
                for (int i = ge; i < r; ++ i)
                    System.out.print(y + " ");
            }
        }
    }
}

3663. 打印数字菱形

import java.util.*;

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

        // 根据坐标
        for (int i = 0; i < n * 2 + 1; i ++ ) {
            for (int j = 0; j < n * 2 + 1; j ++ ) {
                int d = Math.abs(i - n) + Math.abs(j - n);
                // 当(i, j) 和 (n, n) 坐标差之和大于 n 即为打印域外，应打空格
                if (d > n) System.out.print("  ");
                else System.out.print(n - d + " ");
            }
            System.out.println();
        }
    }
}

3655. 楼层

🧩 上取整公式

import java.util.*;

// a / b 上取整数 = (a + b - 1) / b 下取整
public class Main{
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), x = sc.nextInt();
            System.out.println(n <= 2 ? 1 : (n - 2 + x - 1) / x + 1);
        }
    }
}

3646. 分水果

🧩 位枚举

import java.util.*;

public class Main {
    static int[][] p = {
        {0, 0, 1},
        {0, 1, 0},
        {1, 0, 0},
        {0, 1, 1},
        {1, 0, 1},
        {1, 1, 0},
        {1, 1, 1}
    };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            int ans = 0;
            for (int i = 0; i < 1 << 7; ++ i) {
                int sx = 0, sy = 0, sz = 0;
                int cnt = 0;
                for (int j = 0; j < 7; ++ j) {
                    if (((i >> j) & 1) == 1) {
                        sx += p[j][0];
                        sy += p[j][1];
                        sz += p[j][2];
                        ++ cnt;
                    }
                    if (sx <= x && sy <= y && sz <= z) {
                        ans = Math.max(ans, cnt);
                    }
                }
            }
            System.out.println(ans);
        }
    }
}

3636. 数组延伸

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt(), x = sc.nextInt();
            long sum = 0, psum = 0, cnt = Long.MAX_VALUE;
            for (int i = 0; i < n; ++ i) {
                int num = sc.nextInt();
                sum += num;

                int c = 1, tmp = num;
                while (tmp % x == 0) {
                    ++ c;
                    tmp /= x;
                }
                if (c < cnt) {
                    cnt = c;
                    psum = sum - num;
                }
            }
            System.out.println((long)(sum * cnt + psum));
        }
    }
}

3624. 三值字符串

🧩 双指针

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 t = Integer.parseInt(br.readLine());
        while (t -- > 0) {
            String s = br.readLine();
            int[] cur = {-1, -1, -1};
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < s.length(); ++ i) {
                int num = s.charAt(i) - '0';
                if (num >= 1 && num <= 3) {
                    cur[num - 1] = i;
                }
                if (cur[0] != -1 && cur[1] != -1 && cur[2] != -1) {
                    ans = Math.min(ans, Arrays.stream(cur).max().getAsInt() - Arrays.stream(cur).min().getAsInt() + 1);
                }
            }
            System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
        }
    }
}