【HDOJ6659】Acesrc and Good Numbers（dfs）

题意：定义f(n,d)为数码d在1到n中出现的次数，其中d=0..9
如果f(d,k)=k，则称k是d好数
给定x和d，求不大于x的最大的d好数
x<=1e18
思路：考虑f的增长率主要和位数有关
各种位数，上限，下限剪枝……
事实上所有d好数不会超过1e11
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 typedef unsigned int uint;
  5 typedef unsigned long long ull;
  6 typedef pair<int,int> PII;
  7 typedef pair<ll,ll> Pll;
  8 typedef vector<int> VI;
  9 typedef vector<PII> VII;
 10 #define N  210000
 11 #define M  4100000
 12 #define fi first
 13 #define se second
 14 #define MP make_pair
 15 #define pi acos(-1)
 16 #define mem(a,b) memset(a,b,sizeof(a))
 17 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
 18 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
 19 #define lowbit(x) x&(-x)
 20 #define Rand (rand()*(1<<16)+rand())
 21 #define id(x) ((x)<=B?(x):m-n/(x)+1)
 22 #define ls p<<1
 23 #define rs p<<1|1
 24 
 25 const ll MOD=1e9+7,inv2=(MOD+1)/2;
 26       double eps=1e-6;
 27       ll INF=1e18;
 28       int dx[4]={-1,1,0,0};
 29       int dy[4]={0,0,-1,1};
 30 
 31 ll a[N],b[N],ans,n,k,mi[N];
 32 int len;
 33 
 34 ll read()
 35 {
 36    ll v=0,f=1;
 37    char c=getchar();
 38    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
 39    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
 40    return v*f;
 41 }
 42 
 43 ll calc(ll n)
 44 {
 45     if(n<0) return 0;
 46     int len=0;
 47     while(n)
 48     {
 49         b[++len]=n%10;
 50         n/=10;
 51     }
 52     ll t=0,re=0;
 53     per(i,len,1)
 54     {
 55         rep(j,0,b[i]-1)
 56         {
 57             if(i>=2) re+=mi[i-2]*(i-1);
 58             if(j==k) re+=mi[i-1];
 59             re+=mi[i-1]*t;
 60         }
 61         if(b[i]==k) t++;
 62     }
 63     return re+t;
 64 }
 65 
 66 void dfs(int u,ll now,ll now_,int flag,int s)
 67 {
 68     if(u==0)
 69     {
 70         if(calc(now)==now)
 71         {
 72             ans=now;
 73             return;
 74         }
 75     }
 76     if(s>=1)
 77     {
 78         if(calc(now)-now<=0&&calc(now_)-now_>=0)
 79         {
 80             ll l=now,r=now_,last=now;
 81             while(l<=r)
 82             {
 83                 ll mid=(l+r)>>1;
 84                 if(calc(mid)-mid<=0){last=mid; l=mid+1;}
 85                  else r=mid-1;
 86             }
 87             if(calc(last)-last==0) ans=max(ans,last);
 88         }
 89         return;
 90     }
 91     ll x=calc(now)-now,y=calc(now_)-calc(now),z=now-now_;
 92     if(x<0&&x+y<0) return;
 93     if(x>0&&x+z>0) return;
 94     if(flag)
 95     {
 96         per(i,9,0)
 97         {
 98             dfs(u-1,now+mi[u-1]*i,now+mi[u-1]*(i+1)-1,1,s+(i==k));
 99             if(ans!=-INF) return;
100         }
101     }
102      else
103      {
104          dfs(u-1,now+mi[u-1]*a[u],now_,0,s+(a[u]==k));
105          if(ans!=-INF) return;
106          per(i,a[u]-1,0)
107          {
108              dfs(u-1,now+mi[u-1]*i,now+mi[u-1]*(i+1)-1,1,s+(i==k));
109              if(ans!=-INF) return;
110          }
111      }
112 
113 }
114 
115 int main()
116 {
117     //freopen("1.in","r",stdin);
118     //freopen("1.out","w",stdout);
119 
120     int cas;
121     scanf("%d",&cas);
122     mi[0]=1;
123     rep(i,1,30) mi[i]=mi[i-1]*10;
124     while(cas--)
125     {
126         k=read(),n=read();
127         ll n_=n;
128         if(n==0)
129         {
130             printf("0
");
131             continue;
132         }
133         len=0;
134         while(n)
135         {
136             a[++len]=n%10;
137             n/=10;
138         }
139         ans=-INF;
140         n=n_;
141         dfs(len,0,n,0,0);
142         printf("%I64d
",ans);
143 
144 
145     }
146 
147     return 0;
148 }