2017第八届蓝桥杯省赛JAVA A组真题解析（带源码及解析）

绝地灬酷狼 2022-11-19 01:28 248阅读 0赞

## [蓝桥杯历年真题及解析][Link 1]. ##

### 目录： ###

*   *  蓝桥杯历年真题及解析.
     *   *  A：迷宫（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  B：九数算式（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  C：魔方还原（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  D：方格分割（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  E：字母拼串（难度：★）
         *   *  题目：
             *  分析：
             *  代码：
         *  F：最大公共子串（难度：★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  G：正则问题（难度：★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  H：包子凑数（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  I：分巧克力（难度：★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  J：油漆面积（难度：★★★★★）
         *   *  题目：
             *  分析：
             *  代码：
         *  算法交流群：

### A：迷宫（难度：★） ###

#### 题目： ####

X星球的一处迷宫游乐场建在某个小山坡上。  
它是由10x10相互连通的小房间组成的。

房间的地板上写着一个很大的字母。  
我们假设玩家是面朝上坡的方向站立，则：  
L表示走到左边的房间，  
R表示走到右边的房间，  
U表示走到上坡方向的房间，  
D表示走到下坡方向的房间。

X星球的居民有点懒，不愿意费力思考。  
他们更喜欢玩运气类的游戏。这个游戏也是如此！

开始的时候，直升机把100名玩家放入一个个小房间内。  
玩家一定要按照地上的字母移动。

迷宫地图如下：  
UDDLUULRUL  
UURLLLRRRU  
RRUURLDLRD  
RUDDDDUUUU  
URUDLLRRUU  
DURLRLDLRL  
ULLURLLRDU  
RDLULLRDDD  
UUDDUDUDLL  
ULRDLUURRR

请你计算一下，最后，有多少玩家会走出迷宫?  
而不是在里边兜圈子。

请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。

如果你还没明白游戏规则，可以参看一个简化的4x4迷宫的解说图：  
![在这里插入图片描述][20210414092354117.png]

#### 分析： ####

枚举10\*10的所有位置，查看是否可以从该位置走到数组外边，  
最终计数即可。  
注意需要解决死循环（兜圈子）问题。  
答案=31

#### 代码： ####

满分

public class A迷宫 { 
        static String s[]={ "UDDLUULRUL",
                "UURLLLRRRU",
                "RRUURLDLRD",
                "RUDDDDUUUU",
                "URUDLLRRUU",
                "DURLRLDLRL",
                "ULLURLLRDU",
                "RDLULLRDDD",
                "UUDDUDUDLL",
                "ULRDLUURRR"};
        static char c[][]=new char [10][10];
        public static void main(String[] args) { 
            for(int i=0;i<10;i++){ 
                c[i]=s[i].toCharArray();
            }
            int fin=0;
            for(int i=0;i<10;i++){ 
                for(int j=0;j<10;j++){ 
                    boolean vis[][]=new boolean[10][10];
                    int x=i,y=j;
                    while(x>=0&&y>=0&&x<10&&y<10&&!vis[x][y]){ 
                        vis[x][y]=true;
                        if(c[x][y]=='U'){ 
                            x--;
                        }else if(c[x][y]=='D'){ 
                            x++;
                        }else if(c[x][y]=='L'){ 
                            y--;
                        }else if(c[x][y]=='R'){ 
                            y++;
                        }
                    }
                    if(x<0||y<0||x>=10||y>=10){ 
                        fin++;
                    }
                }
            }
            System.out.println(fin);
        }
    }

### B：九数算式（难度：★★） ###

#### 题目： ####

观察如下的算式：

9213 x 85674 = 789314562

左边的乘数和被乘数正好用到了1~9的所有数字，每个1次。  
而乘积恰好也是用到了1~9的所有数字，并且每个1次。

请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？

注意：

1.  总数目包含题目给出的那个示例。
2.  乘数和被乘数交换后作为同一方案来看待。

#### 分析： ####

全排列问题，枚举所有排列，对所有排列顺序进行检查即可。  
答案=1625

#### 代码： ####

满分

public class B9数算式 { 
        public static int arr[]={ 1,2,3,4,5,6,7,8,9};
        public static int ans=0,cnt=0;
        public static long toint(int b,int e){ 
            long res=0;
            for(int i=b;i<=e;i++){ 
                res*=10;
                res+=arr[i];
            }
            return res;
        }
        public static boolean check(long x){ 
            if(String.valueOf(x).length()!=9)return false;
            int count[]=new int[10];
            while(x!=0){ 
                count[(int) (x%10)]++;
                x/=10;
            }
            for(int i=1;i<10;i++){ 
                if(count[i]!=1)return false;
            }
            return true;
        }
        public static void qpl(int k){ 
            if(k>=arr.length){ 
                for(int i=0;i<arr.length-1;i++){ 
                    cnt++;
                    long a=toint(0,i);
                    long b=toint(i+1,arr.length-1);
                    if(check(a*b))ans++;
                }
            }else{ 
                for(int i=k;i<arr.length;i++){ 
                    int t=arr[i];arr[i]=arr[k];arr[k]=t;
                    qpl(k+1);
                    t=arr[i];arr[i]=arr[k];arr[k]=t;
                }
            }
        }
        public static void main(String[] args) { 
            qpl(0);
            System.out.println(ans/2);
        }
    }

### C：魔方还原（难度：★★★★★） ###

#### 题目： ####

二阶魔方就是只有2层的魔方，只由8个小块组成。  
如图p1.png所示。

小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：

前面：橙色  
右面：绿色  
上面：黄色  
左面：绿色  
下面：橙色  
后面：黄色

请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。

如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。

请提交表示状态数的整数，不要填写任何多余内容或说明文字。  
![在这里插入图片描述][20210414092437869.png]

#### 分析： ####

这个不是给人做的，神仙才能做。。。

#### 代码： ####

AC代码，但不是我自己写的

import java.util.*;
    
    class MFState { 
    	public int a;
    	public int b;
    	public int c;
    
    	public MFState(char[] x) { 
    
    		for (int i = 0; i < 8; i++) { 
    			a = a * 10 + (x[i] - '0');
    		}
    		for (int i = 8; i < 16; i++) { 
    			b = b * 10 + (x[i] - '0');
    		}
    		for (int i = 16; i < 24; i++) { 
    			c = c * 10 + (x[i] - '0');
    		}
    	}
    
    	public int hashCode() { 
    		return a * 600 * 600 + b * 600 + c;
    	}
    
    	public boolean equals(Object other) { 
    		if (other instanceof MFState == false)
    			return false;
    		MFState m = (MFState) other;
    		return a == m.a && b == m.b && c == m.c;
    	}
    
    	public char[] getState() { 
    		String s = String.format("%8d%8d%8d", a, b, c);
    		return s.toCharArray();
    	}
    
    	public String toString() { 
    		return new String(getState());
    	}
    }
    
    public class C魔方状态 { 
    	// 某个面顺时针旋转
    	static int[][][] ACT = {  {  {  0, 1, 2, 3 }, {  4, 17, 14, 23 }, {  7, 16, 13, 22 } }, // 前
    			{  {  8, 9, 10, 11 }, {  5, 20, 15, 18 }, {  6, 21, 12, 19 } }, // 后
    			{  {  4, 5, 6, 7 }, {  1, 21, 11, 17 }, {  2, 22, 8, 18 } }, // 右
    			{  {  12, 13, 14, 15 }, {  0, 16, 10, 20 }, {  3, 19, 9, 23 } }, // 左
    			{  {  20, 21, 22, 23 }, {  0, 12, 8, 4 }, {  1, 13, 9, 5 } }, // 上
    			{  {  16, 17, 18, 19 }, {  2, 6, 10, 14 }, {  3, 7, 11, 15 } } }; // 下
    
    	// 同态变换
    	static int[][] SAME = new int[24][];
    
    	// 基本变换
    	static int[][] BASE = new int[9][];
    
    	///
    
    	// 用ACT 第k个，对a状态进行变换
    	static char[] f(char[] a, int k) { 
    		char[] b = new char[a.length];
    		for (int i = 0; i < b.length; i++)
    			b[i] = a[i];
    
    		for (int i = 0; i < ACT[k].length; i++) { 
    			for (int j = 0; j < ACT[k][i].length; j++) { 
    				b[ACT[k][i][(j + 1) % ACT[k][i].length]] = a[ACT[k][i][j]];
    			}
    		}
    
    		return b;
    	}
    
    	// 返回恒等变换
    	static int[] t_id() { 
    		int[] r = new int[24];
    		for (int i = 0; i < r.length; i++)
    			r[i] = i;
    		return r;
    	}
    
    	// ACT第k条转为变换
    	static int[] a_to_t(int k) { 
    		int[] b = new int[24];
    		for (int i = 0; i < b.length; i++)
    			b[i] = i;
    
    		for (int i = 0; i < ACT[k].length; i++) { 
    			for (int j = 0; j < ACT[k][i].length; j++) { 
    				b[ACT[k][i][(j + 1) % ACT[k][i].length]] = ACT[k][i][j];
    			}
    		}
    
    		return b;
    	}
    
    	// 变换x与y的复合
    	static int[] t_t(int[] x, int[] y) { 
    		int[] r = new int[x.length];
    		for (int i = 0; i < y.length; i++) { 
    			r[i] = x[y[i]];
    		}
    		return r;
    	}
    
    	// 变换t，作用于a，返回变换结果
    	static char[] g(char[] a, int[] t) { 
    		char[] r = new char[a.length];
    		for (int i = 0; i < t.length; i++) { 
    			r[i] = a[t[i]];
    		}
    		return r;
    	}
    
    	// 对状态a 进行同态变换，返回结果
    	static char[][] tong(char[] a) { 
    		char[][] aa = new char[SAME.length][];
    
    		for (int i = 0; i < SAME.length; i++) { 
    			aa[i] = g(a, SAME[i]);
    		}
    
    		return aa;
    	}
    
    	// 执行一系列ACT，生成等效变换，
    	static int[] act_to_t(int[] act) { 
    		int[] r = t_id();
    		for (int i = 0; i < act.length; i++) { 
    			r = t_t(r, a_to_t(act[i]));
    		}
    		return r;
    	}
    
    	static { 
    		// 24种同态
    		SAME[0] = act_to_t(new int[] { });
    		SAME[1] = act_to_t(new int[] {  4, 5, 5, 5 });
    		SAME[2] = act_to_t(new int[] {  4, 4, 5, 5 });
    		SAME[3] = act_to_t(new int[] {  4, 4, 4, 5 });
    		SAME[4] = act_to_t(new int[] {  2, 3, 3, 3 });
    		SAME[5] = act_to_t(new int[] {  2, 3, 3, 3, 0, 1, 1, 1 });
    		SAME[6] = act_to_t(new int[] {  2, 3, 3, 3, 0, 0, 1, 1 });
    		SAME[7] = act_to_t(new int[] {  2, 3, 3, 3, 0, 0, 0, 1 });
    		SAME[8] = act_to_t(new int[] {  2, 2, 3, 3 });
    		SAME[9] = act_to_t(new int[] {  2, 2, 3, 3, 4, 5, 5, 5 });
    		SAME[10] = act_to_t(new int[] {  2, 2, 3, 3, 4, 4, 5, 5 });
    		SAME[11] = act_to_t(new int[] {  2, 2, 3, 3, 4, 4, 4, 5 });
    		SAME[12] = act_to_t(new int[] {  2, 2, 2, 3 });
    		SAME[13] = act_to_t(new int[] {  2, 2, 2, 3, 0, 1, 1, 1 });
    		SAME[14] = act_to_t(new int[] {  2, 2, 2, 3, 0, 0, 1, 1 });
    		SAME[15] = act_to_t(new int[] {  2, 2, 2, 3, 0, 0, 0, 1 });
    		SAME[16] = act_to_t(new int[] {  0, 1, 1, 1 });
    		SAME[17] = act_to_t(new int[] {  0, 1, 1, 1, 3, 2, 2, 2 });
    		SAME[18] = act_to_t(new int[] {  0, 1, 1, 1, 3, 3, 2, 2 });
    		SAME[19] = act_to_t(new int[] {  0, 1, 1, 1, 3, 3, 3, 2 });
    		SAME[20] = act_to_t(new int[] {  0, 0, 0, 1 });
    		SAME[21] = act_to_t(new int[] {  0, 0, 0, 1, 3, 2, 2, 2 });
    		SAME[22] = act_to_t(new int[] {  0, 0, 0, 1, 3, 3, 2, 2 });
    		SAME[23] = act_to_t(new int[] {  0, 0, 0, 1, 3, 3, 3, 2 });
    
    		// 9种转法
    		BASE[0] = act_to_t(new int[] {  2 });
    		BASE[1] = act_to_t(new int[] {  2, 2 });
    		BASE[2] = act_to_t(new int[] {  2, 2, 2 });
    		BASE[3] = act_to_t(new int[] {  0 });
    		BASE[4] = act_to_t(new int[] {  0, 0 });
    		BASE[5] = act_to_t(new int[] {  0, 0, 0 });
    		BASE[6] = act_to_t(new int[] {  4 });
    		BASE[7] = act_to_t(new int[] {  4, 4 });
    		BASE[8] = act_to_t(new int[] {  4, 4, 4 });
    	}
    
    	public static void main(String[] args) { 
    		// char[] a = "111111113333444411111111".toCharArray();
    		// char[] a = "111122223333222211113333".toCharArray();
    		char[] a = "111122223333444455556666".toCharArray();
    		Set set = new HashSet();
    		set.add(new MFState(a));
    
    		for (int w = 0; w < 12; w++) { 
    			Set set2 = new HashSet();
    			for (Object obj : set) { 
    				MFState it = (MFState) obj;
    				L1: for (int i = 0; i < BASE.length; i++) { 
    					char[] ag = g(it.getState(), BASE[i]);
    					char[][] ag_tong = tong(ag);
    					for (int j = 0; j < ag_tong.length; j++) { 
    						if (set.contains(new MFState(ag_tong[j])))
    							continue L1;
    						if (set2.contains(new MFState(ag_tong[j])))
    							continue L1;
    					}
    					set2.add(new MFState(ag_tong[0]));
    					// if(set.contains(ag)) continue;
    					// if(set2.contains(ag)) continue;
    					// set2.add(new MFState(ag));
    				}
    			}
    			if (set2.isEmpty())
    				break;
    			System.out.print("+ " + set2.size());
    			set.addAll(set2);
    			System.out.println("= " + set.size());
    		}
    
    		System.out.println("final: " + set.size());
    	}
    }

### D：方格分割（难度：★★★★） ###

#### 题目： ####

6x6的方格，沿着格子的边线剪开成两部分。  
要求这两部分的形状完全相同。

如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]

就是可行的分割法。

试计算：  
包括这3种分法在内，一共有多少种不同的分割方法。  
注意：旋转对称的属于同一种分割法。

请提交该整数，不要填写任何多余的内容或说明文字。

#### 分析： ####

通过二进制枚举所有局面，随后对每种局面进行Check联通，  
当同色连通块只有一个并且连通块大小为18的时候则表示分割成功。  
计数加一，枚举结束计数即为结果。  
答案=509

#### 代码： ####

满分

public class D方格分割 { 
        public static int map[][]=new int[6][6];
        public static boolean buf[][];
        public static int check(int x,int y){ 
            int sum=1;
            if(x+1>=0&&x+1<6&&!buf[x+1][y]&&map[x][y]==map[x+1][y]){ 
                buf[x+1][y]=true;
                sum+=check(x+1,y);
            }
            if(x-1>=0&&x-1<6&&!buf[x-1][y]&&map[x][y]==map[x-1][y]){ 
                buf[x-1][y]=true;
                sum+=check(x-1,y);
            }
            if(y+1>=0&&y+1<6&&!buf[x][y+1]&&map[x][y]==map[x][y+1]){ 
                buf[x][y+1]=true;
                sum+=check(x,y+1);
            }
            if(y-1>=0&&y-1<6&&!buf[x][y-1]&&map[x][y]==map[x][y-1]){ 
                buf[x][y-1]=true;
                sum+=check(x,y-1);
            }
            return sum;
        }
        public static void main(String[] args) { 
            int ans=0;
            for(int i=0;i<Math.pow(2, 18);i++){ 
                int tmp=i;
                for(int j=0;j<6;j++){ 
                    for(int k=0;k<3;k++){ 
                        map[k][j]=tmp%2;
                        map[5-k][5-j]=1-tmp%2;
                        tmp/=2;
                    }
                }
                buf=new boolean [6][6];
                buf[0][0]=true;
                if(check(0,0)==18)ans++;
            }
            System.out.println(ans/4);
        }
    }

### E：字母拼串（难度：★） ###

#### 题目： ####

由 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

#### 分析： ####

枚举第 i 个字符一共有3种情况，要么 A 要么 B，要么 C；三种情况相加即可。  
答案=f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1)

#### 代码： ####

满分

public class E字母组串
    { 
    	// 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);
    // return ________________________________; //填空
    	}
    	
    	public static void main(String[] args)
    	{ 
    		System.out.println(f(1,1,1,2));
    		System.out.println(f(1,2,3,3));
    	}
    }

### F：最大公共子串（难度：★★） ###

#### 题目： ####

最大公共子串长度问题就是：  
求两个串的所有子串中能够匹配上的最大长度是多少。

比如：“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);
    	}
    }

#### 分析： ####

注意题目所找的是连续串，跟DP没有关系，所以我们只需要直接拿上边的值+1即可。  
答案=a\[i-1\]\[j-1\]+1

#### 代码： ####

满分

public class F最大公共子串
    { 
    	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][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("abcdkkk", "baabcdadabc");
    		System.out.println(n);
    	}
    }

### G：正则问题（难度：★★★★） ###

#### 题目： ####

考虑一种简单的正则表达式：  
只由 x ( ) | 组成的正则表达式。  
小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。

输入  
一个由x()|组成的正则表达式。输入长度不超过100，保证合法。

输出  
这个正则表达式能接受的最长字符串的长度。

例如，  
输入：  
((xx|xxx)x|(x|xx))xx

程序应该输出：  
6

#### 分析： ####

保证数据合法？  
你确定？  
一直正确75%，翻出来数据才发现最后两组样例括号不配对。。。。

思路是将大的字符串以括号为单位分割成小的字符串，再用“或”的方式求解即可。  
简言之就是切割字符串进行DFS。  
![在这里插入图片描述][20210415161130228.png]

#### 代码： ####

import java.io.FileWriter;
    import java.io.IOException;
    import java.math.*;
    import java.util.*;
     
    public class G正则问题 { 
        public static String max(String a,String b){ 
            return a.length()>b.length()?a:b;
        }
        public static String dfs(String s){ 
            if(!s.contains("(")&&!s.contains("|")){ 
                return s;
            }else if(!s.contains("(")&&s.contains("|")){ 
                return max(s.substring(0,s.indexOf("|")),dfs(s.substring(s.indexOf("|")+1)));
            }else if(s.contains("(")&&!s.contains("|")){ 
                return s.replace("(", "").replace(")", "");
            }else { 
                String s0=s.substring(0,s.indexOf("(")),s1="",s2="";
                int cnt=1;
                for(int i=s.indexOf("(")+1;i<s.length();i++){ 
                    if(s.charAt(i)=='(')cnt++;
                    else if(s.charAt(i)==')'){ 
                        cnt--;
                        if(cnt==0){ 
                            if(i==s.length()-1){ 
                                s1=s.substring(s.indexOf("(")+1,i);
                                s2="";
                            }else{ 
                                s1=s.substring(s.indexOf("(")+1,i);
                                s2=s.substring(i+1);
                            }
                            break;
                        }
                    }
                }
                return dfs(s0+dfs(s1)+s2);
            }
        }
        public static void main(String[] args) throws IOException { 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
            	String s=sc.nextLine().replace(" ", "");
            	int cnt=0;
            	for(int i=0;i<s.length();i++)
            		if(s.charAt(i)=='(')cnt++;
            		else if(s.charAt(i)==')')cnt--;
            	if(cnt!=0)s+=')';
                s=dfs(s);
                System.out.println(s.length());
            }
        }
    }

### H：包子凑数（难度：★★★） ###

#### 题目： ####

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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，所有奇数都凑不出来，所以有无限多个。

#### 分析： ####

因为数据范围有限，所以我们枚举1000000个位置，  
如果GCD！=1就说明他们无法凑出的数目是INF个  
如果GCD==1就说明他们在数据较大时可以凑出来，  
所以枚举1~1000000，检查那个数字是他们所凑不出来的，并进行计数。  
计数即为结果。

#### 代码： ####

![在这里插入图片描述][20210414095202355.png]

import java.util.Scanner;
    
    public class H包子凑数{ 
        public static int gcd(int x,int y){ 
            if(y==0)return x;
            else return gcd(y, x%y);
        }
        public static void main(String[] args) { 
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            int arr[]=new int[n];
            boolean buf[]=new boolean[1000000];
            arr[0]=scanner.nextInt();
            int gcd=arr[0];
            for(int i=1;i<n;i++){ 
                arr[i]=scanner.nextInt();
                gcd=gcd(gcd,arr[i]);
            }
            if(gcd!=1){ 
                System.out.println("INF");
                return ;
            }
            buf[0]=true;
            for(int i=0;i<buf.length;i++){ 
                for(int j=0;j<n;j++){ 
                    if(i>=arr[j]&&buf[i-arr[j]]){ 
                        buf[i]=true;
                    }
                }
            }
            int ans=0;
            for(int i=0;i<buf.length;i++){ 
                if(!buf[i])ans++;
            }
            System.out.println(ans);
        }
    }

### I：分巧克力（难度：★★★） ###

#### 题目： ####

儿童节那天有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

#### 分析： ####

用二分法枚举切出的巧克力边长，并Check可行性，  
当n可行，n+1不可行时，n即为结果。

#### 代码： ####

![在这里插入图片描述][20210414095328792.png]

import java.util.*;
     
    public class I分巧克力 { 
        public static int h[],w[],n,k;
        public static boolean check(int size){ 
            int sum=0;
            for(int i=0;i<n;i++){ 
                sum+=(w[i]/size)*(h[i]/size);
            }
            return sum>=k;
        }
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
            k=sc.nextInt();
            h=new int[n];
            w=new int[n];
            for(int i=0;i<n;i++){ 
                h[i]=sc.nextInt();
                w[i]=sc.nextInt();
            }
            int l=0,r=100000,m=0;
            while(l<=r){ 
                m=(l+r)/2;
                boolean test0=check(m),test1=check(m+1);
                if(test0&&!test1){ 
                    break;
                }else if(test0&&test1){ 
                    l=m+1;
                }else{ 
                    r=m-1;
                }
            }
            System.out.println(m);
             
        }
    }

### J：油漆面积（难度：★★★★★） ###

#### 题目： ####

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

#### 分析： ####

//稍候

#### 代码： ####

//稍候

### 算法交流群： ###

![在这里插入图片描述][20210414095431714.png]

[Link 1]: https://blog.csdn.net/qq_43652327/article/details/104899994
[20210414092354117.png]: /images/20221022/da57a01952654d69bf3d85643157424e.png
[20210414092437869.png]: /images/20221022/232fd6158e094b52b71f1d05cf38d147.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20221022/7557928921f14029b44d8e7e65bdd562.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20221022/061e890ae68c4a02891c728cdad336eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20221022/a893feff2b4844faa3a622e5098f8db9.png
[20210415161130228.png]: /images/20221022/9fdc9473b6a94cac84f2a9226bca6a09.png
[20210414095202355.png]: /images/20221022/0dab54bfa8e64a30a4169e27b27b2419.png
[20210414095328792.png]: /images/20221022/9bb72534e4834027ae413ec5ca83b10d.png
[20210414095431714.png]: /images/20221022/357b771aacb24d1b97b44f4723400991.png