---

5147. 数量

原创 于 2023-09-09 21:07:38 发布 · 粉丝可见 · 263 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132781952

题目：

样例1：

cobol<br/>4<br/>

1

样例2：

cobol<br/>7<br/>

2

样例3：

cobol<br/>77<br/>

6

思路：

根据题意，如果直接 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;
}

最后提交：