【SPOJ】2319 BIGSEQ - Sequence

【算法】数位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[40],k,M;
bool calc(int s)
{int n=0,now=0,i,cpnow=0,tot=0;for(i=1;i<=M;i++){now=0;tot=0;n=0;for(int j=k-1;j>=0;j--){if(now+f[j]+tot*(1<<j)+1<=cpnow+s){now=now+f[j]+tot*(1<<j)+1;n|=(1<<j);tot++;}}printf("s=%d n=%d now=%d\n",s,n,now);if(n==(1<<k)-1)return 1;cpnow=now;}return 0;
}
int main()
{scanf("%d%d",&k,&M);f[0]=0;for(int i=1;i<=31;i++){f[i]=f[i-1]*2+(1<<(i-1));}int l=0,r=(1<<k)-1;while(l<r){int mid=(l+r)>>1;if(calc(mid))r=mid;else l=mid+1;}printf("%d",l);return 0;
}