「RdOI R2」称重(weigh) 题解

rui_er

2021-04-16 18:39:42

Solution

**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; } ```