51nod1306 高楼和棋子

Vexoben

Apr 11, 2019

It takes 5 minutes to read this article.

（刷新以获取数学公式）

题意

有个 $N$ 层的高楼和若干个棋子，所有的棋子都是一样的。棋子从楼的某层 $E$ 扔到地上不会碎 $(0 <= E <= N)$ ，但从比这个楼层高的地方扔到地上都会碎。给出楼的高度 $N$ ，以及棋子的数量 $M$ ，你来找出这个 $E(0 <= E <= N)$ ，问最坏情况下需要实验多少次才能计算出准确的E（如果棋子摔碎了，就不能继续用这个棋子进行测试了）。

数据范围： $T≤50000$ 组数据， $1≤N≤1e18,1≤M≤64$

题解

设 $f_{i,j}$ 为 $i$ 层楼高，还剩 $j$ 颗棋子的最小步数，那么有

$f_{i,j} = \min_k \{ \max\{ f_{i-k,j , \; f_{k-1,j-1}} \} \}$

容易发现， $j$ 相同时，对于很长的一段 $i$ 函数值可能是相同的。

令 $g_{i,j}$ 表示 $i$ 颗棋子 $j$ 次实验可以保证测出的最高楼高。

对 $g$ 打个表：

$1 \quad 2 \quad 3 \quad 4 \quad 5 \quad 6\quad 7 \\ \;\;1\quad 3 \quad 6\quad 10\; \;15\;\; 21\;\; 28 \\ \;\;1\quad 3 \quad 7\quad 14\; \;25\;\; 41\;\; 63 \\ \;\; 1\quad 3 \quad 7\quad 15\; \;30\;\; 56\;\; 98 \\ \;\;\; \;1\quad 3 \quad 7\quad 15\; \;31\;\; 62\;\; 119$

可以发现 $g_{i,j} = g_{i-1,j-1} + g_{i,j-1} + 1$ ，从而可以推断出 $g_i$ 是一个关于 $j$ 的 $m$ 次多项式。

把 $m=1,2,3$ 的时候手工解出来， $m>4$ 的时候只需要不多的项 $g_{m,j}$ 就会到 $1e18$ ，直接预处理出来即可。

$m=1,2,3$ 的情况： $g_1 = x, g_2 = \frac{x(x+1)}{2}, g_3 = \frac{x^3 + 5x}{6}$

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 10;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

LL lim[65];
vector<LL> f[65];

void init() {
	for (int i = 1; i <= 64; ++i) {
		lim[i] = 1e18;
		f[i].push_back(0);
		for (int j = 1; j < N; ++j) {
			LL tmp = f[i][j - 1] + 1;
			if (i > 1) tmp += f[i - 1][j - 1];
			f[i].push_back(tmp);
			if (f[i][j] > 1e18) {
				f[i][j] = 1e18;
				lim[i] = j;
				break;
			}
		}
	}
}

void solve() {
	LL n, m;
	read(n); read(m);
	if (m == 1) printf("%lld\n", n);
	else if (m == 2) {
		__int128 L = 1, R = n, ans = 0;
		while (L <= R) {
			__int128 mid = (L + R) / 2;
			__int128 tmp = mid * (mid + 1) / 2;
			if (tmp >= n) {
				R = mid - 1;
				ans = mid;
			}
			else L = mid + 1;
		}
		printf("%lld\n", (LL) ans);
	}
	else if (m == 3) {
		__int128 L = 1, R = 1e8, ans = 0;
		while (L <= R) {
			__int128 mid = (L + R) / 2;
			__int128 tmp = (mid * mid * mid + mid * 5) / 6;
			if (tmp >= n) {
				ans = mid;
				R = mid - 1;	
			}
			else L = mid + 1;
		}
		printf("%lld\n", (LL) ans);
	}
	else {
		int L = 1, R = lim[m], ans = 0;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (f[m][mid] >= n) {
				ans = mid;
				R = mid - 1;	
			}
			else L = mid + 1;
		}
		printf("%d\n", ans);
	}
}

int main() {
	init();
	int T;
	read(T);
	while (T--) solve();
	return 0;
}