Codeforces

Luogu

分析

蓝题都不会做了 /kk

因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。

那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。

如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int main() {
    srand(19491001);
    int T=read();
    while (T--) {
        int n=read(),k=read(),flag=0;
        for (int i=1;i<=20;++i) {
            printf("? 1 1\n1\n%d\n",rand()%(n-1)+2);
            fflush(stdout); char s[10]; scanf("%s",s);
            if (s[0]=='S') { flag=1; break; }
        }
        if (flag) { puts("! 1"); fflush(stdout); continue; }
        for (int i=1;i<=n;i<<=1) {
            int len=min(i<<1,n)-i;
            printf("? %d %d\n",len,len);
            for (int j=1;j<=len;++j) printf("%d ",j); puts("");
            for (int j=i+1;j<=min(i<<1,n);++j) printf("%d ",j); puts("");
            fflush(stdout); char s[10]; scanf("%s",s);
            if (s[0]=='F') {
                int L=i+1,R=min(i<<1,n);
                while (L<R) {
                    int mid=(L+R)>>1;
                    printf("? %d %d\n",mid-i,mid-i);
                    for (int j=1;j<=mid-i;++j) printf("%d ",j); puts("");
                    for (int j=i+1;j<=mid;++j) printf("%d ",j); puts("");
                    fflush(stdout); char s[10]; scanf("%s",s);
                    if (s[0]=='F') R=mid;
                    else L=mid+1;
                }
                printf("! %d\n",L); fflush(stdout); break;
            }
        }
    }
    return 0;
}