蓝桥杯 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所代表的数字。
注意不要填写多余的内容。
各个面的初始状态如下：
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分析：其实这道题可以通过对编号来进行找规律，从而更快更有效的来重置魔方，但是本弱菜太菜了。。只能通过手工画图，然后一一对比，找到转换魔方编号的方法。。。相当于纯暴力，代码比较容易读懂。。下图是我画的图。。每个格子表示颜色，白色用灰色代替了。。每四个小格子组成一个大格子，左上角写了他属于一开始的哪一个面，用直线画的是每一种转法。。。可能会有点乱，少有不慎就会有错误结果
代码：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) { // bfssta = 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个置为0judge(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个瓶子满了则continueint 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]块钱的方案数。。。