自动搬运

查看原文

来自洛谷，原作者为

	言琢დ “我会成为这里的主宰，清除掉整片土地上的一切障碍，只留下我跟那一堆白骨，她永远不朽，而我不死不灭。”

搬运于2025-08-24 22:34:08，当前版本为作者最后更新于2021-10-20 20:23:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

出题人题解。

E 黄牛の争

数学模型

考虑优化 Special Judge 中 win 函数部分的暴力，首先记

• $\alpha=\left\lceil\dfrac{B}{a}\right\rceil$ 表示 $\tt A$ 击败 $\tt B$ 所需回合数；

• $\beta=\left\lceil\dfrac{A}{b}\right\rceil$ 表示 $\tt B$ 击败 $\tt A$ 所需回合数。

那么：

• 如果 $\tt B$ 是先手，仅需 $\beta\le\alpha$ 即可击败 $\tt A$；

• 如果 $\tt B$ 是后手，则需 $\beta<\alpha$ 才能击败 $\tt A$。

据此，可以得到 $\tt B$ 击败 $\tt A$ 的条件：

$$\left\lceil\frac{A}{b}\right\rceil+[b<a]\le\left\lceil\frac{B}{a}\right\rceil $$

那么 $O(1)$ 的判定胜负的代码：

bool win(int a, int b, int c, int d){
	return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}

---

下面开始分析每个子任务的得分方式。

Subtask 1

$c,C$ 枚举上限 $(M-1)^2$，考虑优化：

1. $\texttt{C}$ 只需要能击败 $\texttt{B}$，因此 $c$ 的枚举上限应为 $\max(1+b,B)$。

2. $\texttt{C}$ 必须输给 $\texttt{A}$，因此 $c$ 的枚举上限应为 $\max(a,A)-1$。

Subtask 2

固定 $c$ 之后，$C$ 越大 $\tt C$ 越强，$C$ 越小 $\tt C$ 越弱。

所以 $C$ 的合法取值一定在一个区间 $[l,r]$ 上，可以考虑二分 $C$。

Subtask 3, 5

留给一些正确性可能看起来很对的奇怪做法。（比如某不知名 $O(\sqrt[3]M\log M)$ 的做法）

Subtask 4

那么这部分分显然是希望我们给出一个 $O(M)$ 的线性做法。

考虑如果我们确定了 $c$，继续推一推式子（其实也就是挪一挪系数），得到：

$$b\times\left(\left\lfloor\dfrac{B}{c}\right\rfloor+[c<b]\right)~\le~C~\le~\left(\left\lfloor\dfrac{A}{c}\right\rfloor-[a<c]\right)\times a+a-1 $$

据此就可以 $O(1)$ 求出 $C$ 的值。

Subtask 6

考虑一种更快的枚举 $c$ 的方式。

由于 $c$ 作为分母，它的取值只影响

$$\left\lceil\dfrac{A}{c}\right\rceil,\left\lceil\dfrac{B}{c}\right\rceil $$

的取值，我们可以整除分块枚举 $c$ 的取值。

一种上取整转下取整的办法：

$$\left\lceil\dfrac{p}{q}\right\rceil=\left\lfloor\dfrac{p-1}{q}\right\rfloor+1 $$

另外，朴素的整除分块只枚举到

$$\min\{A,B\}$$

但是我们的 $c$ 应当一直到

$$\max\{A,B\}$$

处都可能具有贡献。

所以我们考虑根据题意分成两段枚举，第一段使用朴素的整除分块。

第二段枚举 $\min(A,B)\sim\max(A,B)$ 之间的答案贡献部分即可。

std

//E1
#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
	return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int mn(int a, int b){
	return a < b ? a : b;
}
int mx(int a, int b){
	return a > b ? a : b;
}
int main(){
	int q = init();
	while (q--) {
		int a = init(), A = init(), b = init(), B = init();
		if (win(b, B, a, A)) {
			puts("-1 -1");
			continue;
		}
		bool flag = 1;
		for(int x = 1; x <= 100; ++x)
			for(int y = 1; y <= 100 && flag; ++y)
				if (x != a && x != b && win(b, B, x, y) && win(x, y, a, A))
					flag = 0, print(x), putchar(' '), print(y), putchar('\n');
		if(flag)
			print(-1), putchar(' '), print(-1), putchar('\n');
	}
}
//E2
#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
	return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int mn(int a, int b){
	return a < b ? a : b;
}
int mx(int a, int b){
	return a > b ? a : b;
}
signed main(){
	int q = init();
	while (q--) {
		int a = init(), A = init(), b = init(), B = init();
		int MAX = mn(mx(1 + b, B), mx(a, A) - 1);
		int M = mx(mx(a, A), mx(b, B));
		if (!win(a, A, b, B) || (B > A && b > a)) {
			puts("-1 -1");
			continue;
		}
		bool flag=1;
		for (int c = 1; c <= MAX; ++c) {
			if (c == a || c == b)
				continue;
			int l = 1, r = (M - 1) * (M - 1), ans = -1;
			if (c > a) r = A - 1;
			if (c < b) l = B + 1;
			while (l <= r) {
				int mid = l + r >> 1;
				if (!win(c, mid, a, A))
					r = mid - 1;
				else if (!win(b, B, c, mid))
					l = mid + 1;
				else {
					ans = mid;
					break;
				}
			}
			if (ans != -1) {
				print(c), putchar(' '), print(ans), putchar('\n');
				flag = 0;
				break;
			}
		}
		if (flag)
			puts("-1 -1");
	}
}
//E3
#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
	return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int a, A, b, B;
int ok(int c){
	if (c == a || c == b)
		return 0;
	int l = b * (B / c + (c < b)),
	r = (A / c - (a < c)) * a + a - 1;
	if (l > r)
		return 0;
	return l + 1;
}
int mn(int a, int b){
	return a < b ? a : b;
}
int mx(int a, int b){
	return a > b ? a : b;
}
signed main(){
	int t = init();
	for (int i = 1; i <= t; ++i) {
		a = init(), A = init(), b = init(), B = init();
		if (!win(a, A, b, B) || (B > A && b > a)) {
			puts("-1 -1");
			continue;
		}
		--A, --B;
		int c = 0, C;
		if (!ok(a + 1) && !ok(b + 1)) {
			for (int i = 1; i <= mx(A, B); ++i)
				if (ok(i)) {
					c = i, C = ok(i);
					break;
				}
		}
		else {
			if (ok(a + 1))
				c = a + 1, C = ok(a + 1);
			if (ok(b + 1))
				c = b + 1, C = ok(b + 1);
		}
		if (c)
			print(c), putchar(' '), print(C), putchar('\n');
		else
			puts("-1 -1");
	}
}
//E4
#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
bool win(int a, int b, int c, int d){
	return (b + c - 1) / c + (c < a) <= (a + d - 1) / a;
}
int a, A, b, B;
int ok(int c){
	if (c == a || c == b)
		return 0;
	int l = b * (B / c + (c < b)),
	r = (A / c - (a < c)) * a + a - 1;
	if (l > r)
		return 0;
	return l + 1;
}
int mn(int a, int b){
	return a < b ? a : b;
}
int mx(int a, int b){
	return a > b ? a : b;
}
signed main(){
	int t = init();
	for (int i = 1; i <= t; ++i) {
		a = init(), A = init(), b = init(), B = init();
		if (!win(a, A, b, B) || (B > A && b > a)) {
			puts("-1 -1");
			continue;
		}
		--A, --B;
		int c = 0, C;
		if (!ok(a + 1) && !ok(b + 1)) {
			for (int i = 1; i <= A && i <= B; i = mn(A / (A / i), B / (B / i)) + 1)
				if (ok(i)) {
					c = i, C = ok(i);
					break;
				}
			for (int i = mn(A, B) + 1; i <= mx(A, B); i = mx(A, B) / (mx(A, B) / i) + 1)
				if (ok(i)) {
					c = i, C = ok(i);
					break;
				}
		}
		else {
			if (ok(a + 1))
				c = a + 1, C = ok(a + 1);
			if (ok(b + 1))
				c = b + 1, C = ok(b + 1);
		}
		if (c)
			print(c), putchar(' '), print(C), putchar('\n');
		else
			puts("-1 -1");
	}
}