本文最后更新于2021年10月4日，已超过 7 个月没更新！
👩🏫每日一题·夏季
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);
}
}
}
