BIGSEQ - Sequence
You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partition the sequence into M chunks. Each chunk must be a consecutive subsequence of the original sequence. Let Si (1 ≤ i ≤ M) be the total number of 1's in all numbers in the ith chunk when written in binary, and let S be the maximum of all Si, i.e. the maximum number of 1's in any chunk. Your goal is to minimize S.
Input
In the first line of input, two numbers, K and M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100, M ≤ 2^K), are given, separated by a single space character.
Output
In one line of the output, write the minimum S that can be obtained by some split. Write it without leading zeros. The result is not guaranteed to fit in a 64-bit integer.
Example
Input:
3 4 Output:
4
【题意】
给定所有 K 位二进制数：0,1,…,2^K-1。你需要将它们分成恰好 M 组，每组都是原序列中连续的一些数。设 Si(1 ≤ i ≤ M)表示第 i 组中所有数的二进制表示中 1 的个数，S 等于所有 Si 中的最大值。你的任务是令 S 最小。 【分析】
这题竟然1A了超级感动。
人生第一道重载运算符的高精度。
主要就是高精度真是好恶心哦..看着别人的代码打的，重载运算符之后就直接用了很方便。
进入正题，最大值最小，我们就想到可以二分S，然后划分区间使得每个区间都小于S。
问题就变成了有限制S，然后把它划分成最少的区间，判断区间数是否<=m。
假设我们现在在st的位置，要找最远的ed使得st+1到ed中的数的1的个数<=S。
设c[i]表示小于等于i的数的1的个数和，上面的限制就是c[ed]-c[st]<=S -> c[ed]<=S+c[st]
所以变成找最大的ed使c[ed]<=S+c[st]。
c数组当然不能每个都求，我们用到他的时候就用数位DP求，具体过程就是模拟填数。
找最大的ed使c[ed]<=S+c[st]也是一个模拟填数的过程，也是一个数位DP。
数位DP中用到的数组是d[i],f[i]。
d[i]表示2^i，f[i]表示小于等于d[i]的数中的1的个数和。初始化求出这两个数组。
填数的时候注意1的个数计算。我一开始就傻逼了。
前面填过的1并没有在答案中减去，判断可不可以走左子树的时候要记得把这个也加上判断。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 110 struct bign
{
int len,a[Maxn];
bign ()
{
memset(a,,sizeof(a));
len=;
}
bign (int num)
{
*this = num;
}
bign operator = (const int num)
{
char s[Maxn];
sprintf(s,"%d",num);
*this = s;
return *this;
}
bign operator = (const char *num)
{
while(num[]=='') num++;
len=strlen(num);
for(int i=;i<len;i++)
a[i]=num[len-i-]-'';
return *this;
}
bign operator + (const bign &b)
{
bign c;
c.len=;
for(int i=,g=;g||i<max(len,b.len);i++)
{
int x=g;
if(i<len) x+=a[i];
if(i<b.len) x+=b.a[i];
c.a[c.len++]=x%;
g=x/;
}
return c;
}
bign operator += (const bign &b)
{
*this=*this+b;
return *this;
}
void clean()
{
while(len> && !a[len-]) len--;
}
bign operator * (const bign &b)
{
bign c;
c.len=len+b.len;
for(int i=;i<len;i++)
for(int j=;j<b.len;j++)
c.a[i+j]+=a[i]*b.a[j];
for(int i=;i<c.len;i++)
{
c.a[i+]+=c.a[i]/;
c.a[i]%=;
}
c.clean();
return c;
}
bign operator *= (const bign &b)
{
*this=*this * b;
return *this;
}
bign operator - (const bign b)
{
bign c;
c.len=;
for(int i=,g=;i<len;i++)
{
int x=a[i]-g;
if(i<b.len) x-=b.a[i];
if(x>=) g=;
else
{
g=;
x+=;
}
c.a[c.len++]=x;
}
c.clean();
return c;
}
bign operator -= (const bign &b)
{
*this = *this -b;
return *this;
}
bign operator / (const int b)
{
bign c;
int f=;
for(int i=len-;i>=;i--)
{
f=f*+a[i];
c.a[i]=f/b;
f=f%b;
}
c.len=len;
c.clean();
return c;
}
bign operator / (const bign &b)
{
bign c,f=;
for(int i=len-;i>=;i--)
{
f=f*;
f.a[]=a[i];
while(f>=b)
{
f-=b;
c.a[i]++;
}
}
c.len=len;
c.clean();
return c;
}
bign operator /= (const bign &b)
{
*this = * this /b;
return * this;
}
bign operator % (const bign &b)
{
bign r= *this /b;
r=*this-r*b;
return r;
}
bign operator %= (const bign &b)
{
*this=*this%b;
return *this;
}
bool operator < (const bign &b)
{
if(len!=b.len) return len<b.len;
for(int i=len-;i>=;i--)
if(a[i]!=b.a[i]) return a[i]<b.a[i];
return false;
}
bool operator > (const bign &b)
{
if(len!=b.len) return len>b.len;
for(int i=len-;i>=;i--)
if(a[i]!=b.a[i]) return a[i]>b.a[i];
return false;
}
bool operator == (const bign &b)
{
return !(*this>b) && !(*this<b);
}
bool operator != (const bign &b)
{
return !(*this==b);
}
bool operator <= (const bign &b)
{
return (*this<b)||(*this==b);
}
bool operator >= (const bign &b)
{
return (*this>b)||(*this==b);
}
}; void output(bign x)
{
for(int i=x.len-;i>=;i--) printf("%c",x.a[i]+'');
printf("\n");
} int k,m;
bign d[Maxn],f[Maxn];
void init()
{
d[]=;
for(int i=;i<=k;i++) d[i]=d[i-]*;
f[]=;
for(int i=;i<=k;i++) f[i]=f[i-]*+d[i-];
} bign get_ct(bign x)
{
bign ans=;
if(x==-) return ;
int y=;
for(int i=k;i>=;i--)
{
bign now=x/d[i-];
if(now==) ans+=f[i-]+d[i-]*y,y++;
x%=d[i-];
}
return ans+y;
} bign get_f(bign x)
{
bign ans=;
int y=;
for(int i=k;i>=;i--)
{
if(d[i-]*y+f[i-]<x) ans+=d[i-],x-=d[i-]*y+f[i-],y++;
}
if(x>=y) return ans;
return ans-;
} bool check(bign x)
{
bign st=;
int now=;
while(st<d[k]-)
{
bign y=get_ct(st),ed=get_f(y+x);
now++;
if(now>m) return ;
st=ed;
}
return ;
} void ffind()
{
bign l=,r=f[k];
while(l<r)
{
bign mid=(l+r)/;
if(check(mid)) r=mid;
else l=mid+;
}
output(l);
} int main()
{
scanf("%d%d",&k,&m);
init();
ffind();
return ;
}
[SPOJ 2319]
打这个真是太不容易了！！！！
放一个大神的题解，如果看不懂我说的东西的话：
