题目

题目大意

求区间\([A,B]\)有多少个数是“完美的”。

一个数是“完美的”，当且仅当这个数的各位能分成两个集合，使得两个集合中数字的和相等。

\(B\leq 10^9\)

思考历程

其实思考这题的时候已经没有什么时间了。

但我还是努力地去想正解。

看到的第一眼就会想到数位DP，然后脑中就弹出了一个DP状态。

很快就被自己证伪了，因为显然有重复。

想其它做法，却一直搞不出来。

看时间真的不多了，于是就去打暴力。

思想特别简单，枚举\([A,B]\)中的数，然后判断它们是否可行。

最容易想到的是背包，但是我认为背包会爆炸，于是我打了折半搜索。

然后又搞了各种优化……

最终成功水到了50分。

水法

大把人是打表过的，我真是醉了……

50分的\(10^7\)数据范围其实有另一种更简单的方法：还是背包，但由于背包的值为\(0\)或\(1\)，范围就在\([0,45]\)，就可以用一个long long将DP数组压起来，转移的时候直接位运算搞定……

YMQ说，数位DP一般都会开到\(10^{18}\)，这题只开到\(10^9\)，不是可以打表吗？

接下来介绍一下分段打表大法：

将\([1,10^6x]\)（其中\(1\leq x\leq 10^3\)）的答案全部跑出来。

这样，在询问中一大段的区间就不用处理了，只需要暴力处理剩下的\(10^6\)个数……

时间还快得很……

正解

这题用传统的数位DP似乎不太好做，尤其是判断重复，更加繁琐。

于是我们就试着换一个角度，逃避重复的问题。

可以枚举组成数字的各位数分别有哪些。如果这些数能组成“完美的数”，就进行排列，将范围之内的数统计如答案。

这样显然就不用怕重复了，因为如果是平常的做法，各位数可能有多种组成和相等的两个集合的方法。但是这样不需要管有多少中方法，只要它是成功的就对了。

有重复元素的排列有个公式：\(\frac{(\sum num_i)!}{\prod num_i!}\)

不会证……NOIP初赛的资料上的……

枚举出来的东西不会太多，具体是多少，其实我也没有统计……郑姐说是\(40000\)到\(80000\)。

判断它们是否可以组成“完美的数”就用上面说的那个二进制优化背包的方法。

然后统计答案的时候像正常的数位DP一样卡着它的上限，如果当前位选的数小于边界，后面的就可以随便选，用公式算就好了。

所以这题还算是个数位DP吧……这是数位DP的特征啊……

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

int pow10[10],fac[10];

int low,up,w;

int lim;

int num[10];

int ans;

inline bool ok(){

	unsigned long long f=1;

	int s=0;

	for (int i=0;i<=9;++i){

		for (int j=1;j<=num[i];++j)

			f|=f<<i;

		s+=i*num[i];

	}

	return ((s&1^1) && (f>>(s>>1)&1));

}

inline int calc(int m){

	int fm=1;

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

		fm*=fac[num[i]];

	return fac[m]/fm;

}

inline void dfs(int p){

	int th=lim/pow10[p]%10;

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

		if (num[i]){

			num[i]--;

			ans+=calc(p);

			num[i]++;

		}

	if (num[th] && p){

		num[th]--;

		dfs(p-1);

		num[th]++;

	}

}

void find(int k,int s){

	if (s==w){

		if (ok())

			dfs(w-1);

		return;

	}

	if (k>9)

		return;

	for (int i=0;i<=w-s;++i){

		num[k]=i;

		find(k+1,s+i);

	}

	num[k]=0;

}

int get_ans(int x){

	lim=++x;

	w=0;

	for (int tmp=lim;tmp;tmp/=10,++w);

	ans=0;

	find(0,0);

	return ans;

}

int main(){

	pow10[0]=1;

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

		pow10[i]=pow10[i-1]*10;

	fac[0]=1;

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

		fac[i]=fac[i-1]*i;

	scanf("%d%d",&low,&up);

	printf("%d\n",get_ans(up)-get_ans(low-1));

	return 0;

}

总结

在遇到会出现重复的问题是，可以试着换个角度，避免重复。

巴特西

[JZOJ3362] 【NOI2013模拟】数数

题目

题目大意

思考历程

水法

正解

代码

总结

最新文章

热门文章