可以进行网站外链建设的有,搜索率最高的关键词,怎样做电商入手,什么安装wordpress【蓝桥日记⑤】2014第五届省赛#xff08;软件类#xff09;JavaA组☃答案解析 文章目录【蓝桥日记⑤】2014第五届省赛#xff08;软件类#xff09;JavaA组☃答案解析1、猜年龄2、李白打酒3、神奇算式4、写日志5、锦标赛6、六角填数7、绳圈8、兰顿蚂蚁9、斐波那契10、波动…【蓝桥日记⑤】2014第五届省赛软件类JavaA组☃答案解析 文章目录【蓝桥日记⑤】2014第五届省赛软件类JavaA组☃答案解析1、猜年龄2、李白打酒3、神奇算式4、写日志5、锦标赛6、六角填数7、绳圈8、兰顿蚂蚁9、斐波那契10、波动数列1、猜年龄
解法暴力枚举
package fiveSession;/*** 2014第五届 1、猜年龄 ***/
public class test1 {public static void main(String[] args) {int age1 0, age2 0;boolean find false;for (int i 1; i 50; i) {for (int j i 1; j i 9; j) {if (i * j 6 * (i j)) {age1 i;age2 j;find true;break;}}if (find) break;}System.out.println(age1);}
}答案10 2、李白打酒
解法递归
package fiveSession;/*** 2014第五届 2、李白打酒 ***/
public class test2 {public static void main(String[] args) {int wine 2;int shop 5, flower 10;int res f(wine, shop, flower);System.out.println(res);}private static int f(int wine, int shop, int flower) {if (shop 0 || flower 0) return 0;if (wine 0 (shop ! 0 || flower ! 0)) return 0;if (wine 0 shop 0 flower 0) return 1;int res f(wine * 2, shop - 1, flower);res f(wine - 1, shop, flower - 1);return res;}
}递归二
package fiveSession;/*** 2014第五届 2、李白打酒 ***/
public class test2 {static int res 0;public static void main(String[] args) {int wine 2;int shop 5, flower 10 - 1;f(wine, shop, flower);System.out.println(res);}private static void f(int wine, int shop, int flower) {if (wine 1 shop 0 flower 0) {res;return;}if (shop 0) f(wine * 2, shop - 1, flower);if (flower 0) f(wine - 1, shop, flower - 1);}
}答案14 3、神奇算式
解法暴力枚举
package fiveSession;import java.util.Arrays;/*** 2014第五届 3、神奇算式 ***/
public class test3 {public static void main(String[] args) {int res 0;for (int i 1; i 10; i) {for (int j 0; j 10; j) {if (i j) continue;for (int k 0; k 10; k) {if (i k || j k) continue;for (int p 0; p 10; p) {if (i p || j p || k p) continue;int src i * 1000 j * 100 k * 10 p;if (j ! 0) {res check(src, i * (j * 100 k * 10 p));}if (k ! 0 (i * 10 j) (k * 10 p)) {res check(src, (i * 10 j) * (k * 10 p));}}}}}System.out.println(res);}public static int check(int src, int r2) {String s1 String.valueOf(src);String s2 String.valueOf(r2);char[] cs1 s1.toCharArray();char[] cs2 s2.toCharArray();Arrays.sort(cs1);Arrays.sort(cs2);if (new String(cs1).equals(new String(cs2))) return 1;return 0;}
}答案12 4、写日志
解法找规律
package fiveSession;/*** 2014第五届 4、写日志 ***/
public class test4 {private static int n 1;public static void write(String msg) {String filename t n .log;n (n % 3) 1;System.out.println(filename , msg);}public static void main(String[] args) {for (int i 0; i 15; i) write(a);}
}答案(n % 3) 1 5、锦标赛
package fiveSession;/*** 2014第五届 5、锦标赛 ***/
public class test5 {static void f(int[] a) {int n 1;while (n a.length) n * 2;int[] b new int[2 * n - 1];for (int i 0; i n; i) {if (i a.length)b[n - 1 i] i;elseb[n - 1 i] -1;}//从最后一个向前处理for (int i b.length - 1; i 0; i - 2) {if (b[i] 0) {if (b[i - 1] 0)b[(i - 1) / 2] b[i - 1];elseb[(i - 1) / 2] -1;} else {if (a[b[i]] a[b[i - 1]])b[(i - 1) / 2] b[i];elseb[(i - 1) / 2] b[i - 1];}}//输出树根System.out.println(b[0] : a[b[0]]);//值等于根元素的需要重新pkpk(a, b, 0, b[0]);//再次输出树根System.out.println(b[0] : a[b[0]]);}static void pk(int[] a, int[] b, int k, int v) {//if(kb.length) return;int k1 k * 2 1;int k2 k1 1;if (k1 b.length || k2 b.length) {// 此处将 叶子结点为最大值的 下标b[k]抹去置为-1 b[k] -1; //要是我我会该行代码设为考点~(^_^)~return;}if (b[k1] v)pk(a, b, k1, v);elsepk(a, b, k2, v);//重新比较if (b[k1] 0) {if (b[k2] 0)b[k] b[k2];elseb[k] -1;return;}if (b[k2] 0) {if (b[k1] 0)b[k] b[k1];elseb[k] -1;return;}if (a[b[k1]]a[b[k2]])b[k] b[k1];elseb[k] b[k2];}public static void main(String[] args) {int[] a {54, 55, 18, 16, 122, 255, 30, 9, 58, 66};f(a);}
}答案a[b[k1]]a[b[k2]] 6、六角填数
解法全排列剪枝
package fiveSession;/*** 2014第五届 6、六角填数 ***/
public class test6 {static int[] a {2, 4, 5, 6, 7, 9, 10, 11, 12};public static void main(String[] args) {backtrack(0, a.length);}private static void backtrack(int begin, int end) {if (begin 6 8 a[0] a[1] a[2] ! 1 a[0] a[3] a[5]) return;if (begin 7 8 a[0] a[1] a[2] ! 8 a[3] a[6] 3) return;if (begin end) {if (8 a[0] a[1] a[2] ! a[5] a[6] a[7] a[8]) return;if (8 a[0] a[1] a[2] ! a[2] a[4] a[7] 3) return;if (8 a[0] a[1] a[2] ! 1 a[1] a[4] a[8]) return;System.out.println(a[3]);}for (int i begin; i end; i) {int t a[begin]; a[begin] a[i]; a[i] t;backtrack(begin 1, end);t a[begin]; a[begin] a[i]; a[i] t;}}
}答案10 7、绳圈
解法动态规划
绳圈组合数自成一圈加入前一组合2个头i -1个分割点
令C[i]表示i个绳的组合数则有 C[i]c[i−1]C[i−1]∗(i−1)∗2C[i−1]∗(2i−1)C[i] c[i -1] C[i - 1] *(i - 1) * 2 C[i-1]*(2i-1) C[i]c[i−1]C[i−1]∗(i−1)∗2C[i−1]∗(2i−1) 令F[i][j]表示i个绳组j个圈的概率则有 F[i][j]F[i−1][j−1]∗C[i−1]F[i−1][j]∗C[i−1]∗(i−1)∗2C[i]F[i][j]\frac{F[i-1][j-1]*C[i-1]F[i-1][j]*C[i-1]*(i-1)*2}{C[i]} F[i][j]C[i]F[i−1][j−1]∗C[i−1]F[i−1][j]∗C[i−1]∗(i−1)∗2 联立两式约分有 F[i][j]F[i−1][j−1]F[i−1][j]∗(i−1)∗22i−1F[i][j]\frac{F[i-1][j-1]F[i-1][j]*(i-1)*2}{2i-1} F[i][j]2i−1F[i−1][j−1]F[i−1][j]∗(i−1)∗2
package fiveSession;/*** 2014第五届 7、绳圈 ***/
public class test7 {public static void main(String[] args) {double[][] f new double[101][101];f[1][1] 1;for (int rope 2; rope 100; rope) {f[rope][1] f[rope - 1][1] * (rope - 1) * 2 / (2 * rope - 1);for (int circle 2; circle rope; circle) {f[rope][circle] (f[rope - 1][circle - 1] f[rope - 1][circle] * (rope - 1) * 2) / (2 * rope - 1);}}int ans 0;double maxVal 0.0;for (int circle 1; circle 100; circle) {if (f[100][circle] maxVal) {maxVal f[100][circle];ans circle;}}System.out.println(ans);}
}答案3 8、兰顿蚂蚁
解法方向模拟
package fiveSession;import java.util.Scanner;/*** 2014第五届 8、兰顿蚂蚁 ***/
public class test8 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int m sc.nextInt();int n sc.nextInt();int[][] g new int[m][n];for (int i 0; i m; i) {for (int j 0; j n; j) {g[i][j] sc.nextInt();}}int x sc.nextInt();int y sc.nextInt();String s sc.next();int d getD(s);int k sc.nextInt();// 方向 上右下左int[][] dirs {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};for (int i 1; i k; i) {if (g[x][y] 0) {d (d 3) % 4;g[x][y] 1;} else {d (d 1) % 4;g[x][y] 0;}x x dirs[d][0];y y dirs[d][1];}System.out.println(x y);}private static int getD(String s) {if (s.equals(U)) return 0;if (s.equals(R)) return 1;if (s.equals(D)) return 2;return 3;}
}9、斐波那契
解法一暴力法(4/7)
package fiveSession;import java.util.Scanner;/*** 2014第五届 9、斐波那契暴力法1 ***/
public class test9 {public static void main(String[] args) {Scanner sc new Scanner(System.in);long n sc.nextLong();long m sc.nextLong();long p sc.nextLong();long sum 1;long t 0, f1 0, f2 1, mMod 0;for (long i 2; i n; i) {t f2 f1;f1 f2;f2 t;sum t;if (i m) mMod t;}if (m n) {for (long i n 1; i m; i) {t f2 f1;f1 f2;f2 t;}mMod f2;}System.out.println(sum % mMod % p);}
}解法二公式定理矩阵运算
我这个水平能暴力就暴力现在记公式定理性价比不高推理构造的到时可以深究一下。
有兴趣的可以看一下参考从蓝桥杯来谈Fibonacci数列 10、波动数列
解法一枚举首项dfs2/8 x xa x2a x3a ··· x(n-1)a s nx n(n-1)a/2 x x-b x-2b x-3b ··· x-(n-1)b s nx - n(n-1)b/2 通过上式可以求出首项x的范围 package fiveSession;import java.util.Scanner;/*** 2014第五届 10、波动数列 ***/
public class test10 {static int n, s, a, b;static long ans;static final int MOD (int)1e8 7;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();s sc.nextInt();a sc.nextInt();b sc.nextInt();sc.close();// x xa x2a x3a ··· x(n-1)a s nx n(n-1)a/2//x x-b x-2b x-3b ··· x-(n-1)b s nx - n(n-1)b/2int minX (s - (n - 1) * n * a / 2) / n;int maxX (s (n - 1) * n * b / 2) / n;for (int x minX; x maxX; x) {dfs(x, 1, x);}System.out.println(ans);}private static void dfs(int x, int cnt, int sum) {if (cnt n) {if (sum s) {ans;if (ans MOD) ans % MOD;}return;}dfs(x a, cnt 1, sum x a);dfs(x - b, cnt 1, sum x - b);}
}优化枚举a,b的数目dfs2/8
package fiveSession;import java.util.Scanner;/*** 2014第五届 10、波动数列, 优化枚举 ***/
public class test10_2 {static int n, s, a, b;static long ans;static final int MOD (int)1e8 7;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();s sc.nextInt();a sc.nextInt();b sc.nextInt();sc.close();// x xp x2p x3p ··· x(n-1)p s nx n(n-1)p/2// t n(n-1)/2// 若a的数目为ta, 则b数目为tbint t n * (n - 1) / 2;long minX (s - a * t) / n;long maxX (s b * t) / n;for (long x minX; x maxX; x) {for (long ta 0; ta t; ta) {// 减少对x的枚举long curSum x * n ta * a - (t - ta) * b;if (curSum s) dfs(x, 1, x);}}System.out.println(ans);}private static void dfs(long x, int cnt, long sum) {if (cnt n) {if (sum s) {ans;if (ans MOD) ans % MOD;}return;}dfs(x a, cnt 1, sum x a);dfs(x - b, cnt 1, sum x - b);}
}解法二动态规划求a和b的组合数7/10
package fiveSession;import java.util.Scanner;/*** 2014第五届 10、波动数列, 动态规划 ***/
public class test10_3{static int n, s, a, b;static long ans;static final int MOD (int)1e8 7;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();s sc.nextInt();a sc.nextInt();b sc.nextInt();sc.close();dpMethod();System.out.println(ans);}private static void dpMethod() {int t n * (n - 1) / 2;// dp[i][j]表示用前i个数组成值j的组合数方法int[][] dp new int[n][t 1];dp[0][0] 1;for (int i 0; i n; i) dp[i][0] 1;for (int i 1; i n; i) {for (int j 1; j t; j) {if (i j) {dp[i][j] dp[i - 1][j];} else {dp[i][j] dp[i - 1][j] dp[i - 1][j - i];}dp[i][j] % MOD;}}for (int ta 0; ta t; ta) {if ((s - ta * a (t - ta) * b) % n 0) {ans (ans dp[n - 1][ta]) % MOD;}}}
}优化动态规划滚动数组将状态压缩为二维7/10
package fiveSession;import java.util.Scanner;/*** 2014第五届 10、波动数列, 动态规划 ***/
public class test10_3{static int n, s, a, b;static long ans;static final int MOD (int)1e8 7;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();s sc.nextInt();a sc.nextInt();b sc.nextInt();sc.close();dpMethod2();System.out.println(ans);}private static void dpMethod2() {int t n * (n - 1) / 2;// dp[i][j]表示用前i个数组成值j的组合数方法int[][] dp new int[2][t 1];dp[0][0] dp[1][0] 1;int row 0;for (int i 1; i n; i) {row 1 - row;for (int j 1; j t; j) {if (i j) {dp[row][j] dp[1 - row][j];} else {dp[row][j] dp[1 - row][j] dp[1 - row][j - i];}dp[row][j] % MOD;}}for (long ta 0; ta t; ta) {if ((s - ta * a (t - ta) * b) % n 0) {ans (ans dp[row][(int)ta]) % MOD;}}}
}优化动态规划状态压缩为一维10/10
package fiveSession;import java.util.Scanner;/*** 2014第五届 10、波动数列, 动态规划 ***/
public class test10_3{static int n, s, a, b;static long ans;static final int MOD (int)1e8 7;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();s sc.nextInt();a sc.nextInt();b sc.nextInt();sc.close();dpMethod3();System.out.println(ans);}private static void dpMethod3() {int t n * (n - 1) / 2;// dp[i][j]表示用前i个数组成值j的组合数方法int[] dp new int[t 1];dp[0] 1;for (int i 1; i n; i) {// 减少j的枚举for (int j i * (i 1) / 2; j i; j--) {dp[j] (dp[j] dp[j - i]) % MOD;}}for (long ta 0; ta t; ta) {if ((s - ta * a (t - ta) * b) % n 0) {ans (ans dp[(int)ta]) % MOD;}}}}这道题目的两种方法的一步步优化真的惊艳到我了佩服佩服 参考资料【蓝桥杯JavaA组】2013-2018年试题讲解附含C语言版 总的来说排列组合和动态规划涉及的很多动态规划永远的伤啊~
