专栏文章

题解：CF2061G Kevin and Teams

__abcd_
CF2061G题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqfpd7k
此快照首次捕获于
2025/12/04 04:03
3 个月前
此快照最后确认于
2025/12/04 04:03
3 个月前
查看原文

[CF2061G] Kevin and Teams

考虑一种构造：将 2/32/3 的点两两连边，剩下的点都不连，那么最多有 ⌊n+13⌋\left\lfloor \frac{n+1}{3} \right\rfloor 组匹配。
考虑询问方案：维护一条同色链，令链的末尾的点为 aa，倒数第二个点为 bb，每次询问新点 cc 和 aa 的关系。如果和这条链同色，则将新点加入到链的末尾，否则将 a,ca,c 作为一种颜色的匹配，b,cb,c 作为另一种颜色的匹配，然后将 b,cb,c 从链末删去。最后会剩下一条链，两两匹配即可。不难证明最后链的颜色的匹配数量至少为 ⌊n+13⌋\left\lfloor \frac{n+1}{3} \right\rfloor。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...