AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 4726. Java dfs 2969ms    原题链接    中等

作者: 作者的头像   henrychenOutlook ,  2022-12-04 07:03:11 ,  所有人可见 ,  阅读 90


0


本题和codeforce 96B 一样 https://codeforces.com/problemset/problem/96/B
codeforce 提交结果 https://codeforces.com/problemset/submission/96/171187474

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

public class Main {
    static PrintWriter pw;

    void solve(int n) {
        TreeSet<Long> ts = buildSuperLuckyNumber();
        for (long x : ts) {
            if (x >= n) {
                pr(x);
                return;
            }
        }
    }

    TreeSet<Long> buildSuperLuckyNumber() {
        TreeSet<Long> res = new TreeSet<>();
        Deque<Character> cur = new ArrayDeque<>();
        dfs(cur, res);
        return res;
    }

    void dfs(Deque<Character> cur, TreeSet<Long> res) {
        if (cur.size() > 11) return; // max 7777744444
        for (char i = '0'; i <= '9'; i++) {
            cur.add(i);
            if (ok(cur)) {
                if (isEqual(cur)) res.add(appendNumber(cur));
                dfs(cur, res);
            }
            cur.pollLast();
        }
    }

    boolean ok(Deque<Character> q) {
        if (q.size() > 11) return false;
        for (char c : q) {
            if (c != '4' && c != '7') return false;
        }
        return true;
    }

    long appendNumber(Deque<Character> q) {
        String s = "";
        for (char c : q) s += c;
        return Long.parseLong(s);
    }

    boolean isEqual(Deque<Character> cur) {
        int four = 0, seven = 0;
        for (int x : cur) {
            if (x == '4') {
                four++;
            } else {
                seven++;
            }
        }
        return four == seven;
    }

    private void run() {
        // read_write_file(); // comment this before submission
        FastScanner fs = new FastScanner();
        int n = fs.nextInt();
        solve(n);
    }

    private final String INPUT = "input.txt";
    private final String OUTPUT = "output.txt";

    void read_write_file() {
        FileInputStream instream = null;
        PrintStream outstream = null;
        try {
            instream = new FileInputStream(INPUT);
            outstream = new PrintStream(new FileOutputStream(OUTPUT));
            System.setIn(instream);
            System.setOut(outstream);
        } catch (Exception e) {
        }
    }

    public static void main(String[] args) {
        pw = new PrintWriter(System.out);
        new Main().run();
        pw.close();
    }

    <T> void pr(T t) {
        pw.println(t);
    }

    class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }
    }

    void tr(Object... o) {
        pw.println(Arrays.deepToString(o));
    }
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息