교육 Codeforces Round 50 (Rated for Div. 2) C. 클래스 번호 (dfs + 2 점)
892 단어 【Codeforces】【 2 점 】[검색]
제목: 0 이 아 닌 3 개의 10 진수 의 개 수 를 구 하 는 구간 을 드 립 니 다.
사고: 조건 에 맞 는 모든 수 를 vector 에 넣 고 2 분 동안 상하 계 를 찾 습 니 다.
#include
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
vector v;
void dfs(ll x, int cnt, int len)
{
if (cnt == 4)
return;
if (len == 18)
{
v.push_back(x);
return;
}
for (int i = 0; i <= 9; ++i)
dfs(x * 10 + i, cnt + (i != 0), len + 1);
}
int main()
{
IOS; int t; ll l, r;
dfs(0, 0, 0);
v.push_back(1e18);
sort(v.begin(), v.end());
cin >> t;
while (t--)
{
cin >> l >> r;
cout << (upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l)) << endl;
}
return 0;
}