1440: 蓝桥杯2013年第四届真题-带分数 dfs（JAVA题解）

解题思路:
很暴力的暴力dfs，但要注意的是此题不要直接用字符串，否则会TLE，使用对10取余、叠乘，亦可达到效果（详见代码），且运行速度会大大提升。
注意事项:

参考代码:

import java.io.*;
import java.util.*;

public class Main {
    static StreamTokenizer cin;
    static PrintWriter out;
    static int N;
    static int k = 9;
    static int maxN = (int)1E6;
    static int count = 0;
    static LinkedList<Integer> arr = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        N = nextInt();
        for(int i = 1; i <= k; i++)
            arr.add(i);
        dfs(arr, new LinkedList<>());
        out.println(count);
        out.flush();
        out.close();
    }


    static void dfs(LinkedList<Integer> list, LinkedList<Integer> his){
        if(his.size() == k){
            /**枚举带分数情况**/
            int zheng = 0;
            for(int j = 0; j < his.size(); j++){
                zheng = zheng*10 + his.get(j);
                if(zheng > N)  // 剪枝
                    break;
                int rest = N - zheng;  // 分数需要达到的数值
                int split = j+(his.size()-j)/2;  // 初始间隔位置
                int fz = 0;  // 分子
                int fm = 0;  // 分母
                // 初始化分子分母
                for(int z = j+1; z < split+1; z++)
                    fz = fz*10 + his.get(z);
                for(int z = split+1;z < his.size(); z++)
                    fm = fm*10 + his.get(z);
                if(zheng == 3 && fz == 6952  && fm == 8714)
                    out.print("");
                for(int z = split+1; z < his.size(); z++){  // 枚举分母位置split2, 可剪枝, 分子一定比分母大
                    if(fz%fm == 0  && fz/fm== rest){
                        count++;
                        break;
                    }
                    if(z == his.size()-1)
                        break;
                    fz = fz*10 + his.get(z);
                    fm = fm%((int)Math.pow(10, his.size() - z - 1));

                }
            }
            return;
        }
        for(int i = 0; i < list.size(); i++){
            int num = list.remove(i);
            his.add(num);
            dfs(list, his);
            // 回溯
            his.removeLast();
            list.add(i, num);
        }

    }

    static int nextInt() throws IOException{
        cin.nextToken();
        return (int)cin.nval;
    }
}