「RdOI R2」称重(weigh) 题解

· · 题解

UPD(2021.6.22)：加强了数据，更新解法。

本题解是「RdOI R2」称重(weigh) 的官方题解。

简单思维题。

根据题意，一个假球比一个真球轻，但两个假球比一个真球重，显然询问一要得到信息肯定要使 p=q，否则得不到任何有用的信息。

考虑分类讨论：

考虑将球拆为两组，每组有 i 个球，并询问。因为只有一个假球，显然两组的质量肯定不相等，此时假球在质量更小的一组。

同样拆成两组，各 i 个球。如果得到 =，则两组各有一个假球；否则两个假球都在质量更小的一组。

将球拆为三组，分别有 i,i,1 个，询问 i 个球的两组。如果得到 =，则单独的球是假球；否则假球在质量更小的一组。

同样拆成三组，分别有 i,i,1 个。询问前两组。如果得到 =，则两组各有一个假球；否则在质量更大的一组（总共只有两个假球，可以断定这组必定全为真球）中取一个球与单独的球询问，质量相等则两个假球都在质量更小的一组，否则单独的球是假球，另一个假球在质量更小的一组。

现在思路就比较显然了吧，初始状态是 \left[1,n\right] 中找两个假球，然后按照上面的分类讨论进行二分即可。

std 在所有测试点中的最大询问次数是 15 次。

给出 std 代码供参考：Link

但是上面的 std 在 2021.6.22 的数据加强中被卡成了 Unaccepted 99 分。

考虑进一步优化。

当在区间内找一个假球的时候，我们每次排除 \dfrac{1}{2} 的球，但是显然可以更优。我们在左、右各取大约 \dfrac{1}{3} 的球进行询问，如果相等则递归询问中间段，否则询问更轻的段，这样利用三分的思想，每次可以排除 \dfrac{2}{3} 的球。

代码：

//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;
}