蓝桥杯2015国赛javaB组题目详解
第一题 积分之谜
题目描述：
小明开了个网上商店，卖风铃。共有3个品牌：A，B，C。
为了促销，每件商品都会返固定的积分。
小明开业第一天收到了三笔订单：
第一笔：3个A + 7个B + 1个C，共返积分：315
第二笔：4个A + 10个B + 1个C，共返积分：420
第三笔：A + B + C，共返积分...
你能算出第三笔订单需要返积分多少吗？解析：
3a+7b+c=315
4a+10b+c=420
可以解出
a+b+c=105第二题 完美正方形
题目描述：
如果一些边长互不相同的正方形，可以恰好拼出一个更大的正方形，
则称其为完美正方形。
历史上，人们花了很久才找到了若干完美正方形。
比如：如下边长的22个正方形
2 3 4 6 7 8 12 13 14 15 16 17 18 21 22 23 24 26
27 28 50 60
如下图img-1那样组合，就是一种解法。此时，
紧贴上边沿的是：60 50
紧贴下边沿的是：26 28 17 21 18
22阶完美正方形一共有8种。下面的组合是另一种：
2 5 9 11 16 17 19 21 22 24 26 30 31 33 35 36 41 46 47 50 52 61
如果告诉你该方案紧贴着上边沿的是从左到右依次为：47 46 61
你能计算出紧贴着下边沿的是哪几个正方形吗？解析：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class 蓝桥杯2015完美正方形 {
static class Node{
int x ;
int y ;
public Node(int x ,int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
int N=154;
int[][] graph = new int[N+1][N+1];
//正方形块数组
int[] number = {2,5,9,11,16,17,19,21,22,24,26,30,31,33,35,36,41,50,52};
//init
for(int i=1;i<=154;i++){
for(int j=1;j<=46;j++){
graph[j][i]=1;
}
}
for(int i=1;i<=47;i++){
graph[47][i]=1;
}
for(int i=47;i<=61;i++){
for(int j=94;j<=154;j++){
graph[i][j]=1;
}
}
//开始dfs
select(graph, number);
}
static Stack<Integer> stack = new Stack<>();
static List<String> path = new ArrayList<>();
public static void select(int[][] graph,int[] number){
if(stack.size()==number.length){
System.out.println(path.toString());
System.out.println(stack);
return;
}
for(int n=0;n<number.length;n++){
//先找到可以插入的点
Node myNode = find(graph);
if(myNode!=null){
if(!stack.contains(number[n])&& yvejie(graph, myNode.x, myNode.y, number[n])){
stack.push(number[n]);
//记录路径
path.add("("+myNode.x+","+myNode.y+")");
//graph填充
tianchong(myNode.x, myNode.y, graph, number[n]);
//寻找下一个
select(graph, number);
//无果出栈
stack.pop();
//清除之前错误的填充
qingchu(myNode.x, myNode.y, graph, number[n]);
//清除之前错误的路径
path.remove(path.size()-1);
}
}
}
return;
}
//找到可以插入的NODE
public static Node find(int[][] graph){
for(int i=1;i<graph.length;i++){
for(int j=1;j<graph.length;j++){
if(graph[j][i]==0){
return new Node(i, j);
}
}
}
return null;
}
//判断是否越界
public static Boolean yvejie(int[][] graph,int x,int y,int number) {
if(number>graph.length-x||number>graph.length-y){
return false;
}
for(int m=x;m<x+number;m++){
for(int n=y;n<y+number;n++){
if(graph[m][n]==1){
return false;
}
}
}
return true;
}
//对可行区域进行填充
public static void tianchong(int x,int y,int[][] graph,int number) {
for(int m=x;m<x+number;m++){
for(int n=y;n<y+number;n++){
graph[m][n]=1;
}
}
}
//对尝试过的不可行区域的填充进行一个撤销
public static void qingchu(int x,int y,int[][] graph,int number) {
for(int m=x;m<x+number;m++){
for(int n=y;n<y+number;n++){
graph[m][n]=0;
}
}
}
}
注释写的很清楚了
其实还可以优化一下，就是可以对正方形块进行一个排序
然后只要小的都越界大的就不用看了具体操作为：
对排序过后的number数组进行遍历
在判断是否越界的if的后面添加一个else
加入return就行了要想输出结果更加直观可以考虑path记录四个点的左边而不是一个
最后就很容易找到最下面的正方形第三题 密文搜索
题目描述
福尔摩斯从X星收到一份资料，全部是小写字母组成。
他的助手提供了另一份资料：许多长度为8的密码列表。
福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。
请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。
要考虑密码的所有排列可能性。输入格式
输入第一行：一个字符串s，全部由小写字母组成，长度小于1024*1024
紧接着一行是一个整数n,表示以下有n行密码，1<=n<=1000
紧接着是n行字符串，都是小写字母组成，长度都为8输出格式
一个整数, 表示每行密码的所有排列在s中匹配次数的总和。输入样例
aaaabbbbaabbcccc
2
aaaabbbb
abcabccc输出样例
4数据范围与提示
第一个密码匹配了3次，第二个密码匹配了1次，一共4次。思路步骤
- 对字符串s进行处理从头到尾每8位截取一段，每段按照ASSIC从小到大排序后保存
- 对每一个密码串按照ASSIC从小到大排序
- 遍历比较
代码实现
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
public class 蓝桥杯2015密文搜索 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int N = sc. nextInt();
String[] s = new String[N];
for(int i=0;i<N;i++){
char[] mymid = sc.next().toCharArray();
//转数组排序
Arrays.sort(mymid);
//转字符串保存
s[i] = String.valueOf(mymid);
}
sc.close();
HashMap<Integer,String> map = new HashMap<>();
StringBuilder sb = new StringBuilder(str);
int flag=0;
//字符串切割
while(true){
if(flag+7>str.length()-1){
break;
}
if(flag+7<=str.length()-1){
//substring包前不包后
String mysb = sb.substring(flag, flag+8);
char[] mych = mysb.toCharArray();
Arrays.sort(mych);
map.put(flag,String.valueOf(mych));
}
flag++;
}
int count=0;
for(String st:map.values()){
for(String mima:s){
//记得用equals
if(st.equals(mima)){
count++;
}
}
}
System.out.println(count);
}
}
