题目

描述

题目大意

有从111到nnn的数字，每个数字都可以放在一个盒子里（可以不放）。一旦放，满足：

如果它不在第mmm个盒子，那么它的两倍一定在后面一个盒子里。

如果它不在第111个盒子，那么它的一半（整除，如果不能整除即为不合法）一定在前面的一个盒子里。

询问第一个盒子放的最多的数字个数。

思考历程

其实我当时思考的应该是正解，不过有点麻烦。

题目的重点自然在哪两个限制的条件上。首先，显然奇数必须放在第111个盒子里。

可以互相影响到的其实是2kx2^kx2kx的形式，其中xxx为奇数。

不妨将每个xxx的这个东西想象成一条链。

如果这条链被放入盒子中，第一项必定在第一个盒子里，然后第二项放第二个盒子里……第mmm项放在第三个盒子里。

当它的项数达不到mmm的时候，意味着这条链连不到最后一个盒子，由第一条限制得这样子不合法。

因此，必须要从头连到尾。

对于一个以xxx开头的链，设它的长度为lll，它可以先从头到尾连一遍，然后重新来再连一遍……所以说，它最多可以连⌊lm⌋\lfloor \frac{l}{m} \rfloor⌊ml⌋层。显然l=⌊log⁡2nx⌋+1l=\lfloor\log_2\frac{n}{x}\rfloor+1l=⌊log2xn⌋+1

所以暴力的思路就出来了，枚举奇数xxx，然后计算它对答案的贡献。

显然这样是很慢的，因为xxx的取值有很多。

可是log⁡2x\log_2xlog2x的取值并不是很多啊！

然后就是第二个思路，枚举yyy（也就是log⁡2x\log_2xlog2x），这里xxx的取值范围是⌊n2y+1⌋<x≤⌊n2y⌋\lfloor\frac{n}{2^{y+1}}\rfloor<x \leq \lfloor \frac{n}{2^y} \rfloor⌊2y+1n⌋<x≤⌊2yn⌋。

我们可以将这段区间内的奇数个数计算出来，计入贡献。

这样子显然要快多了。

再看看高精度的做法，如果是用以前的那种求出111分别到左右边界的奇数个数，然后相减的方法，那么花费的时间一定很多。

所以呢？我就开始分类讨论，讨论⌊n2y⌋\lfloor \frac{n}{2^y} \rfloor⌊2yn⌋和⌊n2y+1⌋\lfloor\frac{n}{2^{y+1}}\rfloor⌊2y+1n⌋的奇偶性，还有他们之间奇数个数和⌊n2y+2⌋\lfloor\frac{n}{2^{y+2}}\rfloor⌊2y+2n⌋之间的关系……

的确可以讨论出来，并且也是可以实现的，但是……很复杂啊……

最后我还是没有吧这种方法打上去。

正解

正解的方法要简单多了。

一条链中的数字都可以表示成2kx2^kx2kx的形式。

第一项时k=0k=0k=0，第mmm项时k=m−1k=m-1k=m−1。所以如果可以放一层，那么就要满足2m−1x≤n2^{m-1}x\leq n2m−1x≤n。

然后我们再从左到右，类似地继续来。

这时第一项时k=mk=mk=m，第mmm项时k=2m−1k=2m-1k=2m−1，那么就要满足22m−1x≤n2^{2m-1}x\leq n22m−1x≤n

因此可以这么做：

1、先将nnn变成⌊n2m−1⌋\lfloor\frac{n}{2^{m-1}}\rfloor⌊2m−1n⌋。

2、答案加上111到nnn之间奇数个数，也就是⌊n2⌋+nmod  2\lfloor\frac{n}{2}\rfloor+n \mod 2⌊2n⌋+nmod2。

3、n=⌊n2m⌋n=\lfloor\frac{n}{2^m}\rfloorn=⌊2mn⌋，然后回到第2步。

为什么第一次是m−1m-1m−1，第二次是mmm呢？不解释，手推一下就好。

这样做可以将一些能放多层的链的贡献累加起来，代码实现比较简单，时间也比较优秀。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cassert>

#define BIT 12

#define BITS 1000000000000ll

struct Bigint{

	long long v[2001];

};

Bigint n;

int m;

Bigint ans;

inline void read(Bigint &x){

	static char str[100001];

	scanf("%s",str);

	int len=strlen(str);

	memset(x.v,0,sizeof x.v);

	for (int i=len-1;i>=0;i-=BIT){

		x.v[0]++;

		long long w=1;

		for (int j=0;j<BIT && i-j>=0;++j,w*=10)

			x.v[x.v[0]]+=(str[i-j]-'0')*w;

	}

}

inline void write(Bigint &x){

	printf("%lld",x.v[x.v[0]]);

	for (int i=x.v[0]-1;i>=1;--i)

		printf("%012lld",x.v[i]);

	printf("\n");

}

inline void operator/=(Bigint &x,int y){

	long long mo=0;

	for (int i=x.v[0];i>=1;--i){

		x.v[i]=x.v[i]+mo*BITS;

		mo=x.v[i]%y;

		x.v[i]/=y;

	}

	while (x.v[0] && !x.v[x.v[0]])

		x.v[0]--;

	if (!x.v[0])

		x.v[0]=1;

}

inline void calc(){//计算ans

	ans.v[1]+=n.v[1]&1;

	n/=2;

	ans.v[0]=max(ans.v[0],n.v[0]);

	for (int i=1;i<=ans.v[0];++i){

		ans.v[i]+=n.v[i];

		ans.v[i+1]+=ans.v[i]/BITS;

		ans.v[i]%=BITS;

	}

	if (ans.v[ans.v[0]+1])

		ans.v[0]++;

}

int main(){

	int T;

	scanf("%d",&T);

	while (T--){

		read(n);

		scanf("%d",&m);

		memset(ans.v,0,sizeof ans.v);

		n/=1<<m-1;

		while (!(n.v[0]==1 && n.v[1]==0)){//n不为0时

			calc();

			n/=1<<m-1;//在calc()操作中，n=n/2

		}

		write(ans);

	}

	return 0;

}

总结

当自己想得很复杂的时候，应该考虑一下，这是否是恰当的解法……

巴特西

JZOJ[3771] 【NOI2015模拟8.15】小 Z 的烦恼

题目

描述

题目大意

思考历程

正解

代码

总结

最新文章

热门文章