每天一题(5)-击鼓传花

偏执的太偏执、 2021-11-19 16:50 291阅读 0赞

# 题目 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NuZGF5WVU_size_16_color_FFFFFF_t_70]

# 代码 #

关键：两个人的情况、及利用对称性；

import java.util.Scanner;
    
    /**
     * 题目描述:https://exercise.acmcoder.com/online/online_judge_ques?ques_id=719&konwledgeId=134
     *
     * 学校联欢晚会的时候，为了使每一个同学都能参与进来，主持人常常会带着同学们玩击鼓传花的游戏。游戏规则是这样的：n个同学坐
     * 着围成一个圆圈，指定一个同学手里拿着一束花，主持人在旁边背对着大家开始击鼓，鼓声开始之后拿着花的同学开始传花，每个同
     * 学都可以把花传给自己左右的两个同学中的一个（左右任意），当主持人停止击鼓时，传花停止，此时，正拿着花没传出去的那个同学
     * 就要给大家表演一个节目。
     *  聪明的小赛提出一个有趣的问题：有多少种不同的方法可以使得从小赛手里开始传的花，传了m次以后，又回到小赛手里。
     *  对于传递的方法当且仅当这两种方法中，接到花的同学按接球顺序组成的序列是不同的，才视作两种传花的方法不同。
     *  比如有3个同学1号、2号、3号，并假设小赛为1号，花传了3次回到小赛手里的方式有1->2->3->1和1->3->2->1，共2种。
     *
     * @author ydfind
     * @date 2019.07.26
     */
    public class Main {
    
        /**
         * 计算某一个方向满足条件的次数，为-1时无法判断
         * @param distance 该方向下最少传递次数
         * @param last
         * @return
         */
        private static int calcDirectionCount(int last, int distance){
            int remain = last - distance;
            // 距离太远，或多余一次传递，均无法成功
            if(remain < 0 || (remain % 2 == 1)){
                return 0;
            }
            return remain == 0 ? 1 : -1;
        }
    
        /**
         * 符合条件下，有多少种传递情况
         * @param n 总人数
         * @param index 当前传递到的人（1-n）
         * @param last 还剩下的传递次数
         * @return 符合条件下，有多少种传递情况
         */
        private static int calcCount(int n, int index, int last){
            // 已经传到最后不需要再传了
            if(last == 0){
                return index == 1 ? 1 : 0;
            }
            // 利用对称性
            if(index == 1){
                return 2 * calcCount(n, index + 1, last -1);
            }
            // 看是否能直接判断出结果
            int leftCount = calcDirectionCount(last, index - 1);
            int rightCount = calcDirectionCount(last, n - index + 1);
            if(leftCount > -1 && rightCount > -1){
                return leftCount + rightCount;
            }
            // 继续向左边、向右传递
            leftCount = calcCount(n, index > 1 ? index - 1 : n, last - 1);
            rightCount = calcCount(n, index < n ? index + 1 : 1, last - 1);
            return leftCount + rightCount;
        }
    
    
        /**
         * 计算 从第一个人传递m次后回到第一个的情况数
         * @param n 总人数
         * @param m 传递次数
         * @return 从第一个人传递m次后回到第一个的情况数
         * @throws Exception
         */
        private static int calcCount(int n, int m) throws Exception {
            if(n < 1 || m < 0){
                throw new Exception("数据错误！");
            }
            if(m > 0 && n <= 1){
                throw new Exception("单节点无法传递！");
            }
            int count = -1;
            if(n == 2){
                // 2的情况比较特殊，向左向右都一样
                count = m % 2 == 1 ? 0 : 1;
            }else{
                count = calcCount(n, 1, m);
            }
            return count;
        }
    
        public static void main(String[] args) throws Exception {
            Scanner cin = new Scanner(System.in);
            while(cin.hasNextInt()) {
                int n = cin.nextInt();
                int m = cin.nextInt();
                int count = calcCount(n, m);
                System.out.println(count);
            }
        }
    }

# 优秀答案 #

import java.util.*;
    import java.io.*;
    
    public class Main2 {
    
        public static void main(String[]args){
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt(),m=sc.nextInt();
            int[][]dp=new int[m+1][n];
            dp[0][0]=1;
            for(int i=1;i<=m;i++){
                for(int j=0;j<n;j++){
                    dp[i][j]=dp[i-1][(j-1+n)%n]+dp[i-1][(j+1)%n];
                }
            }
            System.out.println(dp[m][0]);
        }
    
    //    public static void main(String[] args) {
    //        try {
    //            InputReader in;
    //            PrintWriter out;
    //            boolean useOutput = false;
    //            // if (System.getProperty("ONLINE_JUDGE") == null) useOutput = true;
    //            if (useOutput) {
    //                FileInputStream fin = new FileInputStream(new File("src/testdata.in"));
    //                in = new InputReader(fin);
    //                FileOutputStream fout = new FileOutputStream(new File("src/testData.out"));
    //                out = new PrintWriter(fout);
    //            } else {
    //                InputStream inputStream = System.in;
    //                in = new InputReader(inputStream);
    //                OutputStream outputStream = System.out;
    //                out = new PrintWriter(outputStream);
    //            }
    //            Solver solver = new Solver();
    //            solver.solve(in, out);
    //            out.close();
    //        } catch (Exception e) {
    //            e.printStackTrace();
    //        }
    //    }
    //
    //    static class Solver
    //    {
    //
    //        public void solve (InputReader cin, PrintWriter cout)
    //        {
    //            try {
    //                int n, m;
    //                n = cin.nextInt(); m = cin.nextInt();
    //                int dp[][] = new int[m + 1][n];
    //                // 第0次传递，到达第0位置的次数为2，即从0开始传递
    //                dp[0][0] = 1;
    //                // i: 第1、2、3...次传递
    //                for (int i = 1; i <= m; ++i) {
    //                    // j: 第i次传递，到达j的位置的次数
    //                    for (int j = 0; j < n; ++j) {
    //                        dp[i][j] = dp[i - 1][(j + 1) % n] + dp[i - 1][(j - 1 + n) % n];
    //                    }
    //                }
    //                cout.println(dp[m][0]);
    //            } catch (RuntimeException e) {
    //                return;
    //            } catch (Exception e) {
    //                e.printStackTrace();
    //                return;
    //            }
    //
    //        }
    //    }
    //
    //    static class InputReader {
    //        public BufferedReader reader;
    //        public StringTokenizer tokenizer;
    //
    //        public InputReader(InputStream stream) {
    //            reader = new BufferedReader(new InputStreamReader(stream));
    //            tokenizer = null;
    //        }
    //
    //        public String next() {
    //            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    //                try {
    //                    tokenizer = new StringTokenizer(reader.readLine());
    //                } catch (IOException e) {
    //                    throw new RuntimeException(e);
    //                }
    //            }
    //            return tokenizer.nextToken();
    //        }
    //
    //        public int nextInt() {
    //            return Integer.parseInt(next());
    //        }
    //
    //        public long nextLong () {
    //            return Long.parseLong(next());
    //        }
    //
    //        public double nextDouble () {
    //            return Double.parseDouble(next());
    //        }
    //
    //    }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NuZGF5WVU_size_16_color_FFFFFF_t_70]: /images/20211119/682432ff78124ae09d833b6fea07e5e6.png