本文主要是介绍Educational Codeforces Round 50 (Rated for Div. 2) C. Classy Numbers(dfs构造某类数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题意：找出区间[L, R]之间最多有三位是非零数字的十进制数的个数；
思路：用构造出所有的满足题意的数，然后排序，二分找；
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> vec;
void dfs(ll cur, int cnt, int len){vec.push_back(cur);if(len==18) return;dfs(cur*10, cnt, len+1);if(cnt<3){for(int i=1; i<=9; i++){dfs(cur*10+i, cnt+1, len+1);}}
}int main(){for(int i=1; i<=9; i++)dfs(i, 1, 1);vec.push_back(1e18);sort(vec.begin(), vec.end());int T;scanf("%d", &T);while(T--){ll L, R;scanf("%lld%lld", &L, &R);int l=lower_bound(vec.begin(), vec.end(), L)-vec.begin();int r=upper_bound(vec.begin(), vec.end(), R)-vec.begin();cout << r-l << endl;}return 0;
}
这篇关于Educational Codeforces Round 50 (Rated for Div. 2) C. Classy Numbers(dfs构造某类数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
