👩🏫每日一题·夏季
数组重排
🧩 枚举
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);
}
}
}
3617. 子矩形计数⭐
🧩 差分
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
int[] b = new int[m];
int[] s1 = new int[n + 2];
int[] s2 = new int[m + 2];
for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
for (int i = 0; i < m; ++ i) b[i] = sc.nextInt();
work(a, s1);
work(b, s2);
long ans = 0;
for (int i = 1; i <= n; ++ i) {
if (k % i == 0) {
int j = k / i;
if (j <= m) ans += s1[i] * s2[j];
}
}
System.out.println(ans);
}
public static void work (int[] nums, int[] s) {
int n = nums.length;
for (int i = 0, j = 0; i < n; ++ i) {
if (nums[i] != 0) {
++ j;
s[1] ++;
s[j + 1] --;
} else j = 0;
}
for (int i = 1; i <= n; ++ i)
s[i] += s[i - 1];
}
}
3583. 整数分组⭐
🧩 动态规划
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; ++ i) a[i] = sc.nextInt();
Arrays.sort(a);
// f[i][j] 表示在前[1, i]中选 j 组的最大选择数
int[][] f = new int[n + 1][m + 1];
for (int i = 1, k = 1; i <= n; ++ i) {
while (a[i] - a[k] > 5) ++ k;
for (int j = 1; j <= m; ++ j) {
f[i][j] = Math.max(f[i - 1][j], f[k - 1][j - 1] + i - k + 1);
}
}
System.out.println(f[n][m]);
}
}
🍹y总笔记🍹
3580. 整数配对🥰
🧩 贪心 证明是重点
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0;i < n; ++ i) nums[i] = sc.nextInt();
Arrays.sort(nums);
int ans = 0;
for (int i = 1; i < n; i += 2) {
ans += nums[i] - nums[i - 1];
}
System.out.println(ans);
}
}
3574. 乘积数量⭐
🧩 前缀和
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// Positive and Negative
long rp = 0, rn = 0;
int sp = 1, sn = 0, s = 1;
for (int i = 1; i <= n; ++ i) {
int a = sc.nextInt();
if (a < 0) s *= -1;
if (s > 0) {
rp += sp;
rn += sn;
++ sp;
}
else {
rp += sn;
rn += sp;
++ sn;
}
}
System.out.println(rn + " " + rp);
}
}
3565. 完美矩阵🧐
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[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
int[][] arr = new int[n][m];
for (int j = 0; j < n; ++ j) {
String[] s2 = br.readLine().split(" ");
for (int k = 0; k < m; ++ k) {
arr[j][k] = Integer.parseInt(s2[k]);
}
}
long ans = 0;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
int a = arr[i][j];
int b = arr[n - i - 1][j];
int c = arr[i][m - j - 1];
int d = arr[n - i - 1][m - j - 1];
int mid = Math.min(Math.max(a, b), Math.max(c, d));
ans += Math.abs(a - mid) + Math.abs(b - mid) + Math.abs(c - mid) + Math.abs(d - mid);
}
}
bw.write(ans / 4 + "\n");
}
bw.close();
br.close();
}
}
类似题型: 货仓选址
3554. 二进制🥰
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());
for (int j = 0; j < t; ++ j) {
String s = br.readLine();
StringBuilder str1 = new StringBuilder(s);
boolean flag = true;
for (int i = 31; i >= 0 && flag; -- i) {
if (str1.charAt(i) == '1') str1.setCharAt(i, '0');
else {
str1.setCharAt(i, '1');
flag = false;
}
}
if (flag) str1.insert(0, '1');
StringBuilder str2 = new StringBuilder(str1);
bw.write(str1.toString() + "\n");
flag = true;
for (int i = str2.length() - 2; i >= 0 && flag; -- i) {
if (str2.charAt(i) == '1') str2.setCharAt(i, '0');
else {
str2.setCharAt(i, '1');
flag = false;
}
}
if (flag) str2.insert(0, '1');
bw.write(str2.toString() + "\n");
}
bw.close();
br.close();
}
}
3333. K-优字符串🥰
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());
for (int i = 1; i <= t; ++ i) {
String[] strs = br.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int k = Integer.parseInt(strs[1]);
String s = br.readLine();
int len = s.length();
int count = 0, ans = 0;
for (int j = 0; j < len / 2; ++ j) {
if (s.charAt(j) != s.charAt(len - 1 - j)) {
count ++;
}
}
ans = Math.abs(count - k);
bw.write("Case #" + i + ": " + ans + "\n");
}
bw.close();
br.close();
}
}
3483. 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));
String s;
while ((s = br.readLine()) != null) {
int n = Integer.parseInt(s);
bw.write(dfs(n) + "\n");
}
bw.close();
br.close();
}
private static String dfs (int num) {
StringBuilder str = new StringBuilder();
for (int i = 14; i >= 0; -- i) {
if (((num >> i) & 1) == 1) {
if (str.length() != 0) str.append("+");
if (i == 0) str.append("2(0)");
else if (i == 1) str.append("2");
else str.append("2(").append(dfs(i)).append(")");
}
}
return str.toString();
}
}
3404. 谁是你的潜在朋友
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));
String[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int[] readers = new int[n];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; ++ i) {
readers[i] = Integer.parseInt(br.readLine());
map.put(readers[i], map.getOrDefault(readers[i], 0) + 1);
}
for (int i = 0; i < n; ++ i) {
int num = map.getOrDefault(readers[i], 0);
if (num == 1) {
bw.write("BeiJu\n");
} else {
bw.write(num - 1 + "\n");
}
}
bw.close();
br.close();
}
}
3516. 最大面积🤯
import java.util.*;
import java.io.*;
public class Main {
static int N = 2010;
static int[][] matrix = new int[N][N];
static int[][] sum = new int[N][N];
static int[] u = new int[N];
static int[] d = new int[N];
static int[] l = new int[N];
static int[] r = new int[N];
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] strs = br.readLine().split(" ");
int n = Integer.parseInt(strs[0]);
int m = Integer.parseInt(strs[1]);
for (int i = 1; i <= n; ++ i) {
String s = br.readLine();
for (int j = 1; j <= m; ++ j) {
matrix[i][j] = s.charAt(j - 1) - '0';
}
}
// 自顶向下
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
if (matrix[i][j] == 1) sum[i][j] = sum[i - 1][j] + 1;
else sum[i][j] = 0;
}
u[i] = Math.max(u[i - 1], calc(sum[i], m));
}
// 清空
for (int i = 0; i < N; ++ i) Arrays.fill(sum[i], 0);
// 自底向上
for (int i = n; i >= 1; -- i) {
for (int j = 1; j <= m; ++ j) {
if (matrix[i][j] == 1) sum[i][j] = sum[i + 1][j] + 1;
else sum[i][j] = 0;
}
d[i] = Math.max(d[i + 1], calc(sum[i], m));
}
// 清空
for (int i = 0; i < N; ++ i) Arrays.fill(sum[i], 0);
// 自左向右
for (int i = 1; i <= m; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (matrix[j][i] == 1) sum[i][j] = sum[i - 1][j] + 1;
else sum[i][j] = 0;
}
l[i] = Math.max(l[i - 1], calc(sum[i], n));
}
// 清空
for (int i = 0; i < N; ++ i) Arrays.fill(sum[i], 0);
// 自右向左
for (int i = m; i >= 1; -- i) {
for (int j = 1; j <= n; ++ j) {
if (matrix[j][i] == 1) sum[i][j] = sum[i + 1][j] + 1;
else sum[i][j] = 0;
}
r[i] = Math.max(r[i + 1], calc(sum[i], n));
}
int q = Integer.parseInt(br.readLine());
for (int i = 0; i < q; ++ i) {
String[] s = br.readLine().split(" ");
int x = Integer.parseInt(s[0]) + 1;
int y = Integer.parseInt(s[1]) + 1;
int ans = Math.max(Math.max(u[x - 1], d[x + 1]), Math.max(l[y - 1], r[y + 1]));
bw.write(ans + "\n");
}
bw.close();
br.close();
}
// 单调栈求最大面积
public static int calc (int[] nums, int n) {
Deque<Integer> stack = new LinkedList<>();
int[] left = new int[n + 1];
int[] right = new int[n + 1];
Arrays.fill(left, 0);
Arrays.fill(right, n + 1);
for (int i = 1; i <= n; ++ i) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
right[stack.pop()] = i;
}
stack.push(i);
}
stack.clear();
for (int i = n; i >= 1; -- i) {
while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
left[stack.pop()] = i;
}
stack.push(i);
}
int ans = 0;
for (int i = 1; i <= n; ++ i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * nums[i]);
}
return ans;
}
}
830.单调栈 -> 131.直方图中最大的矩形 -> 152.城市游戏 -> 3516.最大面积
🧩 calc另一写法
public static int calc(int[] nums, int n){
nums[0] = -1;
nums[n + 1] = -1;
int ans = 0;
int[] left = new int[n + 1];
int[] right = new int[n + 1];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for(int i = 1; i <= n; i ++){
while(nums[i] <= nums[stack.peek()]){
stack.pop();
}
left[i] = stack.peek();
stack.push(i);
}
stack.clear();
stack.push(n + 1);
for(int i = n; i >= 1; i --){
while(nums[i] <= nums[stack.peek()]){
stack.pop();
}
right[i] = stack.peek();
stack.push(i);
}
for(int i = 1; i <= n; i ++){
ans = Math.max(ans, (right[i] - left[i] - 1) * nums[i]);
}
return ans;
}
3481. 阶乘的和🧐
🧩 爆搜
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int[] res = new int[10];
res[0] = 1;
for (int i = 1; i < 10; ++ i) {
res[i] = res[i - 1] * i;
}
while (sc.hasNext()) {
long n = sc.nextLong();
if (n < 0) break;
if (dfs(res, n, 0)) System.out.println("YES");
else System.out.println("NO");
}
}
private static boolean dfs (int[] res, long n, int idx) {
if (idx > 9) return false;
long tmp = n - res[idx];
if (tmp > 0) {
return dfs(res, tmp, idx + 1) || dfs(res, n, idx + 1);
}
if (tmp == 0) return true;
return false;
}
}
🧩 位枚举📘
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
Set<Integer> set = new HashSet<>();
int[] res = new int[10];
res[0] = 1;
for (int i = 1; i < 10; ++ i) {
res[i] = res[i - 1] * i;
}
for (int i = 1; i < 1 << 10; ++ i) {
int s = 0;
for (int j = 0; j < 10; ++ j) {
if ((i >> j & 1) == 1) {
s += res[j];
}
}
set.add(s);
}
while (sc.hasNext()) {
int num = sc.nextInt();
if (num < 0) break;
if (set.contains(num)) System.out.println("YES");
else System.out.println("NO");
}
}
}
3489. 星期几🤓
import java.util.*;
public class Main {
int[] mouths;
String[] week_name;
HashMap<String, Integer> mouth_name;
public Main () {
mouths = new int[]{
0, 31, 28, 31, 30, 31, 30, 31, 31,
30, 31, 30, 31
};
mouth_name = new HashMap<String, Integer>(){{
put("January", 1);
put("February", 2);
put("March", 3);
put("April", 4);
put("May", 5);
put("June", 6);
put("July", 7);
put("August", 8);
put("September", 9);
put("October", 10);
put("November", 11);
put("December", 12);
}};
week_name = new String[]{
"Monday", "Tuesday", "Wednesday",
"Thursday", "Friday", "Saturday",
"Sunday"
};
}
boolean is_leap (int year) {
return year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
}
int get_days (int year, int mouth) {
int days = mouths[mouth];
if (mouth == 2 && is_leap(year)) ++ days;
return days;
}
public static void main (String[] args) {
Main sol = new Main();
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] strs = sc.nextLine().split(" ");
int day = Integer.parseInt(strs[0]), mouth = sol.mouth_name.get(strs[1]), year = Integer.parseInt(strs[2]);
int d = 1, m = 1, y = 1;
int days = 0;
while (d < day || m < mouth || y < year) {
++ days;
++ d;
if (d > sol.get_days(y , m)) {
d = 1;
++ m;
if (m > 12) {
m = 1;
++ y;
}
}
}
System.out.println(sol.week_name[days % 7]);
}
}
}
3510. 最长公共子序列😳
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] u = br.readLine().split(" ");
String[] v = br.readLine().split(" ");
int[] a = new int[n];
int[] b = new int[n];
for(int i = 0; i < n; i++) a[i] = Integer.parseInt(u[i]);
for(int i = 0; i < n; i++) b[i] = Integer.parseInt(v[i]);
int[] id = new int[1000010];
for (int i = 0; i < n; ++ i) id[a[i]] = i;
int[] q = new int[n + 1];
int tt = 0;
q[0] = 0;
for (int i = 0; i < n; ++ i) {
int k = id[b[i]];
if (k == 0) continue;
int l = 0, r = tt;
while (l < r) {
int mid = (l + r + 1) / 2;
if (q[mid] < k) {
l = mid;
} else {
r = mid - 1;
}
}
q[r + 1] = k;
tt = Math.max(tt, r + 1);
}
System.out.println(tt);
}
}
3502. 不同路径数🥳
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int[][] w = new int[n][m];
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++j) {
w[i][j] = sc.nextInt();
}
}
Set<String> set = new HashSet<>();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
dfs(i, j, k, w, list, set);
}
}
System.out.println(set.size());
}
private static void dfs(int x, int y, int k, int[][] w, List<Integer> list, Set<String> set) {
list.add(w[x][y]);
if (k <= 0) {
set.add(list.toString());
list.remove(list.size() - 1); // 删除添加的元素，关键
return;
}
if (x < w.length - 1) dfs(x + 1, y, k - 1, w, list, set);
if (y < w[0].length - 1) dfs(x, y + 1, k - 1, w, list, set);
if (x > 0) dfs(x - 1, y, k - 1, w, list, set);
if (y > 0) dfs(x, y - 1, k - 1, w, list, set);
list.remove(list.size() - 1);
}
}
3499. 序列最大收益🤒
🧩 动态规划
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m + 1];
for (int i = 1; i <= m; ++i) {
a[i] = sc.nextInt();
}
int[][] w = new int[n + 1][n + 1];
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++j) {
w[i][j] = sc.nextInt();
}
}
// dp[i][j] 表示前i个点删除j个数 保留i的最大收益
int[][] dp = new int[m + 1][k + 1];
for (int i = 0; i <= m; ++ i) {
Arrays.fill(dp[i], -1);
}
dp[1][0] = 0;
for (int i = 2; i <= m; ++ i) {
for (int j = 0; j <= k; ++ j) {
for (int u = 1; u < i; ++ u) {
int tmp = i - u - 1; //
if (j >= tmp)
dp[i][j] = Math.max(dp[i][j], dp[u][j - tmp] + w[a[u]][a[i]]);
}
}
}
int ans = 0;
for (int num : dp[m]) {
ans = Math.max(ans, num);
}
System.out.println(ans);
}
}
3493. 最大的和😜
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
int[] state = new int[n];
for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
for (int i = 0; i < n; ++ i) state[i] = sc.nextInt();
// 求出状态为1的和
long sum = 0;
for (int i = 0; i < n; ++ i) {
if (state[i] == 1) sum += a[i];
}
// 求连续k个位置状态为0的最大值
long v = 0, s = 0;
for (int i = 0; i < n; ++ i) {
if (state[i] == 0) s += a[i];
if (i >= k && state[i - k] == 0) s -= a[i - k];
v = Math.max(v, s);
}
// 相加即为答案
System.out.println(sum + v);
}
}
3485. 最大异或和🤪
🧩 字典树 & 前缀和
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; ++ i) {
nums[i] = scanner.nextInt();
}
System.out.println(maxXORSum(N, M, nums));
scanner.close();
}
/**
* Description: 字典树 + 贪心
*/
private static int maxXORSum (int n, int m, int[] nums) {
// 求前缀异或和
int[] sum = new int[n + 1];
for (int i = 1; i <= n; ++ i) {
sum[i] = sum[i - 1] ^ nums[i - 1];
}
Trie trie = new Trie();
trie.insert(sum[0], 1);
int ans = 0;
for (int i = 1; i <= n; ++ i) {
if (i > m) trie.insert(sum[i - m - 1], -1);
trie.insert(sum[i], 1);
ans = Math.max(ans, trie.get(sum[i]));
}
return ans;
}
}
/**
* Description: Tire树结点定义
*/
class TrieNode {
TrieNode[] sub = new TrieNode[2];
int count = 0;
}
/**
* Description: 字典树
*/
class Trie{
TrieNode root;
public Trie(){
root = new TrieNode();
}
// 插入
public void insert(int x, int v){
TrieNode cur = root;
for(int i = 30; i >= 0; i--){
int d = (x >> i) & 1;
if(cur.sub[d] == null){
cur.sub[d] = new TrieNode();
}
cur = cur.sub[d];
cur.count += v;
}
}
//获得 x 的最大异或值
public int get(int x){
int sum = 0;
TrieNode cur = root;
for(int i = 30; i >= 0; i--){
int d = (x >> i) & 1;
if(cur.sub[d ^ 1] != null && cur.sub[d ^ 1].count > 0){
sum = sum * 2 + 1;
cur = cur.sub[d ^ 1];
}else if(cur.sub[d] != null && cur.sub[d].count > 0){
sum = sum * 2;
cur = cur.sub[d];
}
}
return sum;
}
}
Comments | NOTHING