题解：CF2061G Kevin and Teams

_abcd_ · 2025-01-21 18:05:19 · 题解

[CF2061G] Kevin and Teams

考虑一种构造：将 2/3 的点两两连边，剩下的点都不连，那么最多有 \left\lfloor \frac{n+1}{3} \right\rfloor 组匹配。

考虑询问方案：维护一条同色链，令链的末尾的点为 a ，倒数第二个点为 b ，每次询问新点 c 和 a 的关系。如果和这条链同色，则将新点加入到链的末尾，否则将 a,c 作为一种颜色的匹配， b,c 作为另一种颜色的匹配，然后将 b,c 从链末删去。最后会剩下一条链，两两匹配即可。不难证明最后链的颜色的匹配数量至少为 \left\lfloor \frac{n+1}{3} \right\rfloor 。

#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
int n,m;
stack<int>st;
vector<pair<int,int>>ans[2];
void solve()
{
    n=re();m=(n+1)/3;
    printf("%d\n",m);
    fls();
    bool cl=0;
    while(st.size())
        st.pop();
    ans[0].clear();
    ans[1].clear();
    for(int i=1;i<=n;i++)
    {
        if(!st.size())
            st.push(i);
        else
        {
            int t=st.top();
            printf("? %d %d\n",t,i);
            fls();
            bool ret=re();
            if(st.size()==1)
                cl=ret;
            if(cl!=ret)
            {
                ans[ret].push_back({t,i});
                st.pop();
                int t2=st.top();
                ans[cl].push_back({t2,t});
                st.pop();
            }
            else
                st.push(i);
        }
    }
    while(st.size()>=2)
    {
        int t=st.top();
        st.pop();
        int t2=st.top();
        st.pop();
        ans[cl].push_back({t,t2});
    }
    if(ans[0].size()<m)
        swap(ans[0],ans[1]);
    ans[0].resize(m);
    printf("! ");
    for(auto [u,v]:ans[0])
        printf("%d %d ",u,v);
    pn;
    fls();
}
signed main()
{
    int T=re();
    while(T--)
        solve();
    return 0;
}