第七届蓝桥杯省赛
1458487403
题目下载
不得不说，幸好练习了dfs，除了前面几道简单的填空题就不说了，后面从第六题开始一看题目说是要遍历的就用dfs搞，搞不出再说。
前面8道题目用不到1个小时就做出来并且验算完，差距就是最后两题。就像坐我隔离比赛的同学说会做的都做了，不会做的也做不出来。
写完跟我隔离比赛同学聊了1个多小时，好玩，说他今早5点就坐车来比赛，还跟我说困了要睡会待会叫我。
很侥幸的除了最后一题没算出其他的都搞掂了.
第六题
题目描述
凑算式
B DEF
A + — + ——- = 10
C GHI
（如果显示有问题，可以参见【图1.jpg】）
这个算式中AI代表09的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
解题思路
当时我想都没想直接dfs，结果真算出来了哈哈
代码实现
public class A6 {
static int[] vis = new int[10]; //标记数组
static int[] m = new int[10]; //
static int count = 0;
static void dfs(int n) {
if (n == 10) { //此时1-9已赋值完毕,并验证条件
int a = m[1];
double b = (double) m[2] / m[3];
double c = (double) (m[4] * 100 + m[5] * 10 + m[6])
/ (m[7] * 100 + m[8] * 10 + m[9]);
if (a + b + c == 10.0) {
count++;
for (int i = 1; i <= 9; i++)
System.out.print(m[i]);
System.out.println();
return;
}
}
for (int i = 1; i <= 9; i++)
if (vis[i] == 0) { //判断标记已有的位
vis[i] = 1; //标记i已经使用
m[n] = i; //赋值
dfs(n + 1);
vis[i] = 0; //取消标记
}
}
public static void main(String[] args) {
dfs(1);
System.out.println(count);
}}
运行结果
29
第七题
题目描述
搭积木
小明最近喜欢搭数字积木，
一共有10块积木，每个积木上有一个数字，0~9。
搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。
下面是两种合格的搭法：
0
1 2
3 4 5
6 7 8 9
0
3 1
7 5 2
9 8 6 4
请你计算这样的搭法一共有多少种？
请填表示总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
解题思路
与第六题一致，只是验证条件改一下，明摆的送分题
第八题
题目描述
冰雹数
任意给定一个正整数N，
如果是偶数，执行： N / 2
如果是奇数，执行： N * 3 + 1
生成的新的数字再执行同样的动作，循环往复。
通过观察发现，这个数字会一会儿上升到很高，
一会儿又降落下来。
就这样起起落落的，但最终必会落到“1”
这有点像小冰雹粒子在冰雹云中翻滚增长的样子。
比如N=9
9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1
可以看到，N=9的时候，这个“小冰雹”最高冲到了52这个高度。
输入格式：
一个正整数N（N<1000000）
输出格式：
一个正整数，表示不大于N的数字，经过冰雹数变换过程中，最高冲到了多少。
解题思路
竟然这题比前面两题还简单，不想说话
第九题
题目描述
四平方和
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多4个正整数的平方和。
如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法
程序输入为一个正整数N (N<5000000)
要求输出4个非负整数，按从小到大排序，中间用空格分开
例如，输入：
5
则程序应该输出：
0 0 1 2
再例如，输入：
12
则程序应该输出：
0 2 2 2
再例如，输入：
773535
则程序应该输出：
1 1 267 838
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
解题思路
思路不难，都是遍历，但是优化是一个难题，当时我没有想出来更好的优化方法，后边回去研究研究想起来以前做过的立方和优化的方法，哎呀，真行了。
代码实现
public class A9 {
static int[] mpt = new int[5000010];
static int n;
static void init() {
for (int i = 0; i * i <= n; i++)
for (int j = 0; j * j <= n; j++)
if (i * i + j * j <= n)
mpt[i * i + j * j] = 1;
}
public static void main(String[] args) {
boolean flag = false;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
init();
for (int i = 0; i * i <= n; i++) {
for (int j = 0; j * j <= n; j++) {
if (mpt[n - i * i - j * j] == 0)
continue;// 如果剩下的差用两个完全平方数不能组合出来就不继续
for (int k = 0; k * k <= n; k++) {
int temp = n - i * i - j * j - k * k;
double w = Math.sqrt(temp);
if (w == (int) w) {
System.out.printf("%d %d %d %d ", i, j, k, (int) w);
flag = true;
break;
}
}
if (flag)
break;
}
if (flag)
break;
}
scanner.close();
}}
第十题dfs搞不出来，难度相当。