题目:
样例1:
样例2:
样例3:
思路:
根据题意,如果直接 for 循环暴力,肯定会超时,但是我们换个思路想,只要包含 4 和 7的数字,所以我们可以 DFS 暴搜小于 n 的就可以了。
代码详解如下:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
int n,ans;
string v = "47"; // 包含的数字
string tree = ""; // 选取的数字
inline void DFS()
{
// 递归边界,如果选取合并的数字大于了 n 退出递归
if(tree.size() && stoll(tree) > n) return ;
// 如果 有选取的数字了,并符合 < n 累加该结果
if(tree.size()) ++ans;
for(int i = 0;i < 2;++i)
{
// 先存储好当前的状态
string tem = tree;
// 选取字数
tree += v[i];
DFS();
// 恢复之前状态
tree = tem;
}
return ;
}
inline void solve()
{
cin >> n;
DFS();
cout << ans << endl;
}
int main()
{
// freopen("a.txt", "r", stdin);
___G;
int _t = 1;
// cin >> _t;
while (_t--)
{
solve();
}
return 0;
}
最后提交: