题解 P7045 【「MCOI-03」金牌】

stoorz · 2020-11-03 20:10:33 · 题解

有一个很直接的想法是我们枚举每一块金牌 i，将前 i 块中剩余的金牌扔到队列里。如果第 i 块金牌和队列里的金牌不一致，那么就将这两块金牌都加入答案序列，否则将 i 压入队列中。

那么最后有若干个多出来的互相排斥的金牌在队列中，我们就枚举答案序列，如果相邻两项均与在队列中的金牌吸引，那么就在它们之间插入一块金牌。

如果最终队列里还有金牌，那么该情况就无解。因为上述操作保证了相邻两个中一定有一块金牌和队列中金牌互相排斥，所以任何情况下这种金牌都无法全部插入答案中。

由于我们最开始将 0 直接加入到答案序列中，所以最多会有 2(n-1)=2n-2 次交互。

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int Q,n,m,ret,ans[N];
queue<int> q;

void prework()
{
    while (q.size()) q.pop();
    m=1; ans[1]=0;
}

int main()
{
    scanf("%d",&Q);
    while (Q--)
    {
        scanf("%d%d",&n,&m);
        prework();
        for (int i=1;i<n;i++)
            if (!q.size())  //将能插入的金牌插入到答案序列，否则扔到队列里
            {
                printf("%d %d\n",i,ans[m]);
                fflush(stdout);
                scanf("%d",&ret);
                if (ret) ans[++m]=i;
                    else q.push(i);
            }
            else
            {
                printf("%d %d\n",i,q.front());
                fflush(stdout);
                scanf("%d",&ret);
                if (ret) ans[++m]=i,ans[++m]=q.front(),q.pop();
                    else q.push(i);
            }
        for (int i=2*m;i>=1;i-=2)
            ans[i]=ans[i/2],ans[i-1]=-1;  //将两个金牌中隔出一个空位
        if (q.size())
        {
            bool last=1;
            for (int i=2;i<=2*m;i+=2)  //枚举并判断是否有两个金牌间还可以再次插入
            {
                printf("%d %d\n",q.front(),ans[i]);
                fflush(stdout);
                scanf("%d",&ret);
                if (ret && last) ans[i-1]=q.front(),q.pop();
                if (!q.size()) break;
                last=ret;
            }
        }
        if (q.size()) printf("-1\n");
        else
        {
            printf("%d\n",n);
            for (int i=1;i<=2*m;i++)
                if (ans[i]!=-1) printf("%d ",ans[i]);
            printf("\n");
        }
        fflush(stdout);
    }
    return 0;
}