From ：http://blog.csdn.net/liuqiyao_01/article/details/8757800

好几天前老师说有测试赛，我一直没拿到题，所以一直没做，今天ll老师发到了群里，我就下载下来做了，感觉题目挺难，难度和去年软件大赛决赛c本科一个水准。。想在两个小时之内做完必须有聪哥那样的水平，我差不多一共用了3个半小时才做完，可能是因为我Java学的挺差的。。Java功底雄厚的童鞋，完全可以秒杀我。。

题目在这里：点击打开下载链接

第一题:连续平方数

题目描述：

为了表示方便，我们把5的平方记为：5^2
这样，连续自然数的平方和就记为：1^2 + 2^2 + 3^2 + 4^2 + ...

请看下面的公式：

1^2 + 2^2 + 3^2 + 4^2 + ... + x^2 = y^2

是不是存在整数x,y，使得公式成立呢？显然x=y=1 勉强成立，数学上称为“平凡解”。

你的任务是寻找该方程的某个非平凡解(实际上只有1个)。

请填写该公式中x所代表的数字。
注意不要填写多余的内容。

答案与得分：

24 得分10分

分析：

纯暴力就行。。。代码如下

代码：

[java] view plaincopy

1. public class test1 {  
2.     public static void main(String[] args) {  
3.   
4.         int [] num = new int[110];  
5.         num[0] = 0;  
6.         int i, j;  
7.         for (i = 1; i < 100; i++) {  
8.             num[i] = num[i - 1] + i * i;  
9.             for (j = i; j * j <= num[i]; j++) {  
10.                 if (j * j == num[i])  
11.                     System.out.println(i + " " + j);  
12.             }  
13.         }  
14.   
15.     }  
16. }  

第二题：硬币方案

题目描述：

有50枚硬币，可能包括4种类型：1元，5角，1角，5分。
已知总价值为20元。求各种硬币的数量。
比如：2,34,6,8 就是一种答案。
而 2,33,15,0 是另一个可能的答案，显然答案不唯一。

你的任务是确定类似这样的不同的方案一共有多少个（包括已经给出的2个）？

直接提交该数字，不要提交多余的内容。

答案与得分：

50 得分16分

分析：

(PS:如果不知道dp是啥，或者感觉无从下手的，就先看背包九讲中的第一部分01背包，然后再做我博客里面DP背包专辑中01背包的部分，做完前11道题，再敲一下完全背包的前两题，然后这道题就很轻松了。。。)

看到这道题第一反应就是dp，如果换做一年前的话就是暴搜了，暴搜肯定能出结果，但是效率、空间各方面都不如dp，而且如果这道题放在OJ上面，暴搜一般就会TLE掉。

dp的状态转移方程如下：

for (i = 0; i < 4; i++) 
        for (j = 1; j <= 50; j++) 
                for (k = 400; k >= coin[i]; k--) 
                        dp[j][k] += dp[j-1][k-coin[i]];

实际上就是一个递推，dp[j][k] 表示硬币个数在j以内，弄出k块钱的解法的个数。

代码：

[java] view plaincopy

1. public class test2 {  
2.   
3.     public static void main(String[] args) {  
4.   
5.         int[] coin = { 1, 2, 10, 20 };  //所有给出硬币价值除以 5分，优化  
6.         int[][] dp = new int[55][440]; // dp[j][k] 表示 硬币个数在j以内，弄出k块钱的解法的个数  
7.         dp[0][0] = 1;  
8.   
9.         int i, j, k;  
10.         for (i = 0; i < 4; i++) {  
11.             for (j = 1; j <= 50; j++) {  
12.                 for (k = 400; k >= coin[i]; k--) {  
13.                     dp[j][k] += dp[j-1][k-coin[i]];  
14.                 }  
15.             }  
16.         }  
17.         System.out.println(dp[50][400]);  
18.     }  
19.   
20. }  

第三题：连续公倍数

题目描述：

为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。

我们希望寻找到能除尽1至n的的每个数字的最小整数。

不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800

为此，有必要使用BigInteger来记录这样的大数。

请阅读下面的代码，填写缺失的部分（下划线部分）。

[java] view plaincopy

1. import java.math.BigInteger;  
2. public class My1  
3. {  
4.     // 求能除尽1~n 每个数字的最小整数  
5.     public static BigInteger f(int n)  
6.     {  
7.         int[] x = new int[n+1];  
8.           
9.         for(int i=1; i<=n; i++) x[i] = i;  
10.           
11.         for(int i=2; i<n; i++)  
12.         {  
13.             for(int j=i+1; j<=n; j++)  
14.             {  
15.                 if(x[j] % x[i]==0) _______________;   // 填空位置  
16.             }  
17.         }  
18.           
19.         BigInteger m = BigInteger.ONE;  
20.         for(int i=2; i<=n; i++)  
21.         {  
22.             m = m.multiply(BigInteger.valueOf(x[i]));   
23.         }  
24.           
25.         return m;  
26.               
27.     }  
28.       
29.     public static void main(String[] args)  
30.     {  
31.         System.out.println(f(30));    
32.     }  
33. }  

答案与得分：

x[j] /= x[i]    18分

分析：

额。。怎么说呢。。每次做填空题就是凭着感觉。。就做出来了。。

第四题：二阶魔方

题目描述：

魔方可以对它的6个面自由旋转。


我们来操作一个2阶魔方（如图1所示）
为了描述方便，我们为它建立了坐标系。

各个面的初始状态如下：
x轴正向：绿
x轴反向：蓝
y轴正向：红
y轴反向：橙
z轴正向：白
z轴反向：黄

假设我们规定，只能对该魔方进行3种操作。分别标记为：
x 表示在x轴正向做顺时针旋转
y 表示在y轴正向做顺时针旋转
z 表示在z轴正向做顺时针旋转

基本旋转后的效果如图2,3,4所示。


xyz 则表示顺序执行x,y,z 3个操作

题目的要求是：
从标准输入获得一个串，表示操作序列。
程序输出：距离我们最近的那个小方块的3个面的颜色。
顺序是：x面，y面，z面。

例如：在初始状态，应该输出：
绿红白

初始状态下，如果用户输入：
x
则应该输出：
绿白橙

初始状态下，如果用户输入：
zyx
则应该输出：
红白绿

样例输入：

xy
xxyyy
xyzzzzyyyxxx
xyyzzz
xyxyzzxyxyzz

样例输出：

红白绿
白红蓝
绿红白
黄绿橙
白绿红

得分：

5组数据，正确数据个数*5  满分25

分析：

其实这道题可以通过对编号来进行找规律，从而更快更有效的来重置魔方，但是本弱菜太菜了。。只能通过手工画图，然后一一对比，找到转换魔方编号的方法。。。相当于纯暴力，代码比较容易读懂。。下图是我画的图。。

每个格子表示颜色，白色用灰色代替了。。每四个小格子组成一个大格子，左上角写了他属于一开始的哪一个面，

用直线画的是每一种转法。。。可能会有点乱，少有不慎就会有错误结果

代码：

[java] view plaincopy

1. import java.util.Scanner;  
2.   
3. public class test4 {  
4.   
5.     public static void main(String[] args) {  
6.   
7.         int[] number = new int[24];  
8.         int[] num = new int[24];  
9.         int[] newnum = new int[24];  
10.         int[] flag = { 1, 8, 19 };  
11.   
12.         number[0] = number[1] = number[2] = number[3] = 1; // x正面 绿色  
13.         number[4] = number[5] = number[6] = number[7] = 2; // x背面 蓝色  
14.         number[8] = number[9] = number[10] = number[11] = 3; // y正面 红色  
15.         number[12] = number[13] = number[14] = number[15] = 4; // y背面 橙色  
16.         number[16] = number[17] = number[18] = number[19] = 5; // z正面 白色  
17.         number[20] = number[21] = number[22] = number[23] = 6; // z背面 黄色  
18.   
19.         // newnum = num;  
20.         // for (int i = 0; i < 24; i++)  
21.         // System.out.print(newnum[i] + " ");  
22.   
23.         String str;  
24.         char[] ch = new char[1000];  
25.         Scanner cin = new Scanner(System.in);  
26.         while (cin.hasNext()) {  
27.             str = cin.nextLine();  
28.   
29.             for (int i = 0; i < 24; i++)  
30.                 num[i] = number[i];  
31.             ch = str.toCharArray();  
32.             int len = ch.length;  
33.   
34.             for (int i = 0; i < len; i++) {  
35.                 for (int j = 0; j < 24; j++)  
36.                     newnum[j] = num[j];  
37.                 if (ch[i] == 'x') {  
38.                     newnum[20] = num[10];  
39.                     newnum[21] = num[8];  
40.                     newnum[10] = num[19];  
41.                     newnum[8] = num[18];  
42.                     newnum[19] = num[13];  
43.                     newnum[18] = num[15];  
44.                     newnum[13] = num[20];  
45.                     newnum[15] = num[21];  
46.                     newnum[0] = num[2];  
47.                     newnum[1] = num[0];  
48.                     newnum[3] = num[1];  
49.                     newnum[2] = num[3];  
50.                 } else if (ch[i] == 'y') {  
51.                     newnum[17] = num[1];  
52.                     newnum[19] = num[3];  
53.                     newnum[1] = num[21];  
54.                     newnum[3] = num[23];  
55.                     newnum[21] = num[5];  
56.                     newnum[23] = num[7];  
57.                     newnum[5] = num[17];  
58.                     newnum[7] = num[19];  
59.                     newnum[8] = num[10];  
60.                     newnum[9] = num[8];  
61.                     newnum[11] = num[9];  
62.                     newnum[10] = num[11];  
63.                 } else if (ch[i] == 'z') {  
64.                     newnum[0] = num[8];  
65.                     newnum[1] = num[9];  
66.                     newnum[8] = num[7];  
67.                     newnum[9] = num[6];  
68.                     newnum[7] = num[12];  
69.                     newnum[6] = num[13];  
70.                     newnum[12] = num[0];  
71.                     newnum[13] = num[1];  
72.                     newnum[16] = num[18];  
73.                     newnum[17] = num[16];  
74.                     newnum[19] = num[17];  
75.                     newnum[18] = num[19];  
76.                 }  
77.                 for (int j = 0; j < 24; j++)  
78.                     num[j] = newnum[j];  
79.             }  
80.   
81.             for (int i = 0; i < 3; i++) {  
82.                 // System.out.println(num[flag[i]]);  
83.                 if (num[flag[i]] == 1) {  
84.                     System.out.print("绿");  
85.                 } else if (num[flag[i]] == 2) {  
86.                     System.out.print("蓝");  
87.                 } else if (num[flag[i]] == 3) {  
88.                     System.out.print("红");  
89.                 } else if (num[flag[i]] == 4) {  
90.                     System.out.print("橙");  
91.                 } else if (num[flag[i]] == 5) {  
92.                     System.out.print("白");  
93.                 } else if (num[flag[i]] == 6) {  
94.                     System.out.print("黄");  
95.                 }  
96.             }  
97.             System.out.println();  
98.         }  
99.   
100.     }  
101. }  

第五题：分红酒

题目描述：

  有4个红酒瓶子，它们的容量分别是：9升, 7升, 4升, 2升
  
  开始的状态是 [9,0,0,0]，也就是说：第一个瓶子满着，其它的都空着。

  允许把酒从一个瓶子倒入另一个瓶子，但只能把一个瓶子倒满或把一个瓶子倒空，不能有中间状态。这样的一次倒酒动作称为1次操作。
  假设瓶子的容量和初始状态不变，对于给定的目标状态，至少需要多少次操作才能实现？
  本题就是要求你编程实现最小操作次数的计算。
  输入：最终状态（逗号分隔）
  输出：最小操作次数（如无法实现，则输出-1）

例如：
输入：
9,0,0,0
应该输出：
0

输入：
6,0,0,3
应该输出：
-1

输入：
7,2,0,0
应该输出：
2

样例输入：

2 4 1 2

3 1 3 2
2 6 1 0

样例输出：

6
9
7

得分：

3组测试数据   正确个数*10.333   满分31

分析：

先通过队列来进行bfs，来枚举出每一种状态下的情况，保存在num数字里，每种情况都得到最优结果，然后再直接输出结果就行了。。。如果有不会的再问我就行。。。不难，就是超级麻烦。。。我大约敲了一个半小时才敲出来。。。

代码：

[java] view plaincopy

1. package test;  
2.   
3. import java.util.LinkedList;  
4. import java.util.Queue;  
5. import java.util.Scanner;  
6.   
7. class state {  
8.     int a, b, c, d, step;  
9.   
10.     state() {  
11.         step = 0;  
12.     }  
13.   
14.     state(int x, int y, int z, int q, int p) {  
15.         a = x;  
16.         b = y;  
17.         c = z;  
18.         d = q;  
19.         step = p;  
20.     }  
21. }  
22.   
23. public class test5 {  
24.   
25.     static int inf = 0x3f3f3f3f;  
26.     static int[] full = { 9, 7, 4, 2 };  
27.     static int[][][][] num = new int[10][8][5][3];  
28.     static Queue<state> queue = new LinkedList<state>();  
29.   
30.     public static void judge(int a, int b, int c, int d, int step) {  
31.   
32.         if (num[a][b][c][d] > step + 1) { // 判断是否可以更新  
33.             num[a][b][c][d] = step + 1;  
34.             state tmp = new state(a, b, c, d, step + 1);  
35.             queue.add(tmp); // 可以更新则入队列  
36.         }  
37.     }  
38.   
39.     public static void main(String[] args) {  
40.   
41.         queue.clear();  
42.   
43.         int i, j, k, q;  
44.         for (i = 0; i < 10; i++)  
45.             for (j = 0; j < 8; j++)  
46.                 for (k = 0; k < 5; k++)  
47.                     for (q = 0; q < 3; q++)  
48.                         num[i][j][k][q] = inf;  
49.         num[9][0][0][0] = 0;  
50.         state sta = new state(9, 0, 0, 0, 0);  
51.         queue.add(sta);  
52.   
53.         while (queue.size() > 0) { // bfs  
54.             sta = queue.poll();  
55.             int[] tmpnum = { sta.a, sta.b, sta.c, sta.d, sta.step };  
56. //          System.out.println(tmpnum[0] + " " + tmpnum[1] + " " + tmpnum[2]  
57. //                  + " " + tmpnum[3] + " " + tmpnum[4]);  
58.             for (i = 0; i < 4; i++) {  
59.   
60.                 int tmpi = tmpnum[i]; // 保存第i个  
61. /////----------------------------------将i倒满------------------------------------------//////  
62.                 int cha = full[i] - tmpnum[i];  
63.                 tmpnum[i] = full[i];  
64.                 judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// 判断是否可以更新  
65.                 tmpnum[i] = tmpi; // 还原第i个数  
66.   
67.                 if (tmpnum[i] == 0)  
68.                     continue;  
69.                   
70. /////-----------------------------------将i倒空-----------------------------------------//////  
71.                 tmpnum[i] = 0; // 将第i个置为0  
72.                 judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// 判断是否可以更新  
73.                 tmpnum[i] = tmpi; // 还原第i个数  
74.                   
75. /////---------------------------------将i倒给j-------------------------------------------//////  
76.                 for (j = 0; j < 4; j++) { // 依次将第i个瓶子倒入第j个瓶子  
77.                     if (j == i || tmpnum[j] == full[j])  
78.                         continue; // 如果第j个瓶子满了则continue  
79.                     int tmpj = tmpnum[j];  
80.                     cha = full[j] - tmpnum[j]; // 第j个瓶子还能到进去多少水  
81.                     if (tmpnum[i] >= cha) { // 如果tmpnum[i]中的水足够多可以倒进去  
82.                         tmpnum[i] -= cha;  
83.                         tmpnum[j] += cha;  
84.                     } else { // 不夠多的情況  
85.                         tmpnum[j] += tmpnum[i];  
86.                         tmpnum[i] = 0;  
87.                     }  
88.                     judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// 判断是否可以更新  
89.                     tmpnum[i] = tmpi; // 还原第i个数  
90.                     tmpnum[j] = tmpj;// 还原第j个数  
91.   
92.                 }  
93.             }  
94.         }  
95.   
96.         Scanner cin = new Scanner(System.in);  
97.         while (cin.hasNext()) {  
98.             int a, b, c, d;  
99.             a = cin.nextInt();  
100.             b = cin.nextInt();  
101.             c = cin.nextInt();  
102.             d = cin.nextInt();  
103.   
104.             if (a > full[0] || b > full[1] || c > full[2] || d > full[3]  
105.                     || num[a][b][c][d] == inf) {  
106.                 System.out.println("-1");  
107.                 continue;  
108.             }  
109.             System.out.println(num[a][b][c][d]);  
110.         }  
111.   
112.     }  
113. }