博客

A.门牌制作

题解

624

#include<iostream>
using namespace std;
int nums[10];
void solve(int i)
{
    while(i)
    {
        nums[i%10]++;
        i /= 10;
    }
}
int main()
{
    for(int i = 1; i <= 2020; i++)
        solve(i);
    cout << nums[2];
    return 0;
}

B.寻找2020

📎2020.txt

题目分析

将文本的每一行每一列以及斜线存到数组里，对数组进行遍历，出现一个2020答案加一即可。

16520

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

/**
 * @Description
 * @Author:PrinceHan
 * @CreateTime:2022/1/29 13:31
 */
public class B {
    static final int N = 300;
    static char[][] ch = new char[N][N];
    static String[] strl = new String[N];
    static String[] strc = new String[N];
    static String str;
    static int ans;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("src/lanqiao/y2020_11/2020.txt"));

        for (int i = 0; i < 300; i++) {
            String s = in.readLine();
            ch[i] = s.toCharArray();
            strl[i] = s;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (strl[i].startsWith("2020", j)) ans++;
            }
        }
        for (int i = 0; i < N; i++) {
            StringBuilder s = new StringBuilder();
            for (int j = 0; j < N; j++) {
                s.append(ch[j][i]);
            }
            String tmp = s.toString();
            strc[i] = tmp;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (strc[i].startsWith("2020", j)) ans++;
            }
        }
        for (int i = 0; i < 300; i++) {
            for (int j = 0; j < 300; j++) {
                //检查最后一个坐标是否符合
                if (i + 4 <= 300 && j + 4 <= 300) {
                    String s = "";
                    s += ch[i][j];
                    s += ch[i + 1][j + 1];
                    s += ch[i + 2][j + 2];
                    s += ch[i + 3][j + 3];
                    if (s.equals("2020")) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

C.蛇形填数

题目分析

为了便于计算可以将该矩阵顺时针旋转45度，如下图所示：

则第20行20列旋转后为第20 * 2 – 1行第20个，即第39行第20个，前38行有

(38 + 1) * 38 / 2 = 741


加上第39行的20，一共是761。

题解

761

D.七段码

题目分析

可以将a b c d e f g七个灯管抽象为七个顶点，用edge数组表示灯管是否相连，

edge[i][j] = 1

，表示第i个顶点与第j个顶点相连，即灯管相连。

深搜每一个状态，用并查集判断某一个顶点是否与其他顶点在一个图里，在不影响图的连通性的基础上，将这个顶点加入这个图里。原理为若所有顶点的父亲顶点都一样，则在一个集合里，否则需要合并。实现并查集需要实现它的三个方法，分别为

init()

,

find()

,

join()


init()

public static void init() {
       for (int i = 1; i <= 7; i++) {
           fa[i] = i;//初始化父亲顶点
       }
}

find()

public static int find(int r) {
    if (r == fa[r]) return r;
    else return find(fa[r]);
}

普通的find方法，在查询过程中可能会栈溢出，下面给出路径压缩算法

public static int find(int r) {
    if (r == fa[r]) return r;
    else {
        fa[r] = find(fa[r]);
        return fa[r];
    }
}

join()

public static void join(int x, int y) {
    int xfa = find(x);
    int yfa = find(y);
    if (xfa != yfa) {
        fa[xfa] = yfa;//合并哪个都行
    }
}

题解

80

public class D {
    static final int N = 10;
    static int[] fa = new int[N];
    static int[][] edge = new int[N][N];
    static boolean[] vis = new boolean[N];
    static int ans;

    public static void main(String[] args) {
        link();
        dfs(1);
        System.out.println(ans);
    }

    public static void link() {
        /*
        a b c d e f g
        1 2 3 4 5 6 7
         */
        //将连通的情况置为1
        edge[1][2] = edge[1][6] = 1;
        edge[2][1] = edge[2][3] = edge[2][7] = 1;
        edge[3][2] = edge[3][4] = edge[3][7] = 1;
        edge[4][3] = edge[4][5] = 1;
        edge[5][4] = edge[5][6] = edge[5][7] = 1;
        edge[6][1] = edge[6][5] = edge[6][7] = 1;
        edge[7][2] = edge[7][3] = edge[7][5] = edge[7][6] = 1;
    }

    public static void dfs(int d) {
        //d表示第几个灯管，范围为1~7
        if (d > 7) {
            init();
            for (int i = 1; i <= 7; i++) {
                for (int j = 1; j <= 7; j++) {
                    if (edge[i][j] == 1 && vis[i] && vis[j]) {
                        //如果i,j连通,并且i,j灯管亮了,合并i,j
                        join(i, j);
                    }
                }
            }
            int k = 0;
            for (int i = 1; i <= 7; i++) {
                //如果灯管亮了并且自身是父亲结点
                if (vis[i] && fa[i] == i) k++;
            }
            //如果所有顶点在一个集合里
            if (k == 1) ans++;
            return;
        }
        vis[d] = true;//将第d个灯管点亮
        dfs(d + 1);//在第d个灯管点亮的情况下处理第d + 1个灯管
        vis[d] = false;//将第d个灯管关闭
        dfs(d + 1);//在第d个灯管关闭的情况下处理第d + 1个灯管

    }

    public static void init() {
        for (int i = 1; i <= 7; i++) {
            fa[i] = i;//初始化父亲顶点
        }
    }

    public static int find(int r) {
        if (r == fa[r]) return r;
        else {
            fa[r] = find(fa[r]);
            return fa[r];
        }
    }

    public static void join(int x, int y) {
        int xfa = find(x);
        int yfa = find(y);
        if (xfa != yfa) {
            fa[xfa] = yfa;
        }
    }
}

E.排序

题目分析

题目要求字符串长度最短，在长度最短的情况下使得字典序最小，逆序的字符串需要比较的次数最多，为

(n - 1) * n / 2

，取最接近100并且使结果大于100的n，得 n = 15,此时比较次数为105，要使次数减少5可以让第六个字母放在字符串的首位，结果是

jonmlkihgfedcba。

简单验证一下：

答案正确！

F.成绩分析

题目分析

遍历一遍即可

import java.util.Scanner;

/**
 * @Description
 * @Author:PrinceHan
 * @CreateTime:2022/1/28 19:28
 */
public class F {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            sum += a[i];
        }
        int max = a[0], min = a[0];
        for (int i = 0; i < n; i++) {
            max = Math.max(max, a[i]);
            min = Math.min(min, a[i]);
        }
        System.out.println(max);
        System.out.println(min);
        System.out.printf("%.2f", sum * 1.0 / n);
    }
}

G.单词分析

题目分析

可以用map将字母与出现次数映射在一起，遍历一遍字符串，得到每一个字母出现的次数，比较得出最大值即可。

题解

import java.util.HashMap;
import java.util.Scanner;
import java.util.Set;

/**
 * @Description
 * @Author:PrinceHan
 * @CreateTime:2022/1/28 20:36
 */
public class G {
        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                HashMap<Character, Integer> ci = new HashMap<>();
                String s = null;
                char ans = '\0';
                s = scanner.next();
                int max = -1;
                int len = s.length();
                for (int i = 0; i < len; i++) {
                        char ch = s.charAt(i);
                        Integer value = ci.get(ch);
                        if (value == null) {
                                ci.put(ch,1);
                        } else {
                                value++;
                                ci.put(ch,value);
                        }
                }
                Set<Character> chs = ci.keySet();
                for(Character ch : chs) {
                        if (max < ci.get(ch)) {
                                max = ci.get(ch);
                                ans = ch;
                        }
                }
                System.out.println(ans);
                System.out.println(ci.get(ans));
        }
}

这道题用C++写更方便

#include <iostream>
#include <cstring>
using namespace std;
char ch[1005];
int nums[1005];
int main()
{
    int ansch = 0, ansnum = 0;
    cin >> ch;
    int len = strlen(ch);
    for(int i = 0; i < len; i++)
        nums[ch[i]]++;
    for(int i = 'a'; i <= 'z'; i++)
    {
        if(ansnum < nums[i])
        {
            ansnum = nums[i];
            ansch = i;
        }
    }
    cout << (char)ansch << endl << ansnum;
    return 0;
}

H.数字三角形

题目分析

求最大的和可以用到动态规划，最后和比较大的数都会集中在最后一行。但是本道题目限制了向左走和向右走得步数差不超过一，也就是说答案集中在最后一行得中间位置，如果三角形有奇数层，则中间位置即为解，否则中间两个位置得最大值为解。

题解

import java.util.Scanner;

/**
 * @Description
 * @Author:PrinceHan
 * @CreateTime:2022/1/29 18:42
 */
public class H {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int lev = scanner.nextInt();
        int[][] dp = new int[lev + 1][lev + 1];
        for (int i = 1; i <= lev; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = scanner.nextInt();
            }
        }
        for (int i = 1; i <= lev; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] += Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
        if (lev % 2 == 0) {
            System.out.println(Math.max(dp[lev][lev / 2], dp[lev][lev / 2 + 1]));
        } else System.out.println(dp[lev][lev / 2 + 1]);
    }

}

I.子串分值和

题目分析

从题目中可以看出评测用例的规模为105，因此暴力枚举两层循环会超时，只能独辟蹊径解决问题。

首先将测试用例分成所有的子串，再把每个子串中不重复的字母表示出来。

a         a
ab        a b
aba       a b
abab      a b
ababc     a b     c
 b          b
 ba         b a
 bab        b a
 babc       b a   c
  a           a
  ab          a b
  abc         a b c
   b            b
   bc           b c
    c             c

一开始所有的字符都未出现过，将他们的位置都初始化-1，一旦出现过，更新其位置。

类似“左边两条路右边三条路一共有6种走法”，对于此刻枚举的第i的字符来说，从其前一次出现的位置+1到此刻i都是其可能开始的地方（从上面的数据可以体会到，例如a一开始未出现过，位置为-1，下一个位置为0，i= 0，所以a开始于0，a开始的地方有1个；例如b，上次出现的位置为-1，则从0到1都是其开始的地方，所以在算以a为首字母的子串中有b，以b开头的字串也有b，b开始的地方有两个）；而从此刻i到结尾则可能是其结束的地方。比如，ababc对应下标01234，对于第二个a来说，下标[x，y]x的取值范围是[1,2]，Y则是[1,4]。这样一来的话左边可选有2，右边可选有4，相乘为8；对每一个字符都用这样的思路去思考，最终就是O（n）复杂度的解。

题解

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Description
 * @Author:PrinceHan
 * @CreateTime:2022/1/30 17:47
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        char[] chs = str.toCharArray();
        int len = chs.length;
        int[] loc = new int[26];
        long ans = 0;
        Arrays.fill(loc, -1);
        for (int i = 0, _len = len; i < len; i++, _len --) {
            ans += (long) (i - loc[chs[i] - 'a']) * _len;
            //i - loc[chs[i] - 'a']表示开始的位置有几个，_len表示结束的位置有几个
            loc[chs[i] - 'a'] = i;//更新位置
        }
        System.out.println(ans);
    }
}

J.装饰珠