数学游戏

题目描述：

小T又发脑残了，没错，她又要求奇怪的东西，这次她想知道[X,Y]之间整数有多少可以表示成K个不同的B的幂的和形势。如\(x,y,k,b=15,20,2,2\)，则有：

\[17=2^4+2^0
\]

\[18=2^4+2^1
\]

\[20=2^4+2^2
\]

共3个符合要求的数

输入格式：

输入仅包含一行4个空格隔开的整数X，Y，K，B（1≤X≤Y≤2^31 -1,1≤K≤20）

输出格式：

输出文件包含一行一个即为所求合法数字个数。

样例输入：

15 20 2 2

样例输出：

题解

首先想到的是dfs大力枚举所有子集，这样就拿到了78分的好成绩。

void dfs(int kk,int t,int now)

{

	if(t==k)

	{

		if(now>=x&&now<=y) ans++;

		return;

	}

	if(kk>y) return;

	dfs(kk*b,t+1,now+kk);

	dfs(kk*b,t,now);

}

紫书中介绍了几种枚举子集的方法，所以我用了二进制枚举法，即类似状压一样，1代表选，0代表不选，那我们就可以直接用一个for循环枚举两者之间的所有数，这就枚举了所有子集。

这让我想到了NOIP2006普及T4 数列。

虽然没有剪枝，但似乎除T掉的点外其他都是0.00s过的。

这两个测试点的数据是这样的：

gema2.in:

1 2147483647 20 2

gema8.in:

4 2147483640 18 2

明显在卡子集生成。

代码如下：

#include <fstream>

using namespace std;

ifstream fin("maga.in");

ofstream fout("maga.out");

typedef long long LL;

LL x, y, k, b;

inline bool pan(LL a)//判断二进制下1是否有k个

{

	int ans = 0;

	while(a)

	{

		ans++;

		a = a & (a-1);

		if(ans > k)

			return false;

	}

	return ans == k;

}

inline LL getn(LL x)

{

	LL ans = 0;

	LL t = 1;

	while(x > t)

	{

		t *= b;

		ans++;

	}

	return 1 << ans;

}

inline bool ppan(LL x)//判断是否越界

{

	LL ans = 0;

	LL tk = 1;

	while(x)

	{

		if(x & 1)

			ans += tk;

		tk *= b;

		x >>= 1;

	}

	return ans <= y;

}

int main()

{

	fin >> x >> y >> k >> b;

	LL na = getn(x);

	LL ans = 0;

	for(LL i = na; ppan(i); ++i)

	{

		if(pan(i))

			ans++;

	}

	fout << ans << '\n';

	return 0;

}

其中pan函数比较玄学，看不懂的可以戳这里。

正解其实思想与二进制枚举是差不多的，但复杂度大不相同。

令dp[len][lim][gs]代表枚举到第len位，是否卡上限，其中一的个数有多少。

以len为主线进行大力转移即可。

下面贴一下代码。

#include <fstream>

using namespace std;

ifstream fin("maga.in");

ofstream fout("maga.out");

int x, y, k, b;

int dp[30][2][30];

int shu[10];//k进制下的每一位

inline int js(int len, bool lim, int gs)

{

	if(!lim && dp[len][lim][gs])

		return dp[len][lim][gs];

	if(gs > k)

		return 0;

	if(!len)//如果长度到了就直接判掉

	{

		if(gs == k)

			return dp[len][lim][gs] = 1;

		else

			return dp[len][lim][gs] = 0;

	}

	bool limit;

	if(lim && !shu[len])//如果到上界且该位为0，那该位不能选1

		limit = false;

	else

		limit = true;

	int ans = 0;

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

		ans += js(len-1, lim && i == shu[len], gs+(i==1));

	return dp[len][lim][gs] = ans;

}

inline int get_ans(int x)

{

	int tmp = 0;

	while(x)//先转化为k进制下的数

	{

		shu[++tmp] = x % b;

		x /= b;

	}

	return js(tmp, 1, 0);

}

signed main()

{

	fin >> x >> y >> k >> b;

	fout << get_ans(y) - get_ans(x-1);

	return 0;

}

当然，直接数位dp也是可以的。

inline int calc(int x){

	if(x<=0)return 0;

	memset(f,0,sizeof f);

	memset(num,0,sizeof num);

	size=0;

	while(x){

		num[++size]=x%b;

		x/=b;

	}

	if(num[size]>1){

		f[size][1][0]=1;

		f[size][0][0]=1;

	}else{

		f[size][0][0]=1;

		f[size][1][1]=1;

	}

	for(int i=size-1;i>=1;i--){

		if(num[i]>=1){

			for(int j=0;j<=min(k,size-i+1);j++){

				if(j)f[i][j][0]+=f[i+1][j-1][0];

				f[i][j][0]+=f[i+1][j][0];

				f[i][j][0]+=f[i+1][j][1];

				if(j){

					if(num[i]==1){

						f[i][j][1]+=f[i+1][j-1][1];

					}else{

						f[i][j][0]+=f[i+1][j-1][1];

					}

				}

			}

		}else{

			for(int j=0;j<=min(k,size-i+1);j++){

				f[i][j][0]+=f[i+1][j][0];

				if(j)f[i][j][0]+=f[i+1][j-1][0];

				f[i][j][1]+=f[i+1][j][1];

			}

		}

	}

	return f[1][k][0]+f[1][k][1];

}

巴特西

20180606模拟赛T4——数学游戏