文章目录

• Day16
• • 第一题
  • • NOIP2015普及组
    • 金币
  • 第二题
  • • CSP-J 2020
    • 优秀的拆分
  • 第三题
  • • 第六届2015年蓝桥杯国赛
    • 穿越雷区
  • 第四题
  • • 第十一届2020年蓝桥杯国赛
    • 蓝肽子序列

Day16

第一题

NOIP2015普及组

金币

模拟

数据量比较小，直接双重循环暴力即可。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int sum = 0, day = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {sum += i;day++;if (day == n) System.out.println(sum);}}}}

第二题

CSP-J 2020

优秀的拆分

模拟

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();if (n % 2 == 1) System.out.println(-1);else {// 找到小于等于正整数n的最大的2的正整数次幂m  2^m<=n    int m = 2;    while (m <= n) m *= 2;    if (m > n) m /= 2; while (n > 0) {      System.out.print(m + " "); n -= m; // 将m从n中减去2 // 找到下一个小于等于正整数n的最大的2的正整数次幂m while (m > n) m /= 2;    }}}}

第三题

第六届2015年蓝桥杯国赛

穿越雷区

JavaB组第4题

bfs

import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Main {    static final int N = 110;    static int n;    static String[][] g = new String[N][N];    static boolean[][] st = new boolean[N][N];    public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = Integer.parseInt(sc.nextLine()); // 防止读入回车 int x = 0, y = 0; for (int i = 0; i < n; i++){     g[i] = sc.nextLine().split(" ");     for (int j = 0; j < n; j++) {  if (g[i][j].equals("A")) { // 标记起点      x = i;      y = j;  }     } } System.out.println(bfs(x, y));    }    public static int bfs(int sx, int sy) { Queue<PII> q = new LinkedList<>(); q.offer(new PII(sx, sy, 0)); st[sx][sy] = true; int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1}; while (!q.isEmpty()) {     PII t = q.poll();     for(int i = 0; i < 4; i++) {  int x = t.x + dx[i], y = t.y + dy[i];  if(x < 0 || x >= n || y < 0 || y >= n) continue; // 出界  if(g[t.x][t.y].equals(g[x][y])) continue; // 都为0或-1 不能走  if (st[x][y]) continue; // 已遍历过  if (g[x][y].equals("B")) return t.step + 1; // 遍历到终点 还要走过去 +1  q.offer(new PII(x, y, t.step + 1));  st[x][y] = true;     } } return -1;    }    static class PII { int x; int y; int step; // 记录步数 public PII(int x, int y, int step) {     this.x = x;     this.y = y;     this.step = step; }    }}

第四题

第十一届2020年蓝桥杯国赛

蓝肽子序列

JavaB组第6题

我没有做这道题，给大家把蓝桥oj平台的代码贴过来。

先将字符串预处理分割为每个大写字母开头的“蓝肽” 在将其作为判断最长子序列，判断最长子序列 可以采用：动态规划（最简单高效）

if S1[i] = S2[j] dp[i][j] = dp[i][j] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) 输出最大值即可

import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Main {    public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s1 = sc.next(); String s2 = sc.next(); List<String> list1 = sub(s1); List<String> list2 = sub(s2); int n = Math.max(list1.size(), list2.size()); int[][] dp = new int[n + 1][n + 1]; int max = 0; for(int i = 1; i <= list1.size(); i++) {     for(int j = 1; j <= list2.size(); j++) {  if(list1.get(i - 1).equals(list2.get(j - 1))) dp[i][j] = dp[i - 1][j - 1] + 1;  else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  if(dp[i][j] > max) max = dp[i][j];     } }  System.out.println(max);    }    public static List<String> sub(String s) { List<String> list = new ArrayList<>(); int start = 0; for(int i = 0; i < s.length(); i++) {     if(s.charAt(i) <= 90 && i != 0) {  String temp = s.substring(start, i);  list.add(temp);  start = i;     }     if(i == s.length() - 1) {  String temp = s.substring(start, i + 1);  list.add(temp);     } } return list;    }}