【SPOJ】2319 BIGSEQ

【算法】数位DP

【题解】动态规划

题目要求的是大整数……没办法只写了小数字的，感觉应该没错。

大题框架是最大值最小化的二分问题。

对于每一块要求count(b)-count(a-1)≥s

已知a如何计算b？令now=count(a-1)+s，求的就是满足count(b)≥now的最小b了。

虽然看上去只是不等式的移项，但其实上是一种差分思想：将b-a≥s转化为b≥a+s，避免计算b和a的差。

然后每次求出b后，b+1就是新的起点，也就是count(b)=count(a`-1)，不需要重新计算。

那么如何计算count(i)?画画图就大概知道了：

预处理f[i]表示以高度i为根(不考虑自身)的1的数量，f[i]=f[i-1]*2+(1<<(i-1))。

每次从根到叶子判断若加上左子树权值(左子树包含的数字中所有1的数量)仍≤now就走右子树。

权值如何计算？ans=ans+f[j]+tot*(1<<j)+1，f[j]是假设上面的位是0考虑的，tot表示上面1的数量。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int f[],k,M;

bool calc(int s)

{

    int n=,now=,i,cpnow=,tot=;

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

     {

         now=;tot=;n=;

         for(int j=k-;j>=;j--)

          {

              if(now+f[j]+tot*(<<j)+<=cpnow+s)

               {

                   now=now+f[j]+tot*(<<j)+;

                   n|=(<<j);

                   tot++;

               }

          }

         printf("s=%d n=%d now=%d\n",s,n,now);

         if(n==(<<k)-)return ;

         cpnow=now;

     }

    return ;

}

int main()

{

    scanf("%d%d",&k,&M);

    f[]=;

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

     {

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

     }

    int l=,r=(<<k)-;

    while(l<r)

     {

         int mid=(l+r)>>;

         if(calc(mid))r=mid;

          else l=mid+;

     }

    printf("%d",l);

    return ;

}

巴特西

【SPOJ】2319 BIGSEQ - Sequence

最新文章

热门文章