题解：P12531 [XJTUPC 2025] Beat Verdict: Precision Strike

思路

发现

[0.5n, \, 2n]

的范围中，在

x

很大时会包含很多数，所以考虑将一个区间的数用一个代表记下，这个范围的数在输出代表时均满足。

于是得到如下表格：

区间	代表	区间	代表
$[1, \, 4]$	$2$	$[87381, \, 349524]$	$174762$
$[5, \, 20]$	$10$	$[349525, \, 1398100]$	$699050$
$[21, \, 84]$	$42$	$[1398101, \, 5592404]$	$2796202$
$[85, \, 340]$	$170$	$[5592405, \, 22369260]$	$11184810$
$[341, \, 1364]$	$682$	$[22369261, \, 89478484]$	$44739242$
$[1365, \, 5460]$	$2730$	$[89478485, \, 357913940]$	$178956970$
$[5461, \, 21844]$	$10922$	$[357913941, \, 1431655764]$	$715827882$
$[21845, \, 87380]$	$43690$	$[1431655765, \, 5726623060]$	$2863311530$

~~事实上不看表格也行。~~

总之，设第

i

个区间代表为

f_i

，那么

f_1 = 2

，

f_i = (2 \times f_{i - 1} + 1) \times 2

，对应区间为

[0.5f_i, \, 2f_i]

。

然后你发现刚好

16

个区间，用二分刚好就能在

4

次询问内解决。

然后，就没有然后了。

思路

先预处理代表

f_i

，之后每一次测试二分。

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll c[20];
int T;

int main() {
	c[1] = 2;
	for (int i = 2 ; i <= 16 ; i++)
		c[i] = (c[i - 1] * 2 + 1) * 2;
	for (int i = 1 ; i <= 16 ; i++)
		printf("%lld %lld %lld\n", c[i] / 2, c[i], c[i] * 2);
	cin >> T;
	for (ll n ; T-- ; ) {
		cin >> n;
		int L = 1, R = 2;
		for (int i = 1 ; i <= 16 ; i++)
			if (c[i] * 2 < n) ++R;
		while (L < R - 1) {
			int mid = (L + R) >> 1, k;
			cout << "? " << c[mid] / 2 << endl;
			cin >> k;
			if (k) R = mid;
			else L = mid;
		}
		if (c[L] > n) cout << "! " << n << endl;
		else cout << "! " << c[L] << endl;
	}
	return 0;
}

题解：P12531 [XJTUPC 2025] Beat Verdict: Precision Strike

文章操作

思路

思路

相关推荐

评论

题解：P12531 [XJTUPC 2025] Beat Verdict: Precision Strike