2017第八屆藍橋杯省賽JAVA A組真題解析（帶源碼及解析）

藍橋杯曆年真題及解析.

目錄：

• • 藍橋杯曆年真題及解析.
  • • 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迷宮的解說圖：

分析：

枚舉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種顔色，所有把家裡的二階魔方重新塗了顔色，如下：

前面：橙色

右面：綠色

上面：黃色

左面：綠色

下面：橙色

後面：黃色

請你計算一下，這樣的魔方被打亂後，一共有多少種不同的狀态。

如果兩個狀态經過魔方的整體旋轉後，各個面的顔色都一緻，則認為是同一狀态。

請送出表示狀态數的整數，不要填寫任何多餘内容或說明文字。

分析：

這個不是給人做的，神仙才能做。。。

代碼：

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的方格，沿着格子的邊線剪開成兩部分。

要求這兩部分的形狀完全相同。

如圖：

就是可行的分割法。

試計算：

包括這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。

代碼：

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，檢查那個數字是他們所湊不出來的，并進行計數。

計數即為結果。

代碼：

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即為結果。

代碼：

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

分析：

//稍候

代碼：

//稍候

算法交流群：