「RdOI R2」称重(weigh) 题解
rui_er
2021-04-16 18:39:42
**UPD(2021.6.22):加强了数据,更新解法。**
本题解是「RdOI R2」称重(weigh) 的官方题解。
简单思维题。
根据题意,一个假球比一个真球轻,但两个假球比一个真球重,显然询问一要得到信息肯定要使 $p=q$,否则得不到任何有用的信息。
考虑分类讨论:
- 第一种情况:在 $n=2i$ 个球中找一个假球。
考虑将球拆为两组,每组有 $i$ 个球,并询问。因为只有一个假球,显然两组的质量肯定不相等,此时假球在质量更小的一组。
- 第二种情况:在 $n=2i$ 个球中找两个假球。
同样拆成两组,各 $i$ 个球。如果得到 `=`,则两组各有一个假球;否则两个假球都在质量更小的一组。
- 第三种情况:在 $n=2i+1$ 个球中找一个假球。
将球拆为三组,分别有 $i,i,1$ 个,询问 $i$ 个球的两组。如果得到 `=`,则单独的球是假球;否则假球在质量更小的一组。
- 第四种情况:在 $n=2i+1$ 个球中找两个假球。
同样拆成三组,分别有 $i,i,1$ 个。询问前两组。如果得到 `=`,则两组各有一个假球;否则在质量更大的一组(总共只有两个假球,可以断定这组必定全为真球)中取一个球与单独的球询问,质量相等则两个假球都在质量更小的一组,否则单独的球是假球,另一个假球在质量更小的一组。
现在思路就比较显然了吧,初始状态是 $\left[1,n\right]$ 中找两个假球,然后按照上面的分类讨论进行二分即可。
std 在所有测试点中的最大询问次数是 $15$ 次。
给出 std 代码供参考:[Link](/paste/2hmfhyk8)
---
**但是上面的 std 在 2021.6.22 的数据加强中被卡成了 Unaccepted $99$ 分。**
考虑进一步优化。
当在区间内找一个假球的时候,我们每次排除 $\dfrac{1}{2}$ 的球,但是显然可以更优。我们在左、右各取大约 $\dfrac{1}{3}$ 的球进行询问,如果相等则递归询问中间段,否则询问更轻的段,这样利用三分的思想,每次可以排除 $\dfrac{2}{3}$ 的球。
代码:
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 505;
int n, a[N], b[N];
vector<int> ans;
int interact(int *a, int p, int *b, int q) {
printf("1 %d ", p);
rep(i, 1, p) printf("%d ", a[i]);
printf("%d ", q);
rep(i, 1, q) printf("%d%c", b[i], " \n"[i==q]);
fflush(stdout);
char tmp[2];
scanf("%s", tmp);
if(tmp[0] == '<') return -1;
if(tmp[0] == '=') return 0;
return 1;
}
void searchAns(int L, int R, int k) {
// printf("searchAns %d %d %d\n", L, R, k);
int len = R - L + 1, M = (L + R) >> 1, tA = 0, tB = 0;
int ML = L + (R - L) / 3, MR = R - (R - L) / 3;
// printf("%d %d\n", ML, MR);
if(len == k) {
if(k == 1) ans.push_back(L);
else ans.push_back(L), ans.push_back(R);
return;
}
if(k == 1) {
rep(i, L, ML) a[++tA] = i;
rep(i, MR, R) b[++tB] = i;
int res = interact(a, tA, b, tB);
if(!res) return searchAns(ML+1, MR-1, 1);
if(res == 1) return searchAns(MR, R, 1);
return searchAns(L, ML, 1);
}
if(len & 1) {
rep(i, L, M-1) a[++tA] = i;
rep(i, M, R-1) b[++tB] = i;
int res = interact(a, tA, b, tB);
if(!res) {
searchAns(L, M-1, 1);
searchAns(M, R-1, 1);
}
else if(res == 1) {
a[1] = L; b[1] = R;
int qwq = interact(a, 1, b, 1);
if(qwq == 1) {
ans.push_back(R);
searchAns(M, R-1, 1);
}
else searchAns(M, R-1, 2);
}
else {
a[1] = R - 1; b[1] = R;
int qwq = interact(a, 1, b, 1);
if(qwq == 1) {
ans.push_back(R);
searchAns(L, M-1, 1);
}
else searchAns(L, M-1, 2);
}
}
else {
rep(i, L, M) a[++tA] = i;
rep(i, M+1, R) b[++tB] = i;
int res = interact(a, tA, b, tB);
if(!res) {
searchAns(L, M, 1);
searchAns(M+1, R, 1);
}
else if(res == 1) searchAns(M+1, R, 2);
else searchAns(L, M, 2);
}
}
int main() {
scanf("%d", &n);
searchAns(1, n, 2);
sort(ans.begin(), ans.end());
printf("2 %d %d\n", ans[0], ans[1]);
fflush(stdout);
return 0;
}
```