Day16

第一题

题目来源：NOIP2015普及组

问题描述：

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

解题思路：

题目要求计算从1到n的所有数字的总和。可以利用双重循环遍历所有数字并累加，时间复杂度为O(n²)，在数据量较小的情况下是可行的。

代码示例：

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

问题描述：

判断正整数n是否为奇数。如果是，输出-1；否则，找出n的二进制表示中最大的2的幂，并按顺序输出这些幂的和。

解题思路：

首先判断n是否为奇数。如果不是奇数，找到最大的2的幂m，使得m ≤ n。然后从n中减去m，直到n变为0，重复这个过程。

代码示例：

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 {            int m = 2;            while (m <= n) {                m *= 2;            }            if (m > n) {                m /= 2;            }            while (n > 0) {                System.out.print(m + " ");                n -= m;                while (m > n) {                    m /= 2;                }            }        }    }}

第三题

题目来源：第六届2015年蓝桥杯国赛

问题描述：

在一个网格中，起点为A，终点为B，要求找到从A到B的最短路径。允许移动四个方向，且不能重复经过相同的格子。

解题思路：

使用广度优先搜索（BFS）算法来解决这个问题。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
   
     q = new LinkedList<>();        q.offer(new PII(sx, sy, 0));        st[sx][sy] = true;        int[] dx = {-1, 0, 1, 0};        int[] 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];                int 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;                }                if (st[x][y]) {                    continue;                }                if (g[x][y].equals("B")) {                    return t.step + 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年蓝桥杯国赛

问题描述：

给定两个字符串S1和S2，找到它们的最大公共子序列的长度。

解题思路：

使用动态规划的方法来解决这个问题。创建一个二维数组dp[i][j]，其中dp[i][j]表示S1的前i个字符和S2的前j个字符的最大公共子序列长度。如果S1[i]等于S2[j]，则dp[i][j] = dp[i-1][j-1] + 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
   
     list1 = sub(s1);        List
    
      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
     
       sub(String s) {        List
      
        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;    }}

转载地址：http://hkhfk.baihongyu.com/

你可能感兴趣的文章