java蓝桥杯2017年A组
本文共 10217 字，大约阅读时间需要 34 分钟。
1、迷宫
X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：L表示走到左边的房间，R表示走到右边的房间，U表示走到上坡方向的房间，D表示走到下坡方向的房间。X星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！开始的时候，直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。迷宫地图如下：UDDLUULRULUURLLLRRRURRUURLDLRDRUDDDDUUUUURUDLLRRUUDURLRLDLRLULLURLLRDURDLULLRDDDUUDDUDUDLLULRDLUURRR请你计算一下，最后，有多少玩家会走出迷宫?而不是在里边兜圈子。请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。
深度优先搜索
public class MiGong { static int ok=0,res=0; static char road[][] = new char [][] { { 'U','D','D','L','U','U','L','R','U','L'}, { 'U','U','R','L','L','L','R','R','R','U'}, { 'R','R','U','U','R','L','D','L','R','D'}, { 'R','U','D','D','D','D','U','U','U','U'}, { 'U','R','U','D','L','L','R','R','U','U'}, { 'D','U','R','L','R','L','D','L','R','L'}, { 'U','L','L','U','R','L','L','R','D','U'}, { 'R','D','L','U','L','L','R','D','D','D'}, { 'U','U','D','D','U','D','U','D','L','L'}, { 'U','L','R','D','L','U','U','R','R','R'}}; static int[][] cover=new int[10][10]; public static void main(String[] args) { for(int i=0;i<10;i++) { for(int j=0;j<10;j++) { cover = new int[10][10]; ok=0; dfs(i,j); if(ok==1) { res++; } } } System.out.println(res); } private static void dfs(int i, int j) { if(i==-1 | i==10 | j== -1 | j==10) { ok=1; return ; } if(cover[i][j]==1) return; cover[i][j]=1; if(road[i][j]== 'U') { dfs(i-1,j); } if(road[i][j]=='D') { dfs(i-1,j); } if(road[i][j]=='L') { dfs(i+1,j); } if(road[i][j]=='L') { dfs(i,j-1); } if(road[i][j]=='R') { dfs(i,j+1); } }} 2 、九数算式
观察如下的算式： 9213 x 85674 = 789314562 左边的乘数和被乘数正好用到了1~9的所有数字，每个1次。 而乘积恰好也是用到了1~9的所有数字，并且每个1次。 请你借助计算机的强大计算能力，找出满足如上要求的9数算式一共有多少个？ 注意： 1. 总数目包含题目给出的那个示例。 2. 乘数和被乘数交换后作为同一方案来看待。
import java.util.HashSet;import java.util.Set;public class JiuShu { static int[] book=new int[11]; static int[] result=new int[10]; static int count=0; public static void main(String[] args) { dfs(0); System.out.println(count/2); } static void dfs(int deep) { if(deep==10) { String string=getString(); if(string.charAt(0)=='0'||string.charAt(9)=='0') { return; } String[] split=string.split("0"); int num1=Integer.valueOf(split[0]); int num2=Integer.valueOf(split[1]); if(check(num1*num2)) { System.out.println(num1+" X "+num2+"="+num1*num2); count++; } return; } for(int i=0;i<=9;i++) { if(book[i]==0) { book[i]=1; result[deep]=i; dfs(deep+1); book[i]=0; } } } static String getString() { StringBuilder stringBuilder=new StringBuilder(); for(int i=0;i set=new HashSet (); char[] charArray=String.valueOf(num).toCharArray(); for(int i=0;i 3、魔方状态
二阶魔方就是只有2层的魔方，只由8个小块组成。小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：前面：橙色右面：绿色上面：黄色左面：绿色下面：橙色后面：黄色请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。请提交表示状态数的整数，不要填写任何多余内容或说明文字。
结果：229878
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;public class MoFang { static char[][] start = { "oybbgb".toCharArray(), "oygbbb".toCharArray(), "bygbby".toCharArray(), "bybbgy".toCharArray(), "obbogb".toCharArray(), "obgobb".toCharArray(), "bbgoby".toCharArray(), "bbbogy".toCharArray()}; static char[][][] q = new char[2000000][8][6]; static Set all_state = new HashSet (); static int front, tail; static String to_string(char[][] a) { String ans = ""; for (int i = 0; i < 8; ++i) { ans += new String(a[i]); } return ans; } private static void swap(char[] a, int i, int j) { char t = a[i]; a[i] = a[j]; a[j] = t; } private static void swap(char[][] a, int i, int j) { char[] t = a[i]; a[i] = a[j]; a[j] = t; } //上层的块的旋转，面的相对位置调换 static void ucell(char[] a) { swap(a, 0, 2); swap(a, 2, 5); swap(a, 5, 4); } //上层顺时针旋转 static void u(char[][] s) { ucell(s[0]); ucell(s[1]); ucell(s[2]); ucell(s[3]); //块的相对位置调换 swap(s, 1, 0); swap(s, 2, 1); swap(s, 3, 2); } //右层旋转是面的位置变化 static void rcell(char[] a) { swap(a, 1, 0); swap(a, 0, 3); swap(a, 3, 5); } static void r(char[][] s) { //魔方右层顺时针转 rcell(s[1]); rcell(s[2]); rcell(s[6]); rcell(s[5]); // 块的位置变化 swap(s, 2, 1); swap(s, 5, 1); swap(s, 6, 5); } static void fcell(char[] a) { swap(a, 2, 1); swap(a, 1, 4); swap(a, 4, 3); } static void f(char[][] s) { //前面一层 顺时针转 fcell(s[0]); fcell(s[1]); fcell(s[4]); fcell(s[5]); swap(s, 1, 5); swap(s, 0, 1); swap(s, 4, 0); } static void uwhole(char[][] s) { //整个魔方从顶部看 顺时针转 用于判重 u(s);//上层旋转 //下层旋转 ucell(s[4]); ucell(s[5]); ucell(s[6]); ucell(s[7]); //完成自旋后，块的位置变动 swap(s, 5, 4); swap(s, 6, 5); swap(s, 7, 6); } static void fwhole(char[][] s) { //整个魔方从前面看 顺时针转 用于判重 f(s); fcell(s[2]); fcell(s[6]); fcell(s[7]); fcell(s[3]); swap(s, 2, 6); swap(s, 3, 2); swap(s, 7, 3); } static void rwhole(char[][] s) { //整个魔方从右边看 顺时针转 用于判重 r(s); rcell(s[0]); rcell(s[3]); rcell(s[4]); rcell(s[7]); swap(s, 3, 7); swap(s, 0, 3); swap(s, 4, 0); } static boolean try_insert(char[][] s) { char[][] k = new char[8][6]; memcpy(k, s); for (int i = 0; i < 4; i++) { fwhole(k); for (int j = 0; j < 4; j++) { uwhole(k); for (int q = 0; q < 4; q++) { rwhole(k); if (all_state.contains(to_string(k))) { return false; } } } } all_state.add(to_string(k)); return true; } private static void memcpy(char[][] k, char[][] s) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 6; j++) { k[i][j] = s[i][j]; } } } static void solve() { front = 0; tail = 1; all_state.add(to_string(start)); memcpy(q[front], start);//填充q[0]，相当于第一个状态入队列 while (front < tail) { /*将其所有变形，尝试加入set中*/ memcpy(q[tail], q[front]);//拷贝到tail u(q[tail]);//上层顺时针旋转 if (try_insert(q[tail])) { tail++;//扩展队列 } memcpy(q[tail], q[front]);//拷贝到tail r(q[tail]);//右层顺时针旋转 if (try_insert(q[tail])) { tail++;//扩展队列 } memcpy(q[tail], q[front]);//拷贝到tail f(q[tail]);//前顺时针旋转 if (try_insert(q[tail])) { tail++;//扩展队列 } front++;//弹出队首 } System.out.println(front); } public static void main(String[] args) { solve(); } } 4、方格分割
6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。如图：p1.png, p2.png, p3.png 就是可行的分割法。
试计算： 包括这3种分法在内，一共有多少种不同的分割方法。 注意：旋转对称的属于同一种分割法。 请提交该整数，不要填写任何多余的内容或说明文字。
509public class Fabgge { static int ans; static int[][] dire= { { -1,0}, { 1,0}, { 0,-1}, { 0,1} }; static int[][] vis=new int[7][7]; private static void dfs(int x,int y) { if(x==0 ||y==0||x==6||y==6) { ans++; return; } //当前的点标注为已访问 vis[x][y]=1; //对称点也标注为已访问 vis[6-x][6-y]=1; for(int k=0;k<4;++k) { int nx=x+dire[k][0]; int ny=y+dire[k][1]; if(nx<0||nx>6||ny<0||ny>6){ continue; } if(0==vis[nx][ny]) { dfs(nx,ny); } } vis[x][y]=0; vis[6-x][6-y]=0; } public static void main(String[] args) { dfs(3,3); System.out.print(ans/4); }} 5、字母组串
由 A,B,C 这3个字母就可以组成许多串。 比如：“A”,“AB”,“ABC”,“ABA”,“AACBB” … 现在，小明正在思考一个问题： 如果每个字母的个数有限定，能组成多少个已知长度的串呢？public class Zimu { private static int f(int a,int b,int c,int n) { if(a<0||b<0||c<0) return 0; if(n==0) return 1; return f(a-1,b,c,n-1)+f(a,b-1,c,n-1)+f(a,b,c-1,n-1); } public static void main(String[] args) { System.out.println(f(1,1,1,2)); System.out.println(f(1,2,3,3)); }} 5、最大公共子串
public class Zdg { static int f(String s1,String s2) { char[] c1=s1.toCharArray(); char[] c2=s2.toCharArray(); int[][] a=new int[c1.length+1][c2.length+1]; int max=0; for(int i=1;i max) max=a[i][j]; } } } return max; } public static void main(String[] args) { int n=f("abcdkkk","babcdefa"); System.out.println(n); }} 7、正则问题
考虑一种简单的正则表达式：
只由 x ( ) | 组成的正则表达式。 小明想求出这个正则表达式能接受的最长字符串的长度。例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。
例如，
输入： ((xx|xxx)x|(x|xx))xx程序应该输出：
6一开始题意也没理解，(xx|xxx)2个x和3和x或运算，得3个x，3个x加1个x，在后面的或(x|xx)，得4个x，再加上2个x，最终结果6
层层递归import java.util.Scanner;import static java.lang.Math.*;public class Zhengze { static String s; static int len; static int pos; static int f() { int maxLen=0; int tmp=0; while(pos 8、包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。输入———第一行包含一个整数N。(1 <= N <= 100)以下N行每行包含一个整数Ai。(1 <= Ai <= 100)输出———一个整数代表答案。如果凑不出的数目有无限多个，输出INF。例如，输入：245程序应该输出：6再例如，输入：246程序应该输出：INF
理解：
对于方程 ax + by = C，有定理如下： 1.若 a，b互质，则 x，y一定有解，且无穷多个 如果限制 x，y >= 0，那么使 ax + by = C 无解的 C 的个数有限，且存在 max{ C | C 导致方程无解} = a * b - a - b 2.若 a，b不互质，则不能保证有解 （C % gcd(a，b) = 0 时才有解） <==> 有无限多个 C 是方程无解 （公因数只有1的两个非零自然数，叫做互质数）放在本题就是
方程 a0x0 + a1x1 + … + anxn = C 有解，则 a0 ，a1…an 互质， 否则若不互质，则有无限多个 C 导致方程无解核心问题：有多少个 C 使方程无解 ==> 完全背包问题
C 就是背包承重上限import java.util.Scanner;public class Baozi { static int n, g; static int[] a = new int[101];//101中蒸笼 static boolean[] f = new boolean[10000];//f[i]表示能否凑出 i 个包子 static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); f[0] = true; for (int i = 1; i <= n; ++i) { a[i] = sc.nextInt(); if (i == 1) g = a[i];//初始化最大公约数 else g = gcd(a[i], g); //完全背包的递推 for (int j = 0; j + a[i] < 10000; ++j) { if (f[j]) f[j + a[i]] = true; } } sc.close(); if (g != 1) { //a0 ，a1…an 不互质 System.out.println("INF"); return; } //统计凑不出的个数 int ans = 0; for (int i = 0; i < 10000; ++i) { if (!f[i]) { ans++; } } System.out.println(ans); }} 转载地址：http://ogrwi.baihongyu.com/
你可能感兴趣的文章
XDR-枚举的试用
查看>>
XDR -string的试用
查看>>
XDR-定长数组的使用
查看>>
xdr-union的试用
查看>>
XDR-初探XDR对变长类型空间的管理。--log
查看>>
XDR-变长类型数组-空间管理-log
查看>>
使用CppSQLite3访问SQLite数据库
查看>>
VS2008下使用CppSQLite3访问xgs黑名单表(SQLite数据库)
查看>>
第一个boost程序---timer的使用
查看>>
使用boost asio库实现字节数可控的CS通信
查看>>
linux下串口编程
查看>>
boot asio 非阻塞同步编程---非阻塞的accept和receive。
查看>>
利用ADOX、ADO操纵MDB文件（ACCESS）
查看>>
使用ADO操作MDB,关注数据类型
查看>>
使用windows自带Zip命令压缩文件
查看>>
windows获得文件大小
查看>>
Host 'ETCV3' is blocked because of many connection errors; unblock with 'mysqladmin flush-hosts'
查看>>
mysql高版本兼容老版本的密码格式
查看>>
OCILIB在VS2008中的使用
查看>>
OCILIB VC2008 效率测试
查看>>