【Java】蓝桥杯历届试题PREV（一）

我不是女神ヾ 2022-12-13 04:12 214阅读 0赞

###  ###

*  PREV-46 试题 历届试题 填字母游戏（DFS+博弈论）
 *  PREV-54 试题 历届试题 合根植物（并查集模板）
 *  PREV-55 试题 历届试题 小计算器（模拟+进制转换API）

# PREV-46 试题 历届试题 填字母游戏（DFS+博弈论） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T450][http_lx.lanqiao.cn_problem.page_gpid_T450]

--------------------

**【问题描述】**

小明经常玩 LOL 游戏上瘾，一次他想挑战K大师，不料K大师说：  
　　“我们先来玩个空格填字母的游戏，要是你不能赢我，就再别玩LOL了”。

K大师在纸上画了一行n个格子，要小明和他交替往其中填入字母。

并且：

1. 轮到某人填的时候，只能在某个空格中填入L或O  
　　2. 谁先让字母组成了“LOL”的字样，谁获胜。  
　　3. 如果所有格子都填满了，仍无法组成LOL，则平局。

小明试验了几次都输了，他很惭愧，希望你能用计算机帮他解开这个谜。

--------------------

**【输入格式】**

第一行，数字n（n<10），表示下面有n个初始局面。  
　　  
接下来，n行，每行一个串，表示开始的局面。

比如：\*\*\*\*\*\* , 表示有6个空格。“L\*\*\*\*”, 表示左边是一个字母L，它的右边是4个空格。

--------------------

**【输出格式】**

要求输出n个数字，表示对每个局面，如果小明先填，当K大师总是用最强着法的时候，小明的最好结果。  
　　1 表示能赢  
　　-1 表示必输  
　　0 表示可以逼平

--------------------

**【样例输入】**

4
    ***
    L**L
    L**L***L
    L*****L

--------------------

**【样例输出】**

0  
\-1  
1  
1

--------------------

**思路：** 博弈论 + 记忆化搜索。

这道题的边界条件：

*  如果串中有LO*或L*L或\*OL，则现在走的玩家必赢。
 *  如果串中没有\*，则平局。

用一个map<string, int> m记录每个局面的结果，这样就不会重复计算。

**Code：**

import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    public class Main { 
        static Map<String, Integer> mp = new HashMap<String, Integer>();
        static String[] ch = {  "L", "O" };
    
        static int dfs(String str) { 
            //如果集合里面有这个字符串，就直接返回结果
            if (mp.containsKey(str))
                return mp.get(str);
            //如果字符串有“LOL”，那么就直接输了
            if (str.contains("LOL"))
                return -1;
            //长度小于3，也就直接平局了
            if (str.length() < 3)
                return 0;
            //没有空格也平局
            if (!str.contains("*"))
                return 0;
            //用来判断是否有可能平局的
            boolean ping = false;
            
            int len = str.length();
            for (int i = 0; i < len; i++) { 
                //如果是字符，只需要直接用==，如果是字符串，就要用equals
                if (str.charAt(i) == '*') { 
                    //暂存
                    String tmp = str;
                    for (int j = 0; j < 2; j++) { 
                        //替换指定字符
                        str = tmp.substring(0, i) + ch[j] + tmp.substring(i + 1, len);
                        //存在对手赢的情况，就回溯跳过
                        if (str.contains("L*L") || str.contains("*OL") || str.contains("LO*")) { 
                            str = tmp.substring(0, i) + "*" + tmp.substring(i + 1, len);
                            continue;
                        }
                        //搜索对手的情况
                        int next = dfs(str);
                        //回溯
                        str = tmp.substring(0, i) + "*" + tmp.substring(i + 1, len);
                        //对手赢就跳过
                        if (next == 1)
                            continue;
                        else if (next == -1)
                            return 1;
                        else if (next == 0)
                            ping = true;
    
                    }
                }
            }
    
            //存在平局状况
            if (ping) { 
                mp.put(str, 0);
                return 0;
            }
    
            //反正就是输的情况了
            mp.put(str, -1);
            return -1;
    
        }
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            sc.nextLine();
            for (int i = 0; i < n; i++) { 
                String str = sc.nextLine();
                System.out.println(dfs(str));
            }
        }
    }

# PREV-54 试题 历届试题 合根植物（并查集模板） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T458][http_lx.lanqiao.cn_problem.page_gpid_T458]

--------------------

**【问题描述】**

w星球的一个种植园，被分成 m \* n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。  
　　  
这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

--------------------

**【输入格式】**

第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1<m,n<1000）。  
　　  
接下来一行，一个整数k，表示下面还有k行数据(0<k<100000)  
　　  
接下来k行，第行两个整数a，b，表示编号为a的小格子和编号为b的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。  
　  
比如：5 \* 4 的小格子，编号：  
　　1 2 3 4  
　　5 6 7 8  
　　9 10 11 12  
　　13 14 15 16  
　　17 18 19 20

--------------------

**【样例输入】**

5 4  
16  
2 3  
1 5  
5 9  
4 8  
7 8  
9 10  
10 11  
11 12  
10 14  
12 16  
14 18  
17 18  
15 19  
19 20  
9 13  
13 17

--------------------

**【样例输出】**

--------------------

**【样例说明】**

其合根情况参考下图：

![在这里插入图片描述][20201009205330662.png_pic_center]

--------------------

**思路：** 简单并查集模板题。

**Code：**

import java.util.Scanner;
    
    public class Main { 
        static int n, m, k;
        static int[] root;
    
        static int find(int x) { 
            while (root[x] != x) { 
                x = root[x];
            }
            return x;
        }
    
        static void combine(int x, int y) { 
            int root1 = find(x);
            int root2 = find(y);
            if (root1 != root2) { 
                root[root1] = root2;
            }
        }
    
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            Scanner sc = new Scanner(System.in);
            m = sc.nextInt();
            n = sc.nextInt();
            k = sc.nextInt();
            
            root = new int[m*n+10];
    
            for (int i = 1; i <= m * n; i++) { 
                root[i] = i;
            }
    
            for (int i = 1; i <= k; i++) { 
                int x = sc.nextInt(), y = sc.nextInt();
                combine(x, y);
            }
            int ans = 0;
            for (int i = 1; i <= m * n; i++) { 
                if (root[i] == i)
                    ans++;
            }
            System.out.println(ans);
        }
    }

# PREV-55 试题 历届试题 小计算器（模拟+进制转换API） #

> **原题链接：**[http://lx.lanqiao.cn/problem.page?gpid=T459][http_lx.lanqiao.cn_problem.page_gpid_T459]

--------------------

**【问题描述】**

模拟程序型计算器，依次输入指令，可能包含的指令有

1.  数字：‘NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
2.  运算指令：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’，分别表示加减乘，除法取商，除法取余
3.  进制转换指令：‘CHANGE K’，将当前进制转换为K进制(2≤K≤36)
4.  输出指令：‘EQUAL’，以当前进制输出结果
5.  重置指令：‘CLEAR’，清除当前数字

指令按照以下规则给出：  
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出  
　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令  
　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令  
　　进制转换指令可能出现在任何地方

运算过程中中间变量均为非负整数，且小于2^63。  
　　以大写的 ‘A’ ~ ‘Z’ 表示 10~35

--------------------

**【输入格式】**

第1行：1个n，表示指令数量

第2…n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则

--------------------

**【输出格式】**

依次给出每一次’EQUAL’得到的结果

--------------------

**【样例输入】**

7  
CLEAR  
NUM 1024  
CHANGE 2  
ADD  
NUM 100000  
CHANGE 8  
EQUAL

--------------------

**【样例输出】**

2040

--------------------

**思路：** 这道题的关键在于进制转换，Long.valueOf()这个函数可以把指定字符串转换为想要的进制。

**Code：**

import java.util.Scanner;
    
    public class Main { 
    
        static String op = ""; // 运算符
        static int hex = 10; // 进制
        static long[] num = new long[3]; // 用来存两个要运算的数
    
        public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            sc.nextLine();
    
            for (int i = 1; i <= n; i++) { 
                String ss = sc.nextLine();
                String[] str = ss.split(" "); // 根据空格来分割
                operate(str);
    
            }
        }
    
        // 指令操作
        public static void operate(String[] str) { 
            switch (str[0]) { 
            case "NUM":
                if ("".equals(op)) { 
                    // Long.valueOf可以把字符串str[1]转换为hex进制的long数值
                    num[0] = Long.valueOf(str[1], hex);
                } else { 
                    num[1] = Long.valueOf(str[1], hex);
                    num[0] = calcute();
                    num[1] = 0;
                    op = "";
                }
                break;
            case "ADD":
                op = "ADD";
                break;
            case "SUB":
                op = "SUB";
                break;
            case "MUL":
                op = "MUL";
                break;
            case "DIV":
                op = "DIV";
                break;
            case "MOD":
                op = "MOD";
                break;
            case "CHANGE":
                hex = Integer.parseInt(str[1]);
                break;
            case "EQUAL":
                // 因为有可能是十六进制数，所以要转换为字符串形式，然后还要大写
                System.out.println(Long.toString(num[0], hex).toUpperCase());
                break;
            case "CLEAR":
                num[0] = 0;
                num[1] = 0;
                op = "";
                break;
            default:
                break;
            }
    
        }
    
        // 运算
        private static long calcute() { 
            // TODO Auto-generated method stub
            long ans = 0;
            switch (op) { 
            case "ADD":
                ans = num[0] + num[1];
                break;
            case "SUB":
                ans = num[0] - num[1];
                break;
            case "MUL":
                ans = num[0] * num[1];
                break;
            case "DIV":
                ans = num[0] / num[1];
                break;
            case "MOD":
                ans = num[0] % num[1];
                break;
            default:
                break;
            }
            return ans;
        }
    
    }

[http_lx.lanqiao.cn_problem.page_gpid_T450]: http://lx.lanqiao.cn/problem.page?gpid=T450
[http_lx.lanqiao.cn_problem.page_gpid_T458]: http://lx.lanqiao.cn/problem.page?gpid=T458
[20201009205330662.png_pic_center]: /images/20221123/a672972b77874dd29c2ec32ceafe4ebc.png
[http_lx.lanqiao.cn_problem.page_gpid_T459]: http://lx.lanqiao.cn/problem.page?gpid=T459