Vexoben
Apr 11, 2019
题目链接：51nod1306 高楼和棋子
（刷新以获取数学公式）
题意
有个\(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;
}