Codeforces Round #150 (Div. 2) B dfs-白红宇

Codeforces Round #150 (Div. 2) B dfs

阅读量：5350 次

发布时间：2019-06-15

本文共 1578 字，大约阅读时间需要 5 分钟。

题意：

给一个数n (1 ≤ n ≤ 10⁹) ，然后求小于等于n的数，该数并且满足只有两个十进制数(0-9)组成的个数；

思路：

当时就是一门心思推公式，结果还是没找出规律。赛后想了想推个毛公式啊直接暴力枚举n的长度，然后枚举0到9两辆组合时间复杂度为O(10*10*10*2^10) = O(10^6)啊。

哎只怪自己没有想出来吧。这里还要注意当枚举长度为10时可能会出现超数据类型的要用__int64

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll __int64#define inf 0x7f7f7f7f#define MOD 1073741824#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 150#define N 1007using namespace std;//freopen("data.in","r",stdin);char num[15];int mk[15];int no;set
                
                 st;void dfs(int L,int a,int b,int pos){ if (pos == L + 1){ ll sum = 0; for (int i = 1; i <= L; ++i){ sum = sum*10; if (mk[i] == 1) sum += a; else sum += b; } if (sum <= no){ st.insert(sum); } return ; } mk[pos] = 1; dfs(L,a,b,pos + 1); mk[pos] = 0; dfs(L,a,b,pos + 1);}int main(){ //freopen("din.txt","r",stdin); int i,j,k; while (~scanf("%s",num)){ int len = strlen(num); no = 0; for (i = 0; i < len; ++i){ no = no*10 + (num[i] - '0'); } //cout<
                 
                  <<" " <
                  
                   <
                   
                    = 1 && no <= 99){ printf("%d\n",no); } else{ st.clear(); for (i = 2; i <= len; ++i){ for (j = 0; j <= 9; ++j){ for (k = 0; k <= 9; ++k){ CL(mk,0); dfs(i,j,k,1); } } } cout<