第七题：扑克序列
题目描述
A A 2 2 3 3 4 4， 一共4对扑克牌。请你把它们排成一行。
要求：两个A中间有1张牌，两个2之间有2张牌，两个3之间有3张牌，两个4之间有4张牌。 请填写出所有符合要求的排列中，字典序最小的那个。
例如：22AA3344 比 A2A23344 字典序小。当然，它们都不是满足要求的答案。
请通过浏览器提交答案。“A”一定不要用小写字母a，也不要用“1”代替。字符间一定不要留空格。
解题思路
进行全排列，然后选出符合条件的排列
解题代码
package 蓝桥杯.Java14年B; import java.util.ArrayList; import java.util.HashSet; import java.util.Set; public class 扑克序列 { //要进行排列的数组 static char[] arr = { 'A', 'A', '2', '2', '3', '3', '4', '4' }; static boolean[] is = new boolean[8];//判断字符是否被使用 //存储排列 static ArrayList<Character> ans = new ArrayList<>(); //存储符合条件的结果 static Set<String> res = new HashSet<>(); public static void main(String[] args) { quanpailie();//递归全排列 for (String s : res ) { System.out.println(s); } } public static void quanpailie() { if ( ans.size()==8 ) {//全部的字符都排列 if ( check() ) { //判断是否符合条件 // System.out.println(ans.toString());、 String s = ""; for (char c : ans) { s += c; } res.add(s);//保存结果 return ; } } for ( int i=0; i<8; i++ ) { if ( !is[i] ) { //循环遍历，没有被使用的加入 ans.add(arr[i]); is[i] = true; quanpailie(); //递归 ans.remove(ans.size()-1); //回溯，回归状态 is[i] = false; } } } public static boolean check() { if ( ans.lastIndexOf('A')-ans.indexOf('A')==2 && ans.lastIndexOf('2')-ans.indexOf('2')==3 && ans.lastIndexOf('3')-ans.indexOf('3')==4 && ans.lastIndexOf('4')-ans.indexOf('4')==5) { return true;//符合要求返回true } return false; } }
第八题：分糖果
题目描述
有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：
每个小朋友都把自己的糖果分一半给左手边的孩子。
一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。
反复进行这个游戏，直到所有小朋友的糖果数都相同为止。
你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。
【格式要求】
程序首先读入一个整数N(2<N<100)，表示小朋友的人数。
接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2）
要求程序输出一个整数，表示老师需要补发的糖果数。
例如：输入
3
2 2 4
程序应该输出：
4
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
解题思路
模拟糖果交换的过程和补充糖果的过程直到每个小朋友的糖果相同
解题代码
package 蓝桥杯.Java14年B; import java.io.*; public class 分糖果 { static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); //读入Int public static int inInt() throws IOException { in.nextToken(); return (int) in.nval; } static int[] nums = null;//每个小朋友的糖果数 static int n = 0;//小朋友的个数 static int sum = 0;//补充的糖果 public static void main(String[] args) throws IOException { n = inInt(); nums = new int[n]; //读入 for ( int i=0; i<n; i++ ) { nums[i] = inInt(); } //模拟过程 //不相等就继续交换 while ( !isOK() ) { change(); } //输出 out.println(sum); out.flush(); } //模拟交换 public static void change() { int first = nums[0]; for ( int i=0; i<n; i++ ) { if ( i==n-1 ) { nums[i] = nums[i]/2+first/2; } else { nums[i] = nums[i]/2+nums[i+1]/2; } if ( nums[i]%2!=0 ) { nums[i]++; sum++; } } } //判断是否全部相等 public static boolean isOK() { int num = nums[0]; //因为所有的数要相等 //所以取出一个数和其他的数判断 //不相等直接返回 for( int i=1; i<n; i++ ) { if ( num!=nums[i] ) return false; } return true; } }
第九题：地宫取宝
题目描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角，出口在右下角。小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
【数据格式】
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
例如，输入：
2 2 2
1 2
2 1
程序应该输出：
2
再例如，输入：
2 3 2
1 2 3
2 1 5
程序应该输出：
14
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
解题思路
进行搜索模拟
要完全过，需要记忆化搜索
解题代码
此代码只能通过三个点（42分），不会记忆化搜索 蒟蒻
package 蓝桥杯.Java14年B; import java.io.*; public class 地宫取宝 { //加快读入 static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static int n = 0;//行 static int m = 0;//列 static int k = 0;//要拿的个数 static int max = -1;//拥有的物品的价值最大值 static int[][] arr = null;//所有物品的价值 static long sum = 0;//方案数 public static void main(String[] args) throws IOException { //读入数据 n = inInt(); m = inInt(); k = inInt(); arr = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i][j] = inInt(); } } //搜索 dfs(0, 0, 0); //输出 out.println(sum); out.flush(); } //搜索 dfs public static void dfs(int x, int y, int num) { //越界或拿的个数大于k都不满足条件 if (x == n || y == m || num > k) return;//越界 //走到最后一格 if (x == n - 1 && y == m - 1) { //走完时判断是否成立满足条件 if (num == k || (num == k - 1 && max < arr[x][y])) { sum++;//满足方案数++ return; } } //先记录当前的最大值 //递归回溯后需要恢复之前的状态 int t_max = max; //可以拿新物品时，可以拿也可以不拿 if (max < arr[x][y]) { //取新物品 max = arr[x][y]; //向右递归 dfs(x + 1, y, num + 1); //回溯后重置最大值 max = arr[x][y]; //向下递归 dfs(x, y + 1, num + 1); max = t_max;//回溯后重置最大值 //不取新物品 //向右递归 dfs(x + 1, y, num); max = t_max;//回溯后重置最大值 //向下递归 dfs(x, y + 1, num); max = t_max;//回溯后重置最大值 } else { //不能拿新物品 //向右递归 dfs(x + 1, y, num); max = t_max;//回溯后重置最大值 //向下递归 dfs(x, y + 1, num); } } //读入Int public static int inInt() throws IOException { in.nextToken(); return (int) in.nval; } }
第十题：矩阵翻硬币
题目描述
小明先把硬币摆成了一个 n 行 m 列的矩阵。随后，小明对每一个硬币分别进行一次 Q 操作。对第x行第y列的硬币进行 Q 操作的定义：将所有第 ix 行，第 jy 列的硬币进行翻转。 其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。 小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。
【数据格式】
输入数据包含一行，两个正整数 n m，含义见题目描述。
输出一个正整数，表示最开始有多少枚硬币是反面朝上的。
【样例输入】
2 3
【样例输出】
1
【数据规模】
对于10%的数据，n、m <= 10^3；
对于20%的数据，n、m <= 10^7；
对于40%的数据，n、m <= 10^15；
对于10%的数据，n、m <= 10^1000（10的1000次方）。
资源约定：
峰值内存消耗（含虚拟机） < 256 M
CPU消耗 < 1000 ms
解题代码暂无
