程序员经验分享-hwhale

【蓝桥日记⑤】2014第五届省赛（软件类）JavaA组❆答案解析

2023-05-16

【蓝桥日记⑤】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;
            else
                b[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];
                else
                    b[(i - 1) / 2] = -1;
            } else {
                if (a[b[i]] > a[b[i - 1]])
                    b[(i - 1) / 2] = b[i];
                else
                    b[(i - 1) / 2] = b[i - 1];
            }
        }

        //输出树根
        System.out.println(b[0] + ":" + a[b[0]]);

        //值等于根元素的需要重新pk
        pk(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(k>b.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);
        else
            pk(a, b, k2, v);

        //重新比较
        if (b[k1] < 0) {
            if (b[k2] >= 0)
                b[k] = b[k2];
            else
                b[k] = -1;
            return;
        }

        if (b[k2] < 0) {
            if (b[k1] >= 0)
                b[k] = b[k1];
            else
                b[k] = -1;
            return;
        }

        if (a[b[k1]]>a[b[k2]])
            b[k] = b[k1];
        else
            b[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 ) ∗ 2 = C [ i − 1 ] ∗ ( 2 i − 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)∗2=C[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 ) ∗ 2 C [ 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 ) ∗ 2 2 i − 1 F[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、波动数列

解法一：枚举首项+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

通过上式可以求出首项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 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
        int 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的数目+dfs（2/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 x+p x+2p x+3p ··· x+(n-1)p    s = nx + n(n-1)p/2
        // t = n(n-1)/2
        // 若a的数目为ta, 则b数目为tb
        int 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语言版）

总的来说排列组合和动态规划涉及的很多，动态规划永远的伤啊~

在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【蓝桥日记⑤】2014第五届省赛（软件类）JavaA组❆答案解析 的相关文章

  • Mybatis-Plus-Generator源码解读

    首先 xff0c 从AutoGenerator类的execute方法进入 生成代码 public void execute logger debug 34 61 61 61 61 61 61 61 61 61 61 61 61 61 61

  • Xfce+VNC+XRDP实现远程桌面连接的方法

    本文介绍在CentOS 7 3下安装Xfce 43 VNC 43 XRDP实现远程桌面连接的方法 xff0c 使用root用户进行操作 1 配置前准备 升级更新 xff08 可选 xff09 更新资源 xff0c 避免资源过旧出现问题 yu

  • 视频超分——02 VESPCN

    Real Time Video Super Resolution with Spatio Temporal Networks and Motion Compensation 参考资料 xff1a 论文内容 xff1a https blog

  • 002 在树莓派zero w上安装 VNC

    前言 有时直接在树莓派上工作并不方便 也许您想通过远程控制从另一台设备进行处理 VNC 是一个图形桌面共享系统 xff0c 允许您从另一台计算机或移动设备 xff08 运行 VNC 查看器 xff09 远程控制一台计算机 xff08 运行

  • SRFBN阅读笔记

    文章出自cvpr2019 全称 xff1a Feedback Network for Image Super ResolutionFB层的两个输入 xff08 规定F out 1是F in 0 xff09 先做concatenate xff

  • 升级cmake到3.6.2

    CMake 到 3 6 2 https cmake org download CentOS 7 span class token punctuation span root 64 thrift1 span class token punct

  • dpkg强制卸载

    dpkg的一个强制卸载的方法 安mysql的时候因为玄学国家防火墙 xff0c 安到一般被阻断了 xff0c 再卸的时候各种依赖不对 xff0c dpkg r P怎么都卸不掉 xff0c 提示有依赖卸载包的东西 xff0c 找到一个 for

  • Python打包(构建)、分发、安装 简要介绍

    1 为什么要打包分发 平时我们习惯了使用pip安装一些package xff0c 但是如果想自己写一些package供别人使用 xff0c 就需要打包分发 打包 xff08 构建 xff09 xff1a 将自己的源代码打包封装成packag

  • 树莓派3b安装nginx 2018.12.31

    sudo apt get update sudo apt get upgrade sudo apt get remove apache2 据说如果系统自带apache2的话 xff0c apache2会占用80端口 xff0c 导致影响ng

  • 双系统：解决ubuntu18.04系统开机黑屏的问题（ubuntu20.04，ubuntu16.04适用）

    安装ubuntu双系统 xff1a 点击第三个U盘安装方式 xff1a 安装ubuntu xff1a 会出现黑屏现象 xff1a 重启电脑 xff08 一般是长按开机键 xff09 xff0c 在下面这个界面按e xff0c 注意不是回车是

  • WSL 下 Ubuntu 20.04 中文显示设置

    环境 系统 xff1a Windows 10 Pro 64 子系统 xff1a Ubuntu 20 04 LTS 查看本地语言包 xff0c 安装语言包 locale a 查看现有语言包 span class token function

  • linux网络测试工具

    工具 iperf 网络性能测试工具 测试组播 xff1a iperf s u B lt 组播地址 gt i lt 结果显示间隔 gt iperf s u B 231 1 2 1 i 1 iperf c lt 组播地址 gt u T lt T

  • python检查一个变量的类型

    1 只想知道某个变量的数据类型 xff1a python中判断一个变量的数据类型可以用 type 变量名 函数 xff1a gt gt gt rectangle 61 200 50 gt gt gt type rectangle lt cl

  • Windows10中wsl2安装kali子系统加GUI

    环境 win10专业工作站 操作 确定后重启 配置先决条件 In Windows Powershell 管理员 Enable WindowsOptionalFeature Online FeatureName Microsoft Windo

  • vue项目中使用ramda库

    先安装ramda库 npm i ramda 在main js中引入 import as R from 39 ramda 39 Vue prototype R 61 R

  • Get请求体中转义字符及URI编码

    参考 xff1a 转义字符及URI编码 weixin 30678349的博客 CSDN博客 获取职级类型的列表 getRankTypeList var sql 61 96 select COMMENTS from user col comm

  • 使用jar命令替换jar|war包中指定文件

    一 jar命令用法 span class token operator span c 创建新的归档文件 span class token operator span t 列出归档目录和文件 span class token operator

  • Windows编程UTF-8,UTF-16,ASCII,宽字节,窄字节等编码问题汇总

    宽字节输出乱码问题 span class token macro property span class token directive hash span span class token expression Unicode 字符集 s

  • 前端基础--NPM包管理工具

    NPM包管理工具 关键字 xff1a NPM包资源管理器 pdf 提示 xff1a 经常使用的命令 xff0c 一些生产常见问题记录 文章目录 NPM包管理工具一 常用命令 一 常用命令 span class token number 1

  • java算法1——河内之塔

    河内之塔游戏规则 xff1a 有A B C三个石棒 xff0c A上有若干个从小到大依次排列的盘子 xff0c 盘子的数量为n xff0c 现在要求 xff0c 将A棒上的盘子依次移动到C棒上 xff0c 并且移动过程中要保证小盘在大盘之上

随机推荐

热门标签