解题思路:
很暴力的暴力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; } }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:629 |
字符串输入输出函数 (Java代码)浏览:1440 |
母牛的故事 (C语言代码)浏览:934 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:575 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:543 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:327 |
字符逆序 (C语言代码)浏览:617 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |
C语言程序设计教程(第三版)课后习题12.2 (C语言代码)浏览:767 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:568 |