出题人题解。

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");
	}
}