【藍(lán)橋日記⑤】2014第五屆省賽（軟件類）JavaA組?答案解析

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、寫日志

解法：找規(guī)律

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、錦標(biāo)賽

package fiveSession;/*** 2014第五屆  5、錦標(biāo)賽 ***/
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;}//從最后一個(gè)向前處理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];}}//輸出樹(shù)根System.out.println(b[0] + ":" + a[b[0]]);//值等于根元素的需要重新pkpk(a, b, 0, b[0]);//再次輸出樹(shù)根System.out.println(b[0] + ":" + a[b[0]]);}static void pk(int[] a, int[] b, int k, int v) {//if(k>b.length) return;int k1 = k * 2 + 1;int k2 = k1 + 1;if (k1 >= b.length || k2 >= b.length) {// 此處將 葉子結(jié)點(diǎn)為最大值的 下標(biāo)b[k]抹去，置為-1 b[k] = -1; //（要是我我會(huì)該行代碼設(shè)為考點(diǎn)~(@^_^@)~）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、六角填數(shù)

解法：全排列+剪枝

package fiveSession;/*** 2014第五屆  6、六角填數(shù) ***/
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、繩圈

解法：動(dòng)態(tài)規(guī)劃

繩圈組合數(shù)：自成一圈+加入前一組合（2個(gè)頭+i -1個(gè)分割點(diǎn)）

令C[i]表示i個(gè)繩的組合數(shù)，則有
$$C[i]=c[i?1]+C[i?1]?(i?1)?2=C[i?1]?(2i?1)$$
令F[i][j]表示i個(gè)繩組j個(gè)圈的概率，則有
$$F[i][j]=\frac{F[i?1][j?1]?C[i?1]+F[i?1][j]?C[i?1]?(i?1)?2}{C[i]}$$
聯(lián)立兩式約分有
$$F[i][j]=\frac{F[i?1][j?1]+F[i?1][j]?(i?1)?2}{2i?1}$$

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);}
}

解法二：公式定理+矩陣運(yùn)算

我這個(gè)水平，能暴力就暴力，現(xiàn)在記公式定理性價(jià)比不高，推理構(gòu)造的到時(shí)可以深究一下。

有興趣的可以看一下參考：從藍(lán)橋杯來(lái)談Fibonacci數(shù)列

---

10、波動(dòng)數(shù)列

解法一：枚舉首項(xiàng)+dfs（2/8）

x x+a x+2a x+3a ··· 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

通過(guò)上式可以求出首項(xiàng)x的范圍

package fiveSession;import java.util.Scanner;/*** 2014第五屆  10、波動(dòng)數(shù)列 ***/
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 x+a x+2a x+3a ··· 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);}
}

優(yōu)化：枚舉a,b的數(shù)目+dfs（2/8）

package fiveSession;import java.util.Scanner;/*** 2014第五屆  10、波動(dòng)數(shù)列, 優(yōu)化枚舉 ***/
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 x+p x+2p x+3p ··· x+(n-1)p    s = nx + n(n-1)p/2// t = n(n-1)/2// 若a的數(shù)目為ta, 則b數(shù)目為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++) {// 減少對(duì)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);}
}

解法二：動(dòng)態(tài)規(guī)劃，求a和b的組合數(shù)（7/10）

package fiveSession;import java.util.Scanner;/*** 2014第五屆  10、波動(dòng)數(shù)列, 動(dòng)態(tài)規(guī)劃 ***/
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個(gè)數(shù)組成值j的組合數(shù)方法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;}}}
}

優(yōu)化：動(dòng)態(tài)規(guī)劃+滾動(dòng)數(shù)組將狀態(tài)壓縮為二維（7/10）

package fiveSession;import java.util.Scanner;/*** 2014第五屆  10、波動(dòng)數(shù)列, 動(dòng)態(tài)規(guī)劃 ***/
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個(gè)數(shù)組成值j的組合數(shù)方法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;}}}
}

優(yōu)化：動(dòng)態(tài)規(guī)劃+狀態(tài)壓縮為一維（10/10）

package fiveSession;import java.util.Scanner;/*** 2014第五屆  10、波動(dòng)數(shù)列, 動(dòng)態(tài)規(guī)劃 ***/
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個(gè)數(shù)組成值j的組合數(shù)方法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;}}}}

這道題目的兩種方法的一步步優(yōu)化真的驚艷到我了！佩服佩服！

---

參考資料：【藍(lán)橋杯JavaA組】2013-2018年試題講解（附含C語(yǔ)言版）

總的來(lái)說(shuō)排列組合和動(dòng)態(tài)規(guī)劃涉及的很多，動(dòng)態(tài)規(guī)劃永遠(yuǎn)的傷啊~