超燃智斗，电池假死

AAA混凝土批发ppl哥

2025-10-06 03:54:17

发布于：广东

46阅读

0回复

0点赞

自己左脑右脑博弈了 50min，结果发现正解就是暴力试

不管怎么说，纪念首次通过交互题。

题意解析：

交互题。

你有 $n$ 个电池，其中有 $a(a\ge 2)$ 个电池是能用的， $(n-a)$ 个电池不能用。但你不知道哪些电池能用，你甚至不知道 $a$ 的值。

你需要找到两个能用的电池来组装你的手电筒。你可以进行如下的尝试操作：

选择两个数 $x,y(x\not= y)$ 。
将第 $x$ ，第 $y$ 个电池装进你的手电筒，如果这两个电池都是能用的，则手电筒发光；否则手电筒不发光。

~~问：这两节电池应_______（选填“串联”或“并联”）。~~

由于出题人不想你太快得出结论，所以他要求你进行不超过 $\lfloor\frac{n^2}{a}\rfloor$ 次尝试操作。

考虑如下方法：

首先尝试 $x=1,y=2$ ， $x=2,y=3$ ，...， $x=n-1,y=n$ 。如果没有一次手电筒发光的情况，则说明任意两个好的电池的距离 $\ge 2$ ，可以推导出 $a\le \lceil\frac{n}{2}\rceil$ 。

然后尝试 $x=1,y=3$ ， $x=2,y=4$ ，...， $x=n-2,y=n$ 。同理，如果没有一次手电筒发光的情况，则 $a\le\lceil\frac{n}{3}\rceil$ 。

接着尝试距离为 $3,4,5,...$ 的，直到试出来为止。

假设正整数 $k$ 满足 $\lceil\frac{n}{k-1}\rceil\lt a\le \lceil\frac{n}{k}\rceil$ 。

则 $k\le \lfloor\frac{n}{a}\rfloor$ 。

则按照上面的方法会试不超过 $n+(n-1)+(n-2)+...+(n-k-1)\lt nk$ 次。

即尝试次数不超过 $n\times \lfloor\frac{n}{a}\rfloor\le \lfloor\frac{n^2}{a}\rfloor$ 次，可以通过。

#include <iostream>
#include <cstdio>
using namespace std;
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n - i; j++){
			cout << j << ' ' << j + i << '\n';
			int ans;
			cin >> ans;
			if(ans == 1) return;
		}
	}
}
int main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

AAA混凝土批发ppl哥
d

6天前来自广东
1
ppl 大帝
容易发现，cjdst特别喜欢在acgo发题解，然而都没人认真看完

6天前来自浙江
0
- AAA混凝土批发ppl哥
  回复ppl 大帝
  555
  
  6天前来自广东
  0

全部评论 2

热门讨论