[hdu3943]K-th Nya Number

时间：2021-12-18 08:15:14

　　挺正常的一道模板题。

　　f[i][j][k]表示i位的数，有j个4，k个7的方案数。

　　具体实现的话...我写了发二分答案。。需要注意的是二分时应该是mid=L+(R-L)/2。。不然分分钟爆longlong（unsigned long long党自行退散

　　其实也可以从左端点开始慢慢爬。。。但总觉得比较蛋疼所以没敢写

　　由网上题解可得，其实还可以确定答案的位数后，从高位往低位一个一个试= =...复杂度会比二分答案的少个log

　　需要注意一下对0的特判。。

　　对于从左端点爬到根再爬到右端点的奇怪姿势一直不敢碰。。药丸的节奏啊= =。。GDOI应该不会出这么sxbk的东西吧（手动立flag？

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #define ll long long

 using namespace std;

 struct poi{

     ll k;int id;

 }q[];ll ans[];

 ll f[][][],ten[];bool u[][][];

 int i,j,x,y,X,Y,num;

 ll l,r,tmp;

 int s[],len;

 bool cmp(poi a,poi b){return a.k<b.k;}

 inline ll get(ll x){

     for(tmp=x,len=;tmp;tmp/=)s[++len]=tmp%;

     if(!x)s[len=]=;

     ll ans=;register int i,j;int sx=X,sy=Y;

     if(X+Y>len)return ;

     for(i=sx+sy;i<len;i++)

         for(j=;j<=;j++)

             if((sx||j!=)&&(sy||j!=))ans+=f[i-][sx-(j==)][sy-(j==)];

 //    printf("     %lld\n",ans);

     for(i=;i<s[len];i++)

         if((sx||i!=)&&(sy||i!=))ans+=f[len-][sx-(i==)][sy-(i==)];

     sx-=s[len]==,sy-=s[len]==;

     for(i=len-;i&&sx>=&&sy>=;i--){

         for(j=;j<s[i];j++)

             if((sx||j!=)&&(sy||j!=))ans+=f[i-][sx-(j==)][sy-(j==)];

         sx-=s[i]==,sy-=s[i]==;

     }

     if(!sx&&!sy&&x)ans++;

 //    printf("     %lld\n",ans);

     return ans+(!X&&!Y);

 }

 int main(){

     f[][][]=f[][][]=;f[][][]=;f[][][]=;

     for(i=ten[]=;i<=;i++)ten[i]=ten[i-]*;

     for(i=;i<=;i++){

         for(x=;x<=i;x++)for(y=i-x;y;y--)

             f[i][x][y]=x<=y?(f[i-][x][y]*+f[i-][x-][y]+f[i-][x][y-]):f[i][y][x]

         ;//    ,printf("  %d %d %d   %lld\n",i,x,y,f[i][x][y]);

         for(x=;x<=i;x++)f[i][x][]=f[i][][x]=f[i-][x-][]+f[i-][x][]*;

         f[i][][]=f[i-][][]<<;

     //    if(i<=3)

     //    for(x=0;x<=i;x++)for(y=0;y<=i-x;y++)printf("  %d %d %d  %lld\n",i,x,y,f[i][x][y]);

     }

     int T,TT;scanf("%d",&TT);

     for(T=;T<=TT;T++){

         scanf("%lld%lld%d%d",&l,&r,&X,&Y);scanf("%d",&num);

         for(i=;i<=num;i++)scanf("%lld",&q[i].k),q[i].id=i;

         sort(q+,q++num,cmp);

         ans[]=l;

         ll lnum=get(l),mx=get(r)-lnum;

     //    printf("    lnum:%lld   mx:%lld\n",lnum,mx);

         printf("Case #%d:\n",T);

         for(i=;i<=num;i++){

             ll L=ans[q[i-].id],R=r,mid;

             if(q[i].k==q[i-].k){ans[q[i].id]=L;continue;}

             if(q[i].k>mx){ans[q[i].id]=-;continue;}

             while(L<R){

                 mid=L+((R-L)>>);//printf("   %lld %lld  \n",L,R);

                 if(get(mid)>=q[i].k+lnum)R=mid;else L=mid+;

             }//puts("");

             ans[q[i].id]=L;

         }

         for(i=;i<=num;i++)

             if(ans[i]==-)puts("Nya!");else printf("%lld\n",ans[i]);

     }

     return ;

 }

　　话说网上有些题解遇到极限数据会炸>_<。。

相关文章