火花灿灿

题目：

数据范围：

题解：

这个题真的是个神仙题。

我们对于每块石头维护一个$01$串。

这个$01$串的长度是操作次数。

如果$01$串的当前位是$1$，表示这次操作中当前石子被划分到了贡献当中，就是被划分到了$b_i$中。

那么如果所有的石子都单独一堆，必定是所有的$01$串都互不相同。

而且有一个限制就是每一列最多$m$个。

显然$01$的长度具有单调性。

故此二分答案之后考虑怎么验证。

我们相当于在一个$n\times mid$的棋盘上添$1$使得满足要求。

首先有一个贪心，就是对于每一行来讲，能添$k$个数绝对不填$k + 1$个数，这是显然的吧。

故此我们从每行第一个数开始往下填，填到每行$i$个数。

每行$i$个数，共有$C_{mid}^{i}$种情况，也就是说$n -= C_{mid} ^ {i}$。

与此同时，每列会加$C_{mid - 1}^{i - 1}$个数，也就是说$m -= C_{mid - 1} ^ {i - 1}$。

只需要判断一下最后是谁完事儿就行了。

但是如果到了最后，两边都不足以减掉一次怎么办？

只需要判断一下一共还剩下多少$1$可以填，看看够不够剩下的行即可，详见代码。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0, f = 1;

	char c = nc();

	while (c < 48) {

		if (c == '-')

			f = -1;

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x * f;

}

ll qpow(ll x, ll y) {

	int ans = 1;

	while (y) {

		if (y & 1) {

			ans = ans * x;

		}

		y >>= 1;

		x = x * x;

	}

	return ans;

}

int n, m;

bool check(int x) {

	ll re1 = n - 1;

	ll re2 = m;

	ll C1 = -1, C2 = -1;

	for (int i = 1; i <= x; i ++ ) {

		// puts("Fuck");

		if (C1 == -1) {

			C2 = 1;

			C1 = x;

		}

		else {

			(C1 *= (x - i + 1)) /= i;

			(C2 *= (x - i + 1)) /= (i - 1);

		}

		// cout << C1 << ' ' << C2 << endl ;

		// cout << re1 << ' ' << re2 << endl ;

		if(re1 < C1) {

			return re1 * i <= re2 * x;

		}

		else {

			if (re2 < C2) {

				return false;

			}

			else {

				re1 -= C1;

				re2 -= C2;

			}

		}

	}

	if (!re1) {

		return true;

	}

	return false;

}

int main() {

	// freopen("fire.in", "r", stdin);

	// freopen("fire.out", "w")

	int T = rd();

	while (T -- ) {

		n = rd(), m = rd();

		if (n == 1) {

			puts("0");

			continue;

		}

		int l = 1, r = n;

		int ans = n;

		check(2);

		while (l <= r) {

			// printf("%d %d\n", l, r);

			int mid = (l + r) >> 1;

			if (check(mid)) {

				ans = mid;

				r = mid - 1;

			}

			else {

				l = mid + 1;

			}

		}

		printf("%d\n", ans);

	}

	return 0;

}

/*

1

4 2

*/

/*

12

4 1

4 2

7 3

1 1

42 7

2333333 2

2333333 23

2333333 233

2333333 2333

2333333 23333

2333333 233333

2333333 2333333

*/

小结：能开$long\ long$就开吧，不能慢多少。

巴特西

[校内模拟赛T3]火花灿灿_二分答案_组合数学_贪心

火花灿灿

最新文章

热门文章