Kevin and Teams
进行手玩，发现 \(n\) 从 \(1\) 开始的 \(k\) 分别为 \([0,1,1,1,2,2,\dots]\)。
不妨猜测 \(k = \lfloor \frac{n+1}{3} \rfloor\)，考虑构造性证明这一点。
我们考虑同时保存一组黑色匹配和一组白色匹配，此时我们需要维护一条同色链。
每次我们加入点 \(u\)，假设点 \(u\) 与链尾的边与链同色，则加入点 \(u\)。否则点 \(u\) 与链尾的边与链异色，此时我们去除这两条边，分别加入两个匹配即可。
显然我们会用 \(3\) 个点产生一组匹配，假设链外有 \(3a\) 个点，则匹配数为 \(\lceil \frac{n-3a-1}{2} \rceil + a = \lfloor \frac{n-3a}{2} \rfloor + a = \lfloor \frac{n-a}{2} \rfloor\)。显然 \(a \leq \lfloor \frac{n}{3} \rfloor\)，则原式 \(\geq \lfloor \frac{n - \lfloor \frac{n}{3} \rfloor}{2} \rfloor = \lfloor \frac{\lceil \frac{2n}{3} \rceil}{2} \rfloor = \lfloor \frac{\lfloor \frac{2n+2}{3} \rfloor}{2} \rfloor = \lfloor \frac{2n+2}{6} \rfloor = \lfloor \frac{n+1}{3} \rfloor\)。
其次我们构造一组解，使得 \(k = \lfloor \frac{n+1}{3} \rfloor\)。
不妨考虑构造一个 \(m\) 个点的完全图，此时的答案为 \(\max(\lfloor \frac{m}{2} \rfloor,n-m)\)，也就是 \(\lfloor \frac{\max(m,2n-2m)}{2} \rfloor\)。容易发现上式 \(\geq \lceil \frac{2n}{3} \rceil\)，同上分析即可得到此下界。
#include<iostream>
#include<vector>
#include<stack>
using namespace std;
void solve(){int n;cin>>n;int k=(n+1)/3;cout<<k<<endl;stack<int> st;int flag=0;vector<int> U[2],V[2];for(int i=1;i<=n;i++){if(st.size()==0){st.push(i);}else if(st.size()==1){int u=st.top();cout<<"? "<<u<<" "<<i<<endl;cin>>flag;st.push(i);}else{int u=st.top();st.pop();int v=st.top();cout<<"? "<<u<<" "<<i<<endl;int num;cin>>num;if(num==flag){st.push(u);st.push(i);}else{st.pop();U[flag].push_back(u);V[flag].push_back(v);U[num].push_back(u);V[num].push_back(i);}}}bool tmp=false;while(!st.empty()){if(tmp==false){U[flag].push_back(st.top());}else{V[flag].push_back(st.top());}st.pop();tmp=!tmp;}cout<<"!";for(int i=0;i<k;i++){cout<<" "<<U[flag][i]<<" "<<V[flag][i];}cout<<endl;
}
int main(){int T;cin>>T;while(T--){solve();}return 0;
}