蓝桥杯第八届省赛java

Excel地址
k倍区间
日期问题
拉马车
迷宫
方块分割
最大公共子串
正则问题
承压计算
分巧克力
油漆面积
包子凑数
字母组串

一、Excel地址

Excel单元格的地址表示很有趣，它使用字母来表示列号。比如， A表示第1列， B表示第2列， Z表示第26列， AA表示第27列， AB表示第28列， BA表示第53列， .... BB54 当然Excel的最大列号是有限度的，所以转换起来不难。如果我们想把这种表示法一般化，可以把很大的数字转换为很长的字母序列呢？本题目既是要求对输入的数字, 输出其对应的Excel地址表示方式。

例如，输入： 26 则程序应该输出： Z

再例如，输入： 2054 则程序应该输出： BZZ

我们约定，输入的整数范围[1,2147483647] 资源约定：峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。主类的名字必须是：Main，否则按无效代码处理。

笨笨有话说：这有点像进制关系，又不完全是。好像末2位是以1当26，末3位是以1当26*26 歪歪有话说：要是从字母序列转数字还好点，倒过来有点麻烦，不过计算机跑得快啊。

思路：一开始没看到下面的两对话，做题时切记先把题看全，不然浪费很多时间！！！

完整代码：

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[] iA = new int[5000];
		int n = in.nextInt();
		int i = 1;
		while (n != 0) {
			if (n % 26 == 0) {
				// +64转大写字母，+96转小写字母
				iA[i] = 26 + 64;
				n -= 1;
			} else {
				iA[i] = n % 26 + 64;
			}
			n /= 26;
			i++;
		}
		for (int j = i - 1; j > 0; j--) {
			System.out.print((char)iA[j]);
		}
	}
}

二、k倍区间

给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？

输入

第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)

输出

输出一个整数，代表K倍区间的数目。

例如，输入： 5 2 1
2
3
4
5

程序应该输出： 6

资源约定：峰值内存消耗（含虚拟机） < 256M CPU消耗 < 2000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。

主类的名字必须是：Main，否则按无效代码处理。

思路：题目中的例子6种情况为：2 4 123 345 1234 2345 。这不是一道难度很大的题，至少在理解上是的，但是一般思路做出来的方法肯定是得不了满分的，这可能也是蓝桥杯的另一种“套路”吧，将题目的理解变简单，但是要求变困难。这里就更能体现出算法的重要性。

一开始上来就这直接暴力求了，结果做完时间复杂度为O(n^3)，严重超时，甚至还有一个非常不必要的嵌套。

import java.util.Scanner;
public class Main {
	static int n = 0;
	static int k = 0;
	static int[] a;
	static int cnt = 0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		k = in.nextInt();
		a = new int[n+1];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				if (sum(i, j)% k == 0) {
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
	private static int sum(int i, int j) {
		// TODO Auto-generated method stub
		int s = 0;
		for (int k = i; k <= j; k++) {
			s += a[k];
		}
		return s;
	}
}

接下来，消除嵌套之后，时间复杂度降到了O(n^{2)，但实际上这个题目必须达到线性O(n}2)才能得到满分。

import java.util.Scanner;
public class Main {
	static int n = 0;
	static int k = 0;
	static int[] a;
	static int cnt = 0;
	static int sum;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		k = in.nextInt();
		a = new int[n+1];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		
		for (int i = 0; i < n; i++) {
			sum = 0;
			for (int j = i; j < n; j++) {
				sum += a[k];
				if (sum % k == 0) {
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}
}

参考了大神的代码2017第八届蓝桥杯C/C++ B组省赛题解

下面这个代码非常巧妙，将前缀和保存到数组中，减少每次不必要的嵌套计算，而同时%k会产生两种结果，0或者小于k，这相当于直接记录了符合（%k = 0）与不符合（%k < k）两种情况。根据（sum[r] - sum[l-1]） % k == 0 就可以判断一个区间[l, r]是符合约束区间。但是这样会使用双重循环，时间复杂度为O(n^2)，这样并没有完全把这种算法的好处利用到，而且我们的目的是计算个数，而非要输出所有的k倍区间。

根据上面的式子我们可以看出只要区间两端点的前缀和%k相等，那么这段区间就符合约束，所以我们只需每次使sum加上与当前位置前缀和%k相等的数量（即bk[a[i]]++）就行。

（注意最后的结果还要加上前缀和%k=0的值，这是它自身到1的区间，也符合约束。）

import java.util.Scanner;
public class Main {
	static int n = 0;
	static int k = 0;
	static int sum;
	static int[] a;
	static int[] bk;
	static int cnt = 0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		k = in.nextInt();
		a = new int[n+1];
		bk = new int[n+1];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		a[0] %= k;
		for (int i = 1; i < n; i++) {
			a[i] = (a[i] + a[i-1]) % k;
		}
		for (int i = 0; i < n; i++) {
			sum += (bk[a[i]]++);
		}
		System.out.println(sum + " "+ bk[0]);
	}
}

三、日期问题

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。
比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入

一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

输入

输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。

样例输入

02/03/04

样例输出

2002-03-04
2004-02-03
2004-03-02

资源约定：峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。主类的名字必须是：Main，否则按无效代码处理。

思路：异常混乱的题目，限制条件非常多。看似简单，实则陷阱重重月份的范围在0-12之间天数受到月份的限制 2月的天数还受到闰年的限制输出按顺序，注意不能出现重复的如03/03/03 输出一个2003-03-03

完整代码如下：

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
class Date {
	int year;
	int month;
	int day;
	public Date(int year, int month, int day) {
		this.year = year;
		this.month = month;
		this.day = day;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		if (month < 10 || day < 10) {
			return year + "-0" + month + "-0" + day;
		}
		return year + "-" + month + "-" + day;
	}
}
public class Main {
	static int[] md = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
	static String[] str = new String[3];
	static Date[] date = new Date[6];
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		 String s = in.next();
		 str = s.split("/");
		 int a = Integer.valueOf(str[0]);
		 int b = Integer.valueOf(str[1]);
		 int c = Integer.valueOf(str[2]);
		 // 年月日
		 date[0] = new Date(1900+a, b, c);
		 date[1] = new Date(2000+a, b, c);
		 // 月日年
		 date[2] = new Date(1900+c, a, b);
		 date[3] = new Date(2000+c, a, b);
		 // 日月年
		 date[4] = new Date(1900+c, b, a);
		 date[5] = new Date(2000+c, b, a);
		 // 排序，重写Comparator接口的compare方法，保证按顺序输出
		 Arrays.sort(date, new Comparator<Date>() {
			 @Override
			 public int compare(Date d1, Date d2) {
				if (d1.year == d2.year) {
					if (d1.month == d2.month) {
						return (int) d1.day - d2.day;
					}return (int) d1.month - d2.month;
				}
				return (int) d1.year - d2.year;
			 }
			});
		 // 避免重复	 
		Set<String> set = new HashSet<String>();
		for (int i = 0; i < date.length; i++) {
			if (vial(date[i]) && !set.contains(date[i].toString())) {
				set.add(date[i].toString());
				System.out.println(date[i].toString());
			}
		}
	}
	// 用于判断日期是否符合规则，规则很多
	private static boolean vial(Date d) {
		if (d.year < 1960 || d.year > 2059) {
			return false;
		}
		if (d.month <= 0 || d.month > 12) {
			return false;
		}
		if (d.year % 400 == 0 || d.year % 100 != 0 && d.year % 4 == 0) {
			if (d.month == 2) {
				return d.day >= 1 && d.day <= 29;
			}
			return d.day >= 1 && d.day <= md[d.month];
		} else {
			return d.day >= 1 && d.day <= md[d.month];
		}
	}
}

四、拉马车

小的时候，你玩过纸牌游戏吗？有一种叫做“拉马车”的游戏，规则很简单，却很吸引小朋友。其规则简述如下：假设参加游戏的小朋友是A和B，游戏开始的时候，他们得到的随机的纸牌序列如下： A方：[K, 8, X, K, A, 2, A, 9, 5, A] B方：[2, 7, K, 5, J, 5, Q, 6, K, 4]

其中的X表示“10”，我们忽略了纸牌的花色。从A方开始，A、B双方轮流出牌。当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。

此例中，游戏过程： A出K，B出2，A出8，B出7，A出X，此时桌上的序列为： K,2,8,7,X 当轮到B出牌时，他的牌K与桌上的纸牌序列中的K相同，则把包括K在内的以及两个K之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。此时，A、B双方的手里牌为： A方：[K, A, 2, A, 9, 5, A] B方：[5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]

赢牌的一方继续出牌。也就是B接着出5，A出K，B出J，A出A，B出5，又赢牌了。 5,K,J,A,5 此时双方手里牌： A方：[2, A, 9, 5, A] B方：[Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]

注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。对于本例的初始手牌情况下，最后A会输掉，而B最后的手里牌为： 9K2A62KAX58K57KJ5 本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出-1。输入为2行，2个串，分别表示A、B双方初始手里的牌序列。输出为1行，1个串，表示A先出牌，最后赢的一方手里的牌序。例如，输入： 96J5A898QA 6278A7Q973

则程序应该输出： 2J9A7QA6Q6889977

再比如，输入： 25663K6X7448 J88A5KJXX45A

则程序应该输出： 6KAJ458KXAX885XJ645

我们约定，输入的串的长度不超过30 资源约定：峰值内存消耗（含虚拟机） < 256M CPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。不要使用package语句。不要使用jdk1.7及以上版本的特性。主类的名字必须是：Main，否则按无效代码处理。

笨笨有话说：不断删除前边的，又要后边添加.... 如果用数组，需要开一个大点的，请佛祖保佑在游戏结束前，不会用到数组的边缘。歪歪有话说：反正串也不长，不如每次操作都返回一个新的串。默默有话说：我一般都不吱声，这是典型的队列结构，动态数组最好，没有？自己造一个呗！思路：对于这种双方交替进行的题目还是理解不好，这个题目简单来说就是对数据结构的运用，比如采用ArrayList（由于操作会有插入的操作，如果用普通的数组的话不太容易控制大小，推荐使用动态数组或者链式的其他结构，而且由于操作的是char类型，所以泛型写成Character更方便操作）可以使用remove(0)直接移出首个元素，而indexOf可以找到指定元素，最巧妙的是lastindexOf()可以找到元素上一次出现的位置。基本逻辑就是双方交替，交替之前要完成数据的插入与删除，还要记录这次处理的数据temp。其中如果数据处理完后出现出现可取牌的情况，则需要完成补牌的过程。每次都要判断是否出现一方无牌的情况，以保证程序的终止。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
    static char temp;
    static boolean ok = true;
    static boolean flag = true;
    static ArrayList<Character> a = new ArrayList<Character>();
    static ArrayList<Character> b = new ArrayList<Character>();
    static ArrayList<Character> onging = new ArrayList<Character>();
    public static void main(String[] args) {
        String str;
        Scanner input = new Scanner(System.in);
        //输入
        str = input.next();
        for (char cha : str.toCharArray()) {
        	a.add(cha);
        }
        str = input.next();
        for (char cha : str.toCharArray()) {
        	b.add(cha);
        }
        
        //执行
        while (ok) {
            if (flag) {
                ok = underway(a, onging);
                  if(ok) {
                  	flag = sourse(flag, a, onging);
                  }
            } else {
                ok = underway(b, onging);
                if(ok) {
                	flag = sourse(flag, b, onging);
                }
            }
        }
        
		// 打印
		if(flag){
			Iterator<Character> it = b.iterator();
			while (it.hasNext()) {
				System.out.print(it.next());
			}
		} else {
			Iterator<Character> it = a.iterator();
			while (it.hasNext()) {
				System.out.print(it.next());
			}
		}
    }
    
    //出牌
    public static boolean underway(ArrayList<Character> x, ArrayList<Character> onging) {
            temp = x.remove(0);
            onging.add(temp);
            // 如果其中一方没牌或者出现一次可赢局面（可以拿走牌的情况）
            if(x.size() == 0 && onging.lastIndexOf(temp) == onging.indexOf(temp)) {
                return false;
            }
            return true;
    }


    public static boolean sourse(boolean flag, ArrayList<Character> x, ArrayList<Character> onging) {
        if(onging.size() != 0) {
        	// temp出现的位置更新说明，又出现了一个temp，取牌后继续执行；反之，没有出现相同的，下个人执行
              if(onging.lastIndexOf(temp) == onging.indexOf(temp)) {
                  return !flag;
              }
              int end = onging.indexOf(temp) - 1;
              // 将lastIndex---Index中间的添加到x中，同时从ongoing中移出
              while (onging.size()-1 != end) {
                  int onMax = onging.size()-1;
                  x.add(onging.get(onMax));
                  onging.remove(onMax);
                }
        }
        return flag;
    }
}

五、迷宫

X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则： L表示走到左边的房间， R表示走到右边的房间， U表示走到上坡方向的房间， D表示走到下坡方向的房间。

X星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！开始的时候，直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。

迷宫地图如下：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

请你计算一下，最后，有多少玩家会走出迷宫? 而不是在里边兜圈子。请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。如果你还没明白游戏规则，可以参看一个简化的4x4迷宫的解说图：解析：思路一：最简单的方法就是逐个排查，反正就10*10的矩阵，数据量也不是很大，用Excel可以做好，只不过容易出现漏掉的情况。在比赛中如果不是实在没思路了，还是要谨慎使用这种方法，很容易花不少时间最后结果还错了。 这里写图片描述思路二：这里注意字符串的读取方式，注意每次循环都要初始化boolean[]

public class Main
{
	static char[][] a = new char[10][10];
	static boolean[][] b = new boolean[10][10];
	static int cnt = 0;
	public static void main(String[] args) {
		String str="UDDLUULRULUURLLLRRRURRUURLDLRDRUDDDDUUUUURUDLLRRUUDURLRLDLRLULLURLLRDURDLULLRDDDUUDDUDUDLLULRDLUURRR";  
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				a[i][j] = str.charAt(i*10+j);
			}
		}

		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				int x = i;
				int y = j;
				init();
				while (true) {
					if (x < 0 || x > 9 || y < 0 || y > 9) {
						cnt++;
						break;
					}
					if  (b[x][y] == true) {
						break;
					}
					b[x][y] = true;
					switch (a[x][y]) {
					case 'U':
						x -= 1;
						break;
					case 'D':
						x += 1;
						break;
					case 'L':
						y -= 1;
						break;
					case 'R':
						y += 1;
						break;
					default:
						break;
					}
				}
			}
		}
		System.out.println(cnt);
	}
	private static void init() {
		// TODO Auto-generated method stub
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				b[i][j] = false;
			}
		}
	}
}

六、方格分割

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

解析：从中心N/2开始进行深搜，需要定义方向数组dir[][]和记录数组vis[][]

public class Main
{
	static int[][] a = new int[6][6];
	static boolean[][] vis = new boolean[10][10];
	static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	static int cnt = 0;
	public static void main(String[] args) {
		vis[3][3] = true;
		f(3, 3);
		System.out.println(cnt/4);
	}
	private static void f(int x, int y) {
		// TODO Auto-generated method stub
		if (x == 0 || x == 6 || y == 0 || y == 6) {
			cnt++;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int dx = x + dir[i][0];
			int dy = y + dir[i][1];
			if (dx < 0 || dx > 6 || dy < 0 || dy > 6) {
				continue;
			}
			if (vis[dx][dy] == false) {
				vis[dx][dy] = true;
				vis[6-dx][6-dy] = true;
				f(dx, dy);
				vis[6-dx][6-dy] = false;
				vis[dx][dy] = false;
			}
			
		}
	}
}

七、最大公共子串

最大公共子串长度问题就是：求两个串的所有子串中能够匹配上的最大长度是多少。比如："abcdkkk" 和 "baabcdadabc"，可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。请分析该解法的思路，并补全划线部分缺失的代码。

解析：如果c1[i-1]与c2[j-1]相等，那么a[i][j]是要在a[i-1][j-1]的基础上+1再进行判断的。

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);
	}
}

八、正则问题

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

输入一个由x()|组成的正则表达式。输入长度不超过100，保证合法。
输出这个正则表达式能接受的最长字符串的长度。

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

程序应该输出： 6

解析：字符串处理，当碰到“x”，计数器a++；当碰到“|”，比较两边哪个大，因为统计一直是用a做的，所以这里直接将a赋给b，a置0；当碰到“(”，递归调用；当碰到“)”，返回max(a, b)即可。

import java.util.Scanner;

public class Main {
	static String str;
	static int cnt = 0;
	static int i = -1;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		str = in.next();
		cnt = f();
		System.out.println(cnt);
	}
	private static int f() {
		// TODO Auto-generated method stub
		int a = 0, b = 0;
		while (i < str.length() - 1) {
			i++;
			if (str.charAt(i) == 'x') {
				a++;
			} else if (str.charAt(i) == '|') {
				b = Math.max(a, b);
				a = 0;
			} else if (str.charAt(i) == '(') {
				a+= f();
			} else {
				return Math.max(a, b);
			}
		}
		return a;
	}
}

九、承压计算

X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。每块金属原料的外形、尺寸完全一致，但重量不同。金属材料被严格地堆放成金字塔形。

                             7 
                            5 8 
                           7 8 8 
                          9 2 7 2 
                         8 1 4 9 1 
                        8 1 8 8 4 1 
                       7 9 6 1 4 5 4 
                      5 6 5 5 6 9 5 6 
                     5 5 4 7 9 3 5 5 1 
                    7 5 7 9 7 4 7 3 3 1 
                   4 6 4 5 5 8 8 3 2 4 3 
                  1 1 3 3 1 6 6 5 5 4 4 2 
                 9 9 9 2 1 9 1 9 2 9 5 7 9 
                4 3 3 7 7 9 3 6 1 3 8 8 3 7 
               3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 
              8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 
             8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 
            2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 
           7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 
          9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 
         5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 
        6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 
       2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 
      7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 
     1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 
    2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 
   7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9 
  7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6 
 5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1 
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X

其中的数字代表金属块的重量（计量单位较大）。最下一层的X代表30台极高精度的电子秤。假设每块原料的重量都十分精确地平均落在下方的两个金属块上，最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。电子秤的计量单位很小，所以显示的数字很大。工作人员发现，其中读数最小的电子秤的示数为：2086458231

请你推算出：读数最大的电子秤的示数为多少？注意：需要提交的是一个整数，不要填写任何多余的内容。

解析：题目很好理解，主要要用double类型的二维数组，模拟题目要求，最后求出max和min，由于不知道实际读数，所以这里用比例式来求实际的min：实际的max = 求得的min ：求得的max

public class Main {
	static double[][] a = {
		{7, },
		{5, 8, }, 
		{7, 8, 8, },
		{9, 2, 7, 2, },
		{8, 1, 4, 9, 1, },
		{8, 1, 8, 8, 4, 1, },
		{7, 9, 6, 1, 4, 5, 4, },
		{5, 6, 5, 5, 6, 9, 5, 6, },
		{5, 5, 4, 7, 9, 3, 5, 5, 1, },
		{7, 5, 7, 9, 7, 4, 7, 3, 3, 1, },
		{4, 6, 4, 5, 5, 8, 8, 3, 2, 4, 3, },
		{1, 1, 3, 3, 1, 6, 6, 5, 5, 4, 4, 2, },
		{9, 9, 9, 2, 1, 9, 1, 9, 2, 9, 5, 7, 9, },
		{4, 3, 3, 7, 7, 9, 3, 6, 1, 3, 8, 8, 3, 7, },
		{3, 6, 8, 1, 5, 3, 9, 5, 8, 3, 8, 1, 8, 3, 3, },
		{8, 3, 2, 3, 3, 5, 5, 8, 5, 4, 2, 8, 6, 7, 6, 9, },
		{8, 1, 8, 1, 8, 4, 6, 2, 2, 1, 7, 9, 4, 2, 3, 3, 4, },
		{2, 8, 4, 2, 2, 9, 9, 2, 8, 3, 4, 9, 6, 3, 9, 4, 6, 9, },
		{7, 9, 7, 4, 9, 7, 6, 6, 2, 8, 9, 4, 1, 8, 1, 7, 2, 1, 6, },
		{9, 2, 8, 6, 4, 2, 7, 9, 5, 4, 1, 2, 5, 1, 7, 3, 9, 8, 3, 3, },
		{5, 2, 1, 6, 7, 9, 3, 2, 8, 9, 5, 5, 6, 6, 6, 2, 1, 8, 7, 9, 9, },
		{6, 7, 1, 8, 8, 7, 5, 3, 6, 5, 4, 7, 3, 4, 6, 7, 8, 1, 3, 2, 7, 4, },
		{2, 2, 6, 3, 5, 3, 4, 9, 2, 4, 5, 7, 6, 6, 3, 2, 7, 2, 4, 8, 5, 5, 4, },
		{7, 4, 4, 5, 8, 3, 3, 8, 1, 8, 6, 3, 2, 1, 6, 2, 6, 4, 6, 3, 8, 2, 9, 6, },
		{1, 2, 4, 1, 3, 3, 5, 3, 4, 9, 6, 3, 8, 6, 5, 9, 1, 5, 3, 2, 6, 8, 8, 5, 3, },
		{2, 2, 7, 9, 3, 3, 2, 8, 6, 9, 8, 4, 4, 9, 5, 8, 2, 6, 3, 4, 8, 4, 9, 3, 8, 8, },
		{7, 7, 7, 9, 7, 5, 2, 7, 9, 2, 5, 1, 9, 2, 6, 5, 3, 9, 3, 5, 7, 3, 5, 4, 2, 8, 9, },
		{7, 7, 6, 6, 8, 7, 5, 5, 8, 2, 4, 7, 7, 4, 7, 2, 6, 9, 2, 1, 8, 2, 9, 8, 5, 7, 3, 6, },
		{5, 9, 4, 5, 5, 7, 5, 5, 6, 3, 5, 3, 9, 5, 8, 9, 5, 4, 1, 2, 6, 1, 4, 3, 5, 3, 2, 4, 1, },
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
	};
	static double max = 0;
	static double min = 99999999;
	public static void main(String[] args) {
		for (int i = 1; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				if (j == 0) {
					a[i][j] += a[i-1][j] / 2.0;
				} else if (j == a[i].length - 1) {
					a[i][j] += a[i-1][j-1] / 2.0;
				} else {
					a[i][j] += a[i-1][j] / 2.0 + a[i-1][j-1] / 2.0;
				}
			}
		}
		
		for (int i = 0; i < 30; i++) {
			if (a[29][i] < min) {
				min = a[29][i];
			}
			if (a[29][i] > max) {
				max = a[29][i];
			}
			
		}
		System.out.println(2086458231 / min * max);
	}
}

十、分巧克力

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

形状是正方形，边长是整数
大小相同

例如一块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

解析：对于这个题目，我们可能会纠结与如何保证多块巧克力同时能够被切割成指定块数。其实不过是枚举罢了，我们从大到小进行枚举，找到一个最大的分发能够满足指定块数就可以了。下面采用了二分法进行查找合适大小。

import java.util.Scanner;
class Cho {
	int h;
	int w;
	public Cho(int h, int w) {
		// TODO Auto-generated constructor stub
		this.h = h;
		this.w = w;
	}
}
public class Main2 {
	static int n, k;
	static Cho[] cho;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		k = in.nextInt();
		int low = 1;
		int mid = 0;
		int high = 100000;
		cho = new Cho[n];
		for (int i = 0; i < n; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			cho[i] = new Cho(a, b);
		}
//		二分，基本思路为暴力，从大到小能够保证最先出来的结果就是符合要求的最大情况
		while (low < high -1) {
			mid = (low + high) /2;
			if (!judge(mid)) {
				high = mid;
			} else {
				low = mid;
			}
		}
		System.out.println(mid - 1);
		
	}
	private static boolean judge(int l) {
		// TODO Auto-generated method stub
		int sum = 0;
		for (int i = 0; i < n; i++) {
			sum += (cho[i].h * cho[i].w) / (l * l);
			if (sum >= k) {
				return true;
			}
		}
		return false;
	}
}

十一、油漆面积

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，否则按无效代码处理。

解析：不知道是自己想简单了还是怎么，这道题感觉并不符合最后一个题目的难度，不知道各位大神能否提示一下。

import java.util.Scanner;

public class Main {
	static int n, sum = 0;
	static int[][] p = new int[10005][10005];
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		for (int i = 0; i < n; i++) {
			int x1 = in.nextInt();
			int y1 = in.nextInt();
			int x2 = in.nextInt();
			int y2 = in.nextInt();
			paint(x1, y1, x2, y2);
		}
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p[i].length; j++) {
				sum += p[i][j];
			}
		}
		System.out.println(sum);
	}
	private static void paint(int x1, int y1, int x2, int y2) {
		// TODO Auto-generated method stub
		for (int i = x1; i < x2; i++) {
			for (int j = y1; j < y2; j++) {
				p[i][j] = 1;
			}
		}
	}
}

十二、包子凑数

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

解析：这个问题只要用桶的方式暴力就可以了，只要是a[i]的倍数必定是能够取到的，题目稍微难一点的地方就在于INF情况的判断，这会涉及到拓展欧几里得算法，这是对欧几里得算法（辗转相除法）的一个拓展：对于不全为0的两个数a, b，如果我们用gec(a, b)表示a, b的最大公约数，那么必然存在整数对x, y，使得gad(a, b) = ax + by。也就是说如果a[i]这些数只要最大公倍数不是1，那么就不会出现INF。

import java.util.Scanner;

public class Main2 {
	static int n;
	static int[] a = new int[10005]; 
	static boolean[] vis; 
	static int sum = 0;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		vis = new boolean[10005];
		for (int i = 0; i < n; i++) {
			a[i] = in.nextInt();
		}
		int g = a[0];
		for (int i = 1; i < n; i++) {
			g = gcd(g, a[i]);
		}
		/**
		 * 拓展欧几里得：对于不全为0的两个数a,b，
		 * 如果我们用gcd(a,b)表示a,b的最大公约数，
		 * 那么必然存在整数对x,y, 使得gad(a,b) = ax+by
		 * */
		if (g != 1) {
			System.out.println("INF");
		} else {
			vis[0] = true;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j+a[i] < 10005; j++) {
					if (vis[j] == true) {
						vis[j + a[i]] = true;
					}
				}
			}
			for (int i = 0; i <= 10000-1; i++) {
				if (vis[i] == false) {
					sum++;
				}
			}
			System.out.println(sum);
		}
	}
	private static int gcd(int a, int b) {
		// TODO Auto-generated method stub
		if (b == 0) {
			return a;
		}
		return gcd(b, a%b);
	}
}

十三、字母组串

由 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

注意：只填写划线部分缺少的代码，不要提交任何多余内容或说明性文字。

答案：f(a-1, b, c, n-1)+f(a, b-1, c, n-1)+f(a, b, c-1, n-1) 解析：关于递归问题可以递归出口开始分析，这样会尽快找到递归变量。

n.xuanrui

退无可退，一往无前