侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS】寻找数字

GabrielxD
2022-12-18 / 0 评论 / 0 点赞 / 14 阅读 / 541 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-18,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4726. 寻找数字


给定一个正整数 nn ,请你找到一个正整数 xx ,要求:

  1. xnx \ge n
  2. xx 的各个数位均不包含 4477 以外的数字,且 xx 中包含的 44 的数量与 77 的数量恰好相等。
  3. 满足前两个条件的前提下, xx 应尽可能小。

输入格式

一个正整数 nn

输出格式

一个正整数,表示 xx

数据范围

66 个测试点满足 1n50001 \le n \le 5000
所有测试点满足 1n1091 \le n \le 10^9

输入样例1:

4500

输出样例1:

4747

输入样例2:

47

输出样例2:

47

解题

方法一:DFS

思路

输入数字为 n,设它的位数为 d

  • 如果 d 为偶数那么要找的数要么为 d 位要么为 d+2 位。
  • 如果 d 为奇数那么要找的数必为 d+1 位。

确定了要找的数的位数(d)就可以用 DFS 很方便地构造了:数中 47 的数量一定是 d/2 个,那么只需要先把数中所有位先填满 7 然后从高位往低位依次替换为 4 直到其数量达到 d/2 个即为一个符合要求的数,然后把该数与 n 进行比较,输出构造出的第一个满足条件的数。

代码

#include <iostream>
#include <unordered_set>

using namespace std;

typedef long long LL;

string n;
bool flag = false;
unordered_set<string> vis;

void dfs(string s, int x, int d) {
    if (flag) return;
    if (x == 1) {
        if (stol(s) >= stol(n)) {
            cout << s << "\n";
            flag = true;
        }
        return;
    }
    for (int i = 0; i < d; ++i) {
        if (s[i] == '7') {
            s[i] = '4';
            if (vis.find(s) == vis.end()) {
                dfs(s, x - 1, d);
                vis.insert(s);
            }
            s[i] = '7';
        }
    }
}

void build(int d) {
    string s(d, '7');
    int hf = d / 2;
    for (int i = 0; i < d; ++i) {
        if (flag) return;
        s[i] = '4';
        dfs(s, hf, d);
        s[i] = '7';
    }
}

int main() {
    getline(cin, n);
    int d = n.size();
    if (d & 1) ++d;
    build(d);
    if (!flag) build(d += 2);

    return 0;
}
0

评论区