第八届蓝桥杯个人赛省赛详解（Java-A组）

妖狐艹你老母 2022-11-29 11:51 261阅读 0赞

**目录**

1-懒人走迷宫

2-九数算式

3-魔方问题

4-方块分割

5-有限个数字母组合

6-字符串匹配的最大长度

7-正则问题

8-包子凑数

9-分巧克力

10-油漆面积

总结

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

## 1-懒人走迷宫 ##

> ![20200820121340568.png][]
> 
>   
> 标题：迷宫
> 
> X星球的一处迷宫游乐场建在某个小山坡上。  
> 它是由10x10相互连通的小房间组成的。
> 
> 房间的地板上写着一个很大的字母。  
> 我们假设玩家是面朝上坡的方向站立，则：  
> L表示走到左边的房间，  
> R表示走到右边的房间，  
> U表示走到上坡方向的房间，  
> D表示走到下坡方向的房间。
> 
> X星球的居民有点懒，不愿意费力思考。  
> 他们更喜欢玩运气类的游戏。这个游戏也是如此！
> 
> 开始的时候，直升机把100名玩家放入一个个小房间内。  
> 玩家一定要按照地上的字母移动。
> 
> 迷宫地图如下：  
> \------------  
> UDDLUULRUL  
> UURLLLRRRU  
> RRUURLDLRD  
> RUDDDDUUUU  
> URUDLLRRUU  
> DURLRLDLRL  
> ULLURLLRDU  
> RDLULLRDDD  
> UUDDUDUDLL  
> ULRDLUURRR  
> \------------
> 
> 请你计算一下，最后，有多少玩家会走出迷宫?   
> 而不是在里边兜圈子。
> 
> 请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。

> **分析：**
> 
> 这题主要考点：递归思想，递归终止的依据（是否走迷宫？如有走到重复的路径，则意味着永远走不出去）
> 
> 还要注意一点，这题比较坑，迷宫初始的100个字符如果你使用复制粘贴，然后输入引号隔开，其实有点费时(而且容易有有错误），建议使用程序将字符串分割为字符数组。

public class Main {
    	public static char map[][] = new char[10][10];
    	// 标记走过的路径
    	static int[][] tag = new int[10][10];
    	static String str = "UDDLUULRULUURLLLRRRURRUURLDLRDRUDDDDUUUUURUDLLRRUUDURLRLDLRLULLURLLRDURDLULLRDDDUUDDUDUDLLULRDLUURRR";
    	public static int count = 0;
    
    	static {
    		char[] chars = str.toCharArray();
    		for (int i = 0; i < 10; i++) {
    			for (int j = 0; j < 10; j++) {
    				map[i][j] = chars[i * 10 + j];
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		// 从没个人的角度出发，开始走迷宫
    		for (int i = 0; i < 10; i++) {
    			for (int j = 0; j < 10; j++) {
    				cleanTag();
    				run(i, j);
    				cleanTag();
    			}
    		}
    		System.out.println(count);
    	}
    
    	// 数组归零
    	public static void cleanTag() {
    		for (int i = 0; i < 10; i++) {
    			for (int j = 0; j < 10; j++) {
    				tag[i][j] = 0;
    			}
    		}
    	}
    
    	public static void run(int i, int j) {
    		// 如果当前在界外，说明可以走出迷宫
    		if (i < 0 || i > 9 || j < 0 || j > 9) {
    			count++;
    			return;
    		} else {
    			// 如果这一步曾经走过，那意味着走不出去了
    			if (tag[i][j] == 1) {
    				return;
    			} else {
    				tag[i][j] = 1;
    			}
    			// 获取下一步的位置
    			int nextX = getNextX(i, j);
    			int nextY = getNextY(i, j);
    			run(nextX, nextY);
    		}
    	}
    
    	// 获取下一步横坐标
    	public static int getNextX(int i, int j) {
    		char c = map[i][j];
    		if (c == 'U') {
    			return i - 1;
    		}
    		if (c == 'D') {
    			return i + 1;
    		}
    		if (c == 'L') {
    			return i;
    		}
    		if (c == 'R') {
    			return i;
    		}
    		return i;
    	}
    
    	// 获取下一步纵坐标
    	public static int getNextY(int i, int j) {
    		char c = map[i][j];
    		if (c == 'U') {
    			return j;
    		}
    		if (c == 'D') {
    			return j;
    		}
    		if (c == 'L') {
    			return j - 1;
    		}
    		if (c == 'R') {
    			return j + 1;
    		}
    		return j;
    	}
    }

## 2-九数算式 ##

> 标题：9数算式
> 
> 观察如下的算式：
> 
> 9213 x 85674 = 789314562
> 
> 左边的乘数和被乘数正好用到了1~9的所有数字，每个1次。  
> 而乘积恰好也是用到了1~9的所有数字，并且每个1次。
> 
> 请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？
> 
> 注意：  
> 1. 总数目包含题目给出的那个示例。  
> 2. 乘数和被乘数交换后作为同一方案来看待。

>  **分析：**
> 
> 这题主要考点：深度搜索求全排序问题 （结果重复率为2）
> 
> 这题较为简单，将全排序的结果一个个验证即可，注意重复率问题

public class Main {
    	static char[] arr = new char[] { '0', '1', '2', '3', '4', '5', '6', '7','8', '9' };
    	// 每种可能的结果输出数组
    	static char[] result = new char[arr.length];
    	// 标记数组,记录数字是否被用过(1为用过）
    	static int[] tagArray = new int[arr.length];
    	static int count = 0;
    
    	public static void main(String[] args) {
    		dfs(0);
    		System.out.println(count / 2);
    	}
    
    	public static void dfs(int layer) {
    		if (layer >= arr.length) {
    			if (check(result)) {
    				count++;
    			}
    		} else {
    			for (int i = 0; i < arr.length; i++) {
    				if (tagArray[i] == 0) {
    					tagArray[i] = 1;
    					result[layer] = arr[i];
    					dfs(layer + 1);
    					tagArray[i] = 0;
    				}
    			}
    		}
    	}
    
    	public static boolean check(char[] arr) {
    		String string = new String(arr);
    		// 此处需注意，若分割点在第一个位置，则会分为两个字符串，若在最后一个位置，则只会分为一个字符串
    		String[] strings = string.split("0");
    		if (strings.length == 2 && !strings[0].equals("")
    				&& !strings[1].equals("")) {
    			long a = Long.parseLong(strings[0]);
    			long b = Long.parseLong(strings[1]);
    			long c = a * b;
    			return check(c);
    		}
    		return false;
    	}
    
    	public static boolean check(Long a) {
    		String string = a.toString();
    		for (int i = 1; i < arr.length; i++) {
    			if (!string.contains(new Character(arr[i]).toString())) {
    				return false;
    			}
    		}
    		return true;
    	}
    }

## 3-魔方问题 ##

> ![20200820122254930.png][]
> 
> 标题：魔方状态
> 
> 二阶魔方就是只有2层的魔方，只由8个小块组成。  
> 如图p1.png所示。
> 
> 小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：
> 
> 前面：橙色  
> 右面：绿色  
> 上面：黄色  
> 左面：绿色  
> 下面：橙色  
> 后面：黄色
> 
> 请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。
> 
> 如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。
> 
> 请提交表示状态数的整数，不要填写任何多余内容或说明文字。

> **分析：**
> 
> 此题由于没有找到公开的标准答案，暂未解析

## 4-方块分割 ##

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMDEzMDM1_size_16_color_FFFFFF_t_70][]
> 
>   
> 标题：方格分割
> 
> 6x6的方格，沿着格子的边线剪开成两部分。  
> 要求这两部分的形状完全相同。
> 
> 如图：p1.png, p2.png, p3.png 就是可行的分割法。
> 
> 试计算：  
> 包括这3种分法在内，一共有多少种不同的分割方法。  
> 注意：旋转对称的属于同一种分割法。
> 
> 请提交该整数，不要填写任何多余的内容或说明文字。

>  **分析：**
> 
> 同九数算式一样，此题的考察的也是一个变相的全排序问题。这样思考问题，假设有一个小蚂蚁从该图形的正中间的点出发，下一步可选 上，左，右三个方向，依次走下去，而另一只小蚂蚁向与之相反对称方向出发，列出所有走动的路线可能，即为分割该方块的所有方案，由于是正方形，此题的结果重复率为4

public class Main {
    	// 地图数组（0代表未走过的点，1代表走过的点）
    	int[][] map = new int[7][7];
    	// 方向数组(上下左右）
    	int[][] direction = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    	static int count = 0;
    
    	public void dfs(int x, int y) {
    		// 如果走到边界了，则完成本次切割
    		if (x <= 0 || x >= 6 || y <= 0 || y >= 6) {
    			count++;
    			return;
    		} else {
    			// 如何还有可以走的空间，尝试四个方向
    			for (int i = 0; i < 4; i++) {
    				// 获取该方向下一步的坐标
    				int nextX = x + direction[i][0];
    				int nextY = y + direction[i][1];
    				// 如果该坐标未走过，且该点关于中心对称的点也未走过，则可以走此步
    				if (map[nextX][nextY] != 1 && map[6 - nextX][6 - nextY] != 1) {
    					map[nextX][nextY] = 1;
    					map[6 - nextX][6 - nextY] = 1;
    					dfs(nextY, nextX);
    					map[6 - nextX][6 - nextY] = 0;
    					map[nextX][nextY] = 0;
    				}
    			}
    		}
    	}
    
    	public Main() {
    		map[3][3] = 1;
    		dfs(3, 3);
    		// 有四级重复
    		System.out.println(count / 4);
    	}
    
    	public static void main(String[] args) {
    		new Main();
    	}
    }

## 5-有限个数字母组合 ##

>   
> 标题：字母组串
> 
> 由 A,B,C 这3个字母就可以组成许多串。  
> 比如："A","AB","ABC","ABA","AACBB" ....
> 
> 现在，小明正在思考一个问题：  
> 如果每个字母的个数有限定，能组成多少个已知长度的串呢？
> 
> 他请好朋友来帮忙，很快得到了代码，  
> 解决方案超级简单，然而最重要的部分却语焉不详。
> 
> 请仔细分析源码，填写划线部分缺少的内容。
> 
>   
> public class A  
> \{  
>     // a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。  
>     static int f(int a, int b, int c, int n)  
>     \{  
>         if(a<0 || b<0 || c<0) return 0;  
>         if(n==0) return 1;   
>           
>         return \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_;  //填空  
>     \}  
>       
>     public static void main(String\[\] args)  
>     \{  
>         System.out.println(f(1,1,1,2));  
>         System.out.println(f(1,2,3,3));  
>     \}  
> \}
> 
> 对于上面的测试数据，小明口算的结果应该是：  
> 6
> 
> 19  
> 注意：只填写划线部分缺少的代码，不要提交任何多余内容或说明性文字。

> **分析：**
> 
> 这题考点是一个递归思想，仔细观察上下文不难得出答案

public class Main {
    	// a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串。
    	static int f(int a, int b, int c, int n) {
    		if (a < 0 || b < 0 || c < 0)
    			return 0;
    		if (n == 0)
    			return 1;
    
    		return f(a - 1, b, c, n - 1) + f(a, b - 1, c, n - 1)
    				+ f(a, b, c - 1, n - 1);
    	}
    
    	public static void main(String[] args) {
    		System.out.println(f(1, 1, 1, 2));
    		System.out.println(f(1, 1, 1, 1));
    	}
    }

## 6-字符串匹配的最大长度 ##

>   
> 标题：最大公共子串
> 
> 最大公共子串长度问题就是：  
> 求两个串的所有子串中能够匹配上的最大长度是多少。
> 
> 比如："abcdkkk" 和 "baabcdadabc"，  
> 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
> 
> 下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
> 
> 请分析该解法的思路，并补全划线部分缺失的代码。
> 
> public class Main  
> \{  
>     static int f(String s1, String s2)  
>     \{  
>         char\[\] c1 = s1.toCharArray();  
>         char\[\] c2 = s2.toCharArray();  
>           
>         int\[\]\[\] a = new int\[c1.length+1\]\[c2.length+1\];  
>           
>         int max = 0;  
>         for(int i=1; i<a.length; i++)\{  
>             for(int j=1; j<a\[i\].length; j++)\{  
>                 if(c1\[i-1\]==c2\[j-1\]) \{  
>                     a\[i\]\[j\] = \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_;  //填空   
>                     if(a\[i\]\[j\] > max) max = a\[i\]\[j\];  
>                 \}  
>             \}  
>         \}  
>           
>         return max;  
>     \}  
>       
>     public static void main(String\[\] args)\{  
>         int n = f("abcdkkk", "baabcdadabc");  
>         System.out.println(n);  
>     \}  
> \}
> 
>   
> 注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。

>  **分析：**
> 
> 这题使用的是图标法，将两个字符串作为横纵坐标标出，然后逐次匹配，最终求出斜对角最长的公共字符串即可

public class Main {
    	static int f(String s1, String s2) {
    		char[] c1 = s1.toCharArray();
    		char[] c2 = s2.toCharArray();
    
    		int[][] a = new int[c1.length + 1][c2.length + 1];
    
    		int max = 0;
    		for (int i = 1; i < a.length; i++) {
    			for (int j = 1; j < a[i].length; j++) {
    				if (c1[i - 1] == c2[j - 1]) {
    					a[i][j] = a[i - 1][j - 1] + 1;
    					if (a[i][j] > max)
    						max = a[i][j];
    				}
    			}
    		}
    
    		return max;
    	}
    
    	public static void main(String[] args) {
    		int n = f("abcdkkk111111111111111", "baabcdadabc111111111111");
    		System.out.println(n);
    	}
    }

## 7-正则问题 ##

>   
> 描述：正则问题
> 
> 考虑一种简单的正则表达式：  
> 只由 x ( ) | 组成的正则表达式。  
> 小明想求出这个正则表达式能接受的最长字符串的长度。  
> 
> 例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。
> 
> 输入  
> \----  
> 一个由x()|组成的正则表达式。输入长度不超过100，保证合法。  
> 
> 输出  
> \----  
> 这个正则表达式能接受的最长字符串的长度。  
> 
> 例如，  
> 输入：  
> ((xx|xxx)x|(x|xx))xx  
> 
> 程序应该输出：  
> 6  
> 
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 1000ms
> 
>   
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。

>  **分析：**
> 
> 这题的主要思想是使用递归，从内到外的化简正则表达式，知道表达式不包含 （ ）| 三个符号即为答案

import java.util.Scanner;
    import java.util.regex.Matcher;
    import java.util.regex.Pattern;
    
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		String input = scanner.nextLine();
    		input = input.trim();
    		System.out.println(method(input).length());
    		scanner.close();
    	}
    
    	public static String method(String string) {
    		if (check(string)) {
    			return findMax(string);
    		}
    		String regex = "[(]x*[|]x*[)]";
    		Pattern pattern = Pattern.compile(regex);
    		Matcher matcher = pattern.matcher(string);
    		while (matcher.find()) {
    			String str = matcher.group();
    			String str2 = findMax(str);
    			str = str.replaceAll("[(]", "[(]");
    			str = str.replaceAll("[|]", "[|]");
    			str = str.replaceAll("[)]", "[)]");
    			string = string.replaceAll(str, str2);
    		}
    		return method(string);
    	}
    
    	// (xx|xxxxx) 转化为 xxxx
    	public static String findMax(String string) {
    		if (!string.contains("|"))
    			return string;
    		string = string.replaceAll("[(]|[)]", "");
    		String[] strings = string.split("[|]");
    		if (strings[0].length() >= strings[1].length()) {
    			return strings[0];
    		} else {
    			return strings[1];
    		}
    	}
    
    	// 检查字符串是否含有"|"和"(" ")"
    	public static boolean check(String string) {
    		return !string.contains("(") && !string.contains(")");
    	}
    }

## 8-包子凑数 ##

>   
> 标题：包子凑数
> 
> 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
> 
> 每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
> 
> 当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
> 
> 小明想知道一共有多少种数目是包子大叔凑不出来的。
> 
> 输入  
> \----  
> 第一行包含一个整数N。(1 <= N <= 100)  
> 以下N行每行包含一个整数Ai。(1 <= Ai <= 100)  
> 
> 输出  
> \----  
> 一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
> 
> 例如，  
> 输入：  
> 2    
> 4    
> 5   
> 
> 程序应该输出：  
> 6  
> 
> 再例如，  
> 输入：  
> 2    
> 4    
> 6    
> 
> 程序应该输出：  
> INF
> 
> 样例解释：  
> 对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。    
> 对于样例2，所有奇数都凑不出来，所以有无限多个。  
> 
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 1000ms
> 
>   
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。  
> 提交程序时，注意选择所期望的语言类型和编译器类型。
> 
>

>  **分析：**
> 
> 这题应该算是这套题目除魔方那题以外最难的一题了，涉及的定理较多，我们一步一步分析
> 
> 首先简化一下题目：判断几个整数，在大于0的范围内，有多少个无法组成的数？
> 
> 根据欧几里得公式的推导，我们可以得出这样一个结论，
> 
> “ 如果两个数字不互素，则它们无法组成的数字有无限个，如果两个数互素，则它们无法组成的数字为有限个  ”
> 
> 这条定理的前半句和容易证明，两个不互素的数的和一定不为素数，而素数是由无穷个的，因此有无数个数不能被组成
> 
> 定理的后半段是这题的解题关键，如果我们排除了上面那种无数种的可能，那么现在我们的任务就是要找哪些数是不能被组成的，很明显我们需要一个搜索的范围，不可能去验证所有的数字，这里这样去思考一这个问题：
> 
> 假设我们需要寻找5 7这两个数所不能组成的数字，那么我们能否找到一个点，即连续的五个数字都可以被这两个数字组成，如果可以的话，那么这五个数字后的数字自然都可以被他们组成，不停的+5即可，便只用在这五个数字前的范围搜索无法组成的数字即可， 由公式可推导出，这五个数字在互素数间是一定存在的，且为 5\*7-(5+7)+1----->5\*7-(5+7)+5
> 
> 如此依赖，便可以在一定范围内求出无法组成的数字个数，这里还需要用到一点动态规划的思想，具体理解代码即可

import java.util.Scanner;
    
    public class Main {
    	static int dp[] = new int[10000];
    
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		int a[] = new int[200];
    		int n = 0, i, j, res = 0, mark = 0;
    		n = scanner.nextInt();
    		while (true) {
    			//获取数字数组
    			for (i = 1; i <= n; i++) {
    				a[i] = scanner.nextInt();
    			}
    			//找出这些数字中有没有互质的
    			for (i = 1; i <= n; i++) {
    				for (j = 1; j <= n; j++) {
    					if (gcd(a[i], a[j])) {
    						mark = 1;
    						break;
    					}
    				}
    				if (mark == 1)
    					break;
    			}
    			//无互质则由无限个拼凑不出来的数
    			if (mark != 1) {
    				System.out.println("INF");
    				continue;
    			}
    			
    			//动态规划求出范围内的每个数，能否被组成
    			dp[0] = 1;
    			for (i = 1; i <= n; i++)
    				for (j = 1; j < 10000; j++) {
    					if (a[i] > j)
    						continue;
    					if (dp[j - a[i]] == 1)
    						dp[j] = 1;
    				}
    			
    			
    			for (i = 0; i < 10000; i++) {
    				if (dp[i] != 1)
    					res++;
    			}
    			
    			System.out.println(res);
    		}
    		
    		
    	}
    	
    	//使用辗转相除法(欧几里得公式）验证两个数是否互素（最公约数为1）
    	public static boolean gcd(int x, int y) {
    		int t;
    		while (y > 0) {
    			t = x % y;
    			x = y;
    			y = t;
    		}
    		if (x == 1)
    			return true;
    		return false;
    	}
    }

## 9-分巧克力 ##

>   
> 标题： 分巧克力
> 
>     儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。  
>     小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
> 
>     为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
> 
>     1. 形状是正方形，边长是整数    
>     2. 大小相同  
> 
> 例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
> 
> 当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
> 
> 输入  
> 第一行包含两个整数N和K。(1 <= N, K <= 100000)    
> 以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)   
> 输入保证每位小朋友至少能获得一块1x1的巧克力。   
> 
> 输出  
> 输出切出的正方形巧克力最大可能的边长。
> 
> 样例输入：  
> 2 10    
> 6 5    
> 5 6  
> 
> 样例输出：  
> 2
> 
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 1000ms
> 
>   
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。

> **分析：**
> 
> 这题也较为简单，未涉及太多的算法
> 
> 只需逐次列出分割的巧克力块儿大小，然后依次验证可行性，直到求出最优解

import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		// 巧克力数量
    		int num = scanner.nextInt();
    		// 小朋友人数
    		int a = scanner.nextInt();
    		int[][] arr = new int[num][2];
    		// 巧克力数组
    		for (int i = 0; i < num; i++) {
    			arr[i][0] = scanner.nextInt();
    			arr[i][1] = scanner.nextInt();
    		}
    		// 逐次增加分割的块边长
    		for (int i = 1; i < 100000; i++) {
    			// 可以分割的块数
    			int m = splitAll(arr, i);
    			if (m >= a)
    				continue;
    			if (m < a) {
    				System.out.println(i - 1);
    				break;
    			}
    		}
    
    	}
    
    	/**
    	 * 求出所有巧克力能将分多少块
    	 */
    	public static int splitAll(int[][] arr, int sideLenght) {
    		int count = 0;
    		for (int i = 0; i < arr.length; i++) {
    			count = count + split(arr[i][0], arr[i][1], sideLenght);
    		}
    		return count;
    	}
    
    	/**
    	 * 求出一块巧克力能将分多少块
    	 */
    	public static int split(int height, int width, int sideLenght) {
    		int x = height / sideLenght;
    		int y = width / sideLenght;
    		return x * y;
    	}
    }

## 10-油漆面积 ##

>   
> 标题：油漆面积
> 
> X星球的一批考古机器人正在一片废墟上考古。  
> 该区域的地面坚硬如石、平整如镜。  
> 管理人员为方便，建立了标准的直角坐标系。
> 
> 每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。  
> 经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。
> 
> 矩形的表示格式为(x1,y1,x2,y2)，代表矩形的两个对角点坐标。
> 
> 为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。  
> 小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。
> 
> 其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。  
> 注意，各个矩形间可能重叠。
> 
> 本题的输入为若干矩形，要求输出其覆盖的总面积。
> 
> 输入格式：  
> 第一行，一个整数n，表示有多少个矩形(1<=n<10000)  
> 接下来的n行，每行有4个整数x1 y1 x2 y2，空格分开，表示矩形的两个对角顶点坐标。  
> (0<= x1,y1,x2,y2 <=10000)
> 
> 输出格式：  
> 一行一个整数，表示矩形覆盖的总面积。
> 
> 例如，  
> 输入：  
> 3  
> 1 5 10 10  
> 3 1 20 20  
> 2 7 15 17
> 
> 程序应该输出：  
> 340
> 
> 再例如，  
> 输入：  
> 3  
> 5 2 10 6  
> 2 7 12 10  
> 8 1 15 15
> 
> 程序应该输出：  
> 128
> 
> 资源约定：  
> 峰值内存消耗（含虚拟机） < 256M  
> CPU消耗  < 2000ms  
> 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
> 
> 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。  
> 不要使用package语句。不要使用jdk1.7及以上版本的特性。  
> 主类的名字必须是：Main，否则按无效代码处理。

> **分析：**
> 
> 这题虽放在最后一题，但感觉是本卷最容易的一题，只需要准备一个10000\*10000的boolean数组，初始值为false，当输入一个坐标后，将该坐标内包含的范围设置为true，等所有坐标输入完成后，算出为true的方格即可得出答案

import java.util.Scanner;
    
    public class Main {
    	public static void main(String[] args) {
    		boolean[][] map = new boolean[10000][10000];
    		Scanner scanner = new Scanner(System.in);
    		int num = scanner.nextInt();
    		for (int i = 0; i < num; i++) {
    			int x1 = scanner.nextInt();
    			int y1 = scanner.nextInt();
    			int x2 = scanner.nextInt();
    			int y2 = scanner.nextInt();
    			for (int x = x1; x < x2; x++) {
    				for (int y = y1; y < y2; y++) {
    					map[x][y] = true;
    				}
    			}
    		}
    		int count = 0;
    		for (int i = 0; i < 10000; i++) {
    			for (int j = 0; j < 10000; j++) {
    				if (map[i][j]) {
    					count++;
    				}
    			}
    		}
    		System.out.println(count);
    
    	}
    
    }

## 总结 ##

**主要难点集中在两题，主要考点集中在递归，深度搜索，动态规划**

[20200820121340568.png]: /images/20221124/a2fbc5ae5aad4485bea84b69da4fd0f8.png
[20200820122254930.png]: /images/20221124/653d8f81ba154f87925c69b52135e016.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMDEzMDM1_size_16_color_FFFFFF_t_70]: /images/20221124/d3be9fc62a164bdeb560e1086b5a978e.png