蓝桥杯 2013 全国软件设计大赛 模拟赛 Java 本科B组 答题报告
蓝桥杯 2013 全国软件设计大赛 模拟赛 Java 本科B组 解题报告
好几天前老师说有测试赛，我一直没拿到题，所以一直没做，今天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分
分析：
纯暴力就行。。。代码如下
代码：
public class test1 {
public static void main(String[] args) {
int [] num = new int[110];
num[0] = 0;
int i, j;
for (i = 1; i < 100; i++) {
num[i] = num[i - 1] + i * i;
for (j = i; j * j <= num[i]; j++) {
if (j * j == num[i])
System.out.println(i + " " + j);
}
}
}
}
第二题：硬币方案
题目描述：
有50枚硬币，可能包括4种类型：1元，5角，1角，5分。
已知总价值为20元。求各种硬币的数量。
比如：2,34,6,8 就是一种答案。
而 2,33,15,0 是另一个可能的答案，显然答案不唯一。
你的任务是确定类似这样的不同的方案一共有多少个（包括已经给出的2个）？
直接提交该数字，不要提交多余的内容。
已知总价值为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]];
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块钱的解法的个数。
代码：
public class test2 {
public static void main(String[] args) {
int[] coin = { 1, 2, 10, 20 }; //所有给出硬币价值除以 5分，优化
int[][] dp = new int[55][440]; // dp[j][k] 表示 硬币个数在j以内，弄出k块钱的解法的个数
dp[0][0] = 1;
int i, j, k;
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]];
}
}
}
System.out.println(dp[50][400]);
}
}
第三题：连续公倍数
题目描述：
为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。
但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800
为此，有必要使用BigInteger来记录这样的大数。
请阅读下面的代码，填写缺失的部分（下划线部分）。
但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。
事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。
我们希望寻找到能除尽1至n的的每个数字的最小整数。
不要小看这个数字，它可能十分大，比如n=100, 则该数为：
69720375229712477164533808935312303556800
为此，有必要使用BigInteger来记录这样的大数。
请阅读下面的代码，填写缺失的部分（下划线部分）。
import java.math.BigInteger;
public class My1
{
// 求能除尽1~n 每个数字的最小整数
public static BigInteger f(int n)
{
int[] x = new int[n+1];
for(int i=1; i<=n; i++) x[i] = i;
for(int i=2; i<n; i++)
{
for(int j=i+1; j<=n; j++)
{
if(x[j] % x[i]==0) _______________; // 填空位置
}
}
BigInteger m = BigInteger.ONE;
for(int i=2; i<=n; i++)
{
m = m.multiply(BigInteger.valueOf(x[i]));
}
return m;
}
public static void main(String[] args)
{
System.out.println(f(30));
}
}
答案与得分：
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
则应该输出：
红白绿
我们来操作一个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
xxyyy
xyzzzzyyyxxx
xyyzzz
xyxyzzxyxyzz
样例输出：
红白绿
白红蓝
绿红白
黄绿橙
白绿红
白红蓝
绿红白
黄绿橙
白绿红
得分：
5组数据，正确数据个数*5 满分25
分析：
其实这道题可以通过对编号来进行找规律，从而更快更有效的来重置魔方，但是本弱菜太菜了。。只能通过手工画图，然后一一对比，找到转换魔方编号的方法。。。相当于纯暴力，代码比较容易读懂。。下图是我画的图。。
每个格子表示颜色，白色用灰色代替了。。每四个小格子组成一个大格子，左上角写了他属于一开始的哪一个面，
用直线画的是每一种转法。。。可能会有点乱，少有不慎就会有错误结果
代码：
import java.util.Scanner;
public class test4 {
public static void main(String[] args) {
int[] number = new int[24];
int[] num = new int[24];
int[] newnum = new int[24];
int[] flag = { 1, 8, 19 };
number[0] = number[1] = number[2] = number[3] = 1; // x正面 绿色
number[4] = number[5] = number[6] = number[7] = 2; // x背面 蓝色
number[8] = number[9] = number[10] = number[11] = 3; // y正面 红色
number[12] = number[13] = number[14] = number[15] = 4; // y背面 橙色
number[16] = number[17] = number[18] = number[19] = 5; // z正面 白色
number[20] = number[21] = number[22] = number[23] = 6; // z背面 黄色
// newnum = num;
// for (int i = 0; i < 24; i++)
// System.out.print(newnum[i] + " ");
String str;
char[] ch = new char[1000];
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
str = cin.nextLine();
for (int i = 0; i < 24; i++)
num[i] = number[i];
ch = str.toCharArray();
int len = ch.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < 24; j++)
newnum[j] = num[j];
if (ch[i] == 'x') {
newnum[20] = num[10];
newnum[21] = num[8];
newnum[10] = num[19];
newnum[8] = num[18];
newnum[19] = num[13];
newnum[18] = num[15];
newnum[13] = num[20];
newnum[15] = num[21];
newnum[0] = num[2];
newnum[1] = num[0];
newnum[3] = num[1];
newnum[2] = num[3];
} else if (ch[i] == 'y') {
newnum[17] = num[1];
newnum[19] = num[3];
newnum[1] = num[21];
newnum[3] = num[23];
newnum[21] = num[5];
newnum[23] = num[7];
newnum[5] = num[17];
newnum[7] = num[19];
newnum[8] = num[10];
newnum[9] = num[8];
newnum[11] = num[9];
newnum[10] = num[11];
} else if (ch[i] == 'z') {
newnum[0] = num[8];
newnum[1] = num[9];
newnum[8] = num[7];
newnum[9] = num[6];
newnum[7] = num[12];
newnum[6] = num[13];
newnum[12] = num[0];
newnum[13] = num[1];
newnum[16] = num[18];
newnum[17] = num[16];
newnum[19] = num[17];
newnum[18] = num[19];
}
for (int j = 0; j < 24; j++)
num[j] = newnum[j];
}
for (int i = 0; i < 3; i++) {
// System.out.println(num[flag[i]]);
if (num[flag[i]] == 1) {
System.out.print("绿");
} else if (num[flag[i]] == 2) {
System.out.print("蓝");
} else if (num[flag[i]] == 3) {
System.out.print("红");
} else if (num[flag[i]] == 4) {
System.out.print("橙");
} else if (num[flag[i]] == 5) {
System.out.print("白");
} else if (num[flag[i]] == 6) {
System.out.print("黄");
}
}
System.out.println();
}
}
}
第五题：分红酒
题目描述：
有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
开始的状态是 [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
2 6 1 0
样例输出：
6
9
7
9
7
得分：
3组测试数据 正确个数*10.333 满分31
分析：
先通过队列来进行bfs，来枚举出每一种状态下的情况，保存在num数字里，每种情况都得到最优结果，然后再直接输出结果就行了。。。如果有不会的再问我就行。。。不难，就是超级麻烦。。。我大约敲了一个半小时才敲出来。。。
代码：
package test;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class state {
int a, b, c, d, step;
state() {
step = 0;
}
state(int x, int y, int z, int q, int p) {
a = x;
b = y;
c = z;
d = q;
step = p;
}
}
public class test5 {
static int inf = 0x3f3f3f3f;
static int[] full = { 9, 7, 4, 2 };
static int[][][][] num = new int[10][8][5][3];
static Queue<state> queue = new LinkedList<state>();
public static void judge(int a, int b, int c, int d, int step) {
if (num[a][b][c][d] > step + 1) { // 判断是否可以更新
num[a][b][c][d] = step + 1;
state tmp = new state(a, b, c, d, step + 1);
queue.add(tmp); // 可以更新则入队列
}
}
public static void main(String[] args) {
queue.clear();
int i, j, k, q;
for (i = 0; i < 10; i++)
for (j = 0; j < 8; j++)
for (k = 0; k < 5; k++)
for (q = 0; q < 3; q++)
num[i][j][k][q] = inf;
num[9][0][0][0] = 0;
state sta = new state(9, 0, 0, 0, 0);
queue.add(sta);
while (queue.size() > 0) { // bfs
sta = queue.poll();
int[] tmpnum = { sta.a, sta.b, sta.c, sta.d, sta.step };
// System.out.println(tmpnum[0] + " " + tmpnum[1] + " " + tmpnum[2]
// + " " + tmpnum[3] + " " + tmpnum[4]);
for (i = 0; i < 4; i++) {
int tmpi = tmpnum[i]; // 保存第i个
/////----------------------------------将i倒满------------------------------------------//////
int cha = full[i] - tmpnum[i];
tmpnum[i] = full[i];
judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// 判断是否可以更新
tmpnum[i] = tmpi; // 还原第i个数
if (tmpnum[i] == 0)
continue;
/////-----------------------------------将i倒空-----------------------------------------//////
tmpnum[i] = 0; // 将第i个置为0
judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// 判断是否可以更新
tmpnum[i] = tmpi; // 还原第i个数
/////---------------------------------将i倒给j-------------------------------------------//////
for (j = 0; j < 4; j++) { // 依次将第i个瓶子倒入第j个瓶子
if (j == i || tmpnum[j] == full[j])
continue; // 如果第j个瓶子满了则continue
int tmpj = tmpnum[j];
cha = full[j] - tmpnum[j]; // 第j个瓶子还能到进去多少水
if (tmpnum[i] >= cha) { // 如果tmpnum[i]中的水足够多可以倒进去
tmpnum[i] -= cha;
tmpnum[j] += cha;
} else { // 不夠多的情況
tmpnum[j] += tmpnum[i];
tmpnum[i] = 0;
}
judge(tmpnum[0],tmpnum[1],tmpnum[2],tmpnum[3],tmpnum[4]);// 判断是否可以更新
tmpnum[i] = tmpi; // 还原第i个数
tmpnum[j] = tmpj;// 还原第j个数
}
}
}
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int a, b, c, d;
a = cin.nextInt();
b = cin.nextInt();
c = cin.nextInt();
d = cin.nextInt();
if (a > full[0] || b > full[1] || c > full[2] || d > full[3]
|| num[a][b][c][d] == inf) {
System.out.println("-1");
continue;
}
System.out.println(num[a][b][c][d]);
}
}
}
这次比赛没做好的同学也不要灰心，这套题应该是个决赛题，4个小时的时间，而且离着真正比赛还有一个月的时间，如果按照杭电分类，剩下这30天平均一天去oj切5道题，进决赛也并非难事。。。大家加油~~^o^~~- 1楼weiwei2012start3小时前
- 楼主 你好 请问 第二题：硬币方案 完全背包 第三个循环 怎么写成 for (k = 400; k >= coin[i]; k--)，求解答 ，谢谢
- Re: liuqiyao_012小时前
- 其实写成这个样也是可以的n[code=java]nttfor (i = 0; i < 4; i++) {ntttfor (j = 1; j <= 50; j++) {nttttfor (k = coin[i]; k <= 400; k++) {ntttttdp[j][k] += dp[j - 1][k - coin[i]];ntttt}nttt}ntt}n[/code]ndp[j][k] += dp[j - 1][k - coin[i]]; n意思就是 j个石头组成k块钱的方案数 = 他本身 + j-1个石头组成k-coin[i]块钱的方案数。。。