[C++知识库] 2020第十一届蓝桥杯省赛C/C++真题—

本题为结果填空题，只需要计算出结果提交即可，结果为整数，提交时不能输出多余的内容.

思路：这道题考的是最大公约数问题，因为是填空题不需要担心超时，所以可以直接用两层循环暴力法解决

蛇形填数:

本题为结果填空题，只需要计算出结果提交即可，结果为整数，提交时不能输出多余的内容.

容易看出第i行第i列的值等于第i-1行第i-1列的值+（i-1）*4，也就是a[i][i] = a[i-1][i-1] + (i-1)*4;

七段码

?思路: 可以用DFS搜索所有状态，判断每种状态可不可行。判断的方法是把每条灯管当作一个节点，编号，连边建图，对搜索出的亮灯方案使用并查集判断点亮的灯管是否在同一个集合（并查集）。

????????因为这是填空题，当然还有种办法，人工枚举。但是很容易漏掉，实在不会做可以用。


public class Main {

    static int MAXN = 8;
    static int n = 7;
    static int ans = 0;
    static int[] path = new int[MAXN];
    static int[][] graph = new int[MAXN][MAXN];//保存边之间的关系
    static int father[] = new int[MAXN]; //保存父结点
    static int[] height = new int[MAXN]; //保存树的高度

    public static void main(String[] args) {

        //表示边之间的关系，1表示直连，0反之,自己和自己为一个较大的数
        graph[1][2] = graph[2][1] = 1;
        graph[1][6] = graph[6][1] = 1;
        graph[2][7] = graph[7][2] = 1;
        graph[6][7] = graph[7][6] = 1;
        graph[7][3] = graph[3][7] = 1;
        graph[7][5] = graph[5][7] = 1;
        graph[2][3] = graph[3][2] = 1;
        graph[3][4] = graph[4][3] = 1;
        graph[4][5] = graph[5][4] = 1;
        graph[5][6] = graph[6][5] = 1;

        for (int i = 1; i <= n; i++) {
            dfs(0, 1, i);
        }
        System.out.println(ans);
    }
    //初始化
    private static void init(){
        for (int i = 1; i < MAXN; i++) {
            father[i] = i;
            height[i] = 0;
        }
    }

    //查找x的祖先结点
    private static int find(int x) {
        if (x != father[x])
            return father[x] = find(father[x]);
        return father[x];
    }

    //合并
    private static void union(int x,int y){
        x = find(x);
        y = find(y);
        if (height[x] == height[y]){
            height[x] = height[x] + 1; //合并，树的高度加1
            father[y] = x;
        } else if (height[x] > height[y]) {
            //将高度小的树合并到高度大的树上
            father[y] = x;
        }else {
            //将高度小的树合并到高度大的树上
            father[x] = y;
        }
    }

    private static void dfs(int u, int p, int m) {
        if (u == m) {
            //初始化操作
            init();
            //集合合并
            for (int i = 0; i < m; ++i) {
                for (int j = i + 1; j < m; ++j) {
                    //存在边相连
                    if (graph[path[i]][path[j]] == 1) {
                        //path[i] 和 path[j] 合并成一个集合  
                        union(path[i],path[j]);
                    }
                }
            }
            //查找最终是否为一个集合
            boolean flag = false;
            for (int i = 0; i < m - 1; ++i) {
                //不是同一个集合
                if (find(path[i]) != find(path[i + 1])) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                ++ans;
            }
            return;
        }

        for (int i = p; i <= n; ++i) {
            path[u] = i;
            dfs(u + 1, i + 1, m);
        }
    }

}

跑步锻炼?


public class Main {

    public static void main(String[] args) {
        int ants = 0; //记录结果
        int[] Month = {0,31,28,31,30,31,30,31,31,30,31,30,31}; // 平年每个月的天数
        int year = 2000, month = 1, day = 1, weekday = 6;
        while (true) {
            //判断是否是星期一或者是每个月月初
            if (weekday == 1 || day == 1) {
                ants += 2;
            }else {
                ants += 1;
            }
            if (year == 2020 && month == 10 && day == 1) {
                //结束条件
                break;
            }
            day += 1;
            weekday = (weekday+1)%7;
            //判断是否为闰年并且是二月
            if (month == 2 && ( (year % 4 == 0 && year % 100 != 0) || year % 400 == 0)){
                if (day > Month[month]+1){
                    day = 1;
                    month += 1;
                }
            }else {
                if (day > Month[month]){
                    day = 1;
                    month += 1;
                }
            }
            if (month == 13){
                month = 1;
                year += 1;
            }
        }
        System.out.println(ants); // 8879
    }
}

回文日期:

????????2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年2 月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是20200202，恰好是一个回文数。我们称这样的日期是回文日期。
有人表示20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到2 年之后就是下一个回文日期：20211202 即2021 年12 月2 日。
也有人表示20200202 并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100 年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。
给定一个8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA 型的回文日期各是哪一天。

????????输入包含多组测试数据，第一行为正整数T。(T≤1000)
????????接下来T行，每行包含一个八位整数N，表示日期。
????????对于所有评测用例，10000101?≤?N?≤?89991231，保证N 是一个合法日期的8 位数表示。

????????对于每组测试数据输出两行，每行1 个八位数。
????????第一行表示下一个回文日期，第二行表示下一个ABABBABA 型的回文日期。

思路：需要先写一个方法，来判断八位数是否为合法的日期。判断日期是否合法的时候也需要注意判断是否为润年。满足该条件再判断是否为回文串和ABABBABA型串。判断ABABBABA串可以利用set集合去重，判断set.size()是否等于2.? ?


import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    //保存润年和平年每个月的天数
    public static int run[][] = {{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n;
        n = scanner.nextInt();
        String[] strings = new String[n];
        for (int i = 0; i < n; i++) {
            strings[i] = scanner.next();
        }
        scanner.close();
        for (int i = 0; i < n; i++) {
            //查找第一个回文串
            int num1 = find1(strings[i]);
            System.out.println(num1);
            //查找第一个ABABBABA型的回文串
            int num2 = find2(num1);
            System.out.println(num2);
        }
    }

    public static int find1(String dateStr) {
        int i;
        int date = Integer.parseInt(dateStr);
        for (i = date + 1; i < 90900910; i++) {
            if (check1(i)) {
                break;
            }
        }
        return i;
    }

    //判断是否回文
    private static boolean check1(int i) {
        String str = String.valueOf(i);
        char[] s = str.toCharArray();
        for (int j = 0; j < 4; j++) {
            if (str.charAt(j) != str.charAt(7 - j)) {
                return false;
            }
        }
        //判断是否为合法日期
        if (legalDate(s))
            return true;
        return false;
    }

    public static int find2(int date) {
        int i;
        for (i = date; i < 90900910; i++) {
            if (check2(i)) {
                break;
            }
        }
        return i;
    }

    private static boolean check2(int date) {
        //利用set去重
        Set<String> set = new HashSet<>();
        String str = String.valueOf(date);
        char[] s = str.toCharArray();
        for (int j = 0; j < 8; j++) {
            set.add(String.valueOf(str.charAt(j)));
        }
        if (set.size() != 2) {
            return false;
        } else {
            //还要判断是否为ABABBABA
            if (( str.charAt(0) == str.charAt(1) || str.charAt(2) == str.charAt(3) || str.charAt(1) == str.charAt(2)
                    || str.charAt(5) == str.charAt(6) || str.charAt(6) == str.charAt(7) || str.charAt(4) == str.charAt(5) ) ) {
                return false;
            } else if (str.charAt(3) == str.charAt(4)){
                if (legalDate(s))
                    return true;
                else
                    return false;
            }else
                return false;
        }
    }

    //判断是否为合法日期
    public static boolean legalDate(char[] s){
        int y = (s[0] - '0') * 1000 + (s[1] - '0') * 100 + (s[2] - '0') * 10 + (s[3] - '0');
        int m = (s[4] - '0') * 10 + (s[5] - '0');
        int d = (s[6] - '0') * 10 + (s[7] - '0');
        if (m > 12) return false;
        int f = (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0) ? 0 : 1;
        if (d > run[f][m]) return false;
        return true;
    }
}

字串排序:?

成绩统计：

字串分值和:?

?思路：可以直接用暴力法，利用Set去重的特性，可以得到一半的分数，后面的数据太大超时了

平面切分:?

1、一条一条的把直线放到平面上。
2、每次放入一条直线，看看这条直线会与平面上已有的直线产生多少个不同的交点。假如会产生a个交点，那么可以知道，放入了这条直线后，部分平面的个数会增加a+1（需要注意的是有可能交点会重合，也可能加入的直线在平面中已经存在了）。
3、从第1条直线开始放置到平面上，直至放置第n条结束。将每次放入一条直线后部分平面个数增加的个数累加起来就是最终的答案。