前言
这辈子注定与交互题无缘。不过这道题确实挺妙的。
题目
讲解
直接讲做法。
这是一个 BFS 的过程,状态为我们知道多少个数的异或和。
因为我们不需要具体知道是哪些数的异或和,只需要知道个数,这很显然,但这是这道题最重要且最难想到的点。
然后我们可以用 BFS 求出知道 (n) 个数的异或和的最少操作数。
中途记录一下前驱,构造就随便搞搞就行。
代码
//12252024832524
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 505;
const int INF = 0x3f3f3f3f;
int n,k,ans;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int pre[MAXN],c[MAXN];
bool vis[MAXN];
void bfs()
{
queue<int> q; q.push(0); vis[0] = 1;
while(!q.empty())
{
int t = q.front(); q.pop();
for(int i = 0;i <= Min(t,k);++ i)//chosen number
{
int to = t-i+(k-i);
if(k-i <= n-t && !vis[to])
{
vis[to] = 1;
pre[to] = t;
c[to] = i;
q.push(to);
}
}
}
}
int a[MAXN],tot,E[MAXN],Etot,D[MAXN],Dtot;
int tmp[MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); k = Read();
bfs();
if(!vis[n]) {Put(-1);return 0;}
int now = n;
while(now)
{
a[++tot] = now;
now = pre[now];
}
for(int i = 1;i <= n;++ i) D[i] = i;
Dtot = n;
for(int i = tot;i >= 1;-- i)
{
int cs = c[a[i]]; int ot = k - c[a[i]];
putchar('?');
for(int j = 1;j <= ot;++ j) tmp[j] = D[Dtot-j+1],putchar(' '),Put(tmp[j]);
Dtot -= ot;
for(int j = 1;j <= cs;++ j) D[++Dtot] = E[Etot--],putchar(' '),Put(D[Dtot]);
for(int j = 1;j <= ot;++ j) E[++Etot] = tmp[j];
putchar('
');
fflush(stdout);//要在输入之前
ans ^= Read();
}
putchar('!'); putchar(' '); Put(ans);
return 0;
}