[Codeforces 1036C] Classy Numbers

[Codeforces 1036C] Classy Numbers - 1800

문제 설명 : 

1부터 10^18까지의 수 중에서 0이 아닌 서로 다른 digit이 3번 이하로 등장하는 수가 몇 개 인지 세는 문제이다.

풀이 : 

수의 범위가 최대 10^18이기 때문에 매 쿼리마다 개수를 세는 것은 무리라고 생각해서 어떻게든 전처리를 한 다음에 O(1)이나 O(logN)만에 구해야 한다고 생각했다. 그래서 전처리로 3개의 자리수로 만들 수 있는 수들을 digit 3개, 10의자리 3개로 6중 for문을 구성하여 모두 벡터에다가 집어넣었다. 이렇게해도 최대 10*10*10*18*18*18=583만개이다. 정렬 뒤 unique연산을 취해준다. 그런 다음 쿼리의 L~R값을 구하기 위해서 1~R의 개수에서 1~L의 개수를 빼준다. 개수는 바이너리 서치를 통해서 해당 값보다 작은 원소의 개수가 몇 개인지 센다. 여기서 R값은 upper bound로 L값은 lower bound로 세주면 된다.

주의할 점 : 

-

배울 점 : 

경우의 수 문제라서 처음에 당연히 dp문제라고는 생각은 했는데 전처리로 숫자들을 모두 구해놓는다는 생각은 못했다. 전처리를 할 때도 for문으로 돌리면서 벡터에다 모두 집어넣은 뒤 나중에 바이너리 서치로 개수를 센다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b; S(){}S(int _a,int _b){
        a=_a;
        b=_b;
    }
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
// const int SIZE=
 
vector<ll> v;
 
ll cnt(ll find){
 
    ll l=-1,r=v.size();
 
    while(l+1<r){
        ll mid=(l+r)/2;
 
        if(v[mid]>find)
            r=mid;
        else l=mid;
    }
    return l;
}
 
int main(){
    int t;    scanf("%d",&t);
 
    ll scale[20]={1LL,};
    for(int i=1 ; i<=18 ; i++){
        scale[i]=scale[i-1]*10;
    }
    v.push_back(scale[18]);
 
    for(int d1=0 ; d1<=9 ; d1++){
        for(int d2=0 ; d2<=9 ; d2++){
            for(int d3=0 ; d3<=9 ; d3++){
                for(int s1=0 ; s1<18 ; s1++){
                    for(int s2=s1+1 ; s2<18 ; s2++){
                        for(int s3=s2+1 ; s3<18 ; s3++){
                            ll res=d1*scale[s1]+d2*scale[s2]+d3*scale[s3];
                            v.push_back(res);
                        }
                    }
                }
            }
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
 
    while(t--){
        ll l,r;    scanf("%lld %lld",&l,&r);
        printf("%lld\n",cnt(r)-cnt(l-1));
    }
 
    
 
    return 0;
}