分裂的奶牛群（洛谷P2907题题解，Java语言描述）

题目要求

P2907题目链接

分析

奶牛群分流，假设牛群有n头牛，能分，二者差k头，则分别为:

• (num-limit)/2
• (num+limit)/2

分流条件：

• (num-limit)>0，因为有牛才能分裂。
• (num-limit)&1==0，即n-k是偶数，不是偶数没法除以2。

求解需要写递归的DFS程序。

由于我们要求的是最终几堆牛吃草，所以不能分裂（不满足前面提到的条件），就返回1。 在满足条件可以分裂的时候就需要return dfs((num-limit)/2) + dfs((num+limit)/2);，分别求两堆分开的牛最终能分成几堆。

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {

    private static long limit;

    private static long dfs(long num) {
        if (num > limit && ((num-limit)&1)==0) {
            return dfs((num-limit)/2) + dfs((num+limit)/2);
        }
        return 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long num = scanner.nextLong();
        limit = scanner.nextLong();
        scanner.close();
        System.out.println(dfs(num));
    }

}