题目描述
这是一道交互题。
\(T\) 组数据，一张 \(n\) 个点的无向完全图，边权 \(\in\{0,1\}\) ，边权未知。
你需要先输出最大的 \(k\) ，满足无论每条边的边权是什么，都能找出 \(2k\) 个不同的点 \(\{u_1,\cdots,u_n,v_1,\cdots,v_n\}\) ，使得边 \((u_i,v_i)\) 的权值同时为 \(0\) 或同时为 \(1\) 。
接下来你可以执行至多 \(n\) 次以下操作：
- 输出
? u v，你需要保证 \(1\le u\neq v\le n\) ，交互库将返回这条边的边权。
然后你需要输出 ! u_1 v_1 ... u_k v_k ，表示答案。
数据范围
- \(1\le T\le 10^4,1\le n\le 10^5,\sum n\le 10^5\) 。
时间限制 \(\texttt{4s}\) ，空间限制 \(\texttt{256MB}\) 。
分析
神题！
题目要求 \(n\) 固定时最大的 \(k\) ，我们先反向思考，求 \(k\) 固定（找不到 \(k+1\) 个点对）时最大的 \(n\) 。
结论：\(n\le 3k+1\) 。
构造：令 \(|S_1|=2k+1,|S_2|=k\) ， \(S_1\) 内部边权全为 \(0\) ， \(S_2\) 内部以及 \(S_1,S_2\) 之间的边全为 \(1\) 。
证明可以通过后面的交互过程完成。
怎么想到的？直觉判断应该有一个边权为 \(0\) 的完全子图，然后只要涉及到剩下的点则边权为 \(1\) ，调一调 \(S_1\) 和 \(S_2\) 的大小即可。
因此当 \(n\ge 3k+2\) 时，至少可以找到 \(k+1\) 个点对。
对于一般的 \(n\) ， \(\max k=\lfloor\frac{n+1}3\rfloor\) ，这也是第一问的答案。
构造也并不容易。
首先最朴素的归纳构造毫无前途，假如你有 \(k\) 对 \(0\) 边，你是无法基于此构造出 \(k+1\) 对 \(0\) 边的，因为极端情况下其余所有边都是 \(1\) 。
根据 \(k\) 的范围，大约每 \(3\) 个点就要找一条边，我们尝试寻找 "万金油" 类型的结构。
如果 \((a,b)\) 边权为 \(0\) ， \((a,c)\) 边权为 \(1\) ，那么将 \((a,b,c)\) 三个点删去，至少能找到 \(k-1\) 条颜色相同的边。无论这些边颜色是什么，我们总能从 \((a,b,c)\) 中找到一条边与它们颜色相同。
如果某个子图不存在这种 "万金油" 结构，那就只能是完全图了。当然我们也不必保证一定是完全图，因为询问次数有限。总共询问次数不超过 \(n\) ，平均每个点被询问不超过 \(2\) 次，构造一条颜色相同的链还是可以的。
基于此可以给出以下构造：
维护一条颜色相同（记为
col）的链，每次新加一个点：
- 如果链头与新点之间的边与
col相同，让新点成为链头。- 如果链头与新点之间的边与
col不同，删去链头和次链头，这两个点与新点共同构成 "万金油" 结构。由于每个 "万金油" 结构等价于令
n-=3,k-=1，对结论没有影响。而长为 \(n\) 的链可以找出 \(\lfloor\frac n2\rfloor\ge\lfloor\frac{n+1}3\rfloor\) 个点对，因此构造成立。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int k,n,t,col,top;
int st[maxn];
vector<array<int,3>> vec;
int ask(int x,int y)
{
printf("? %d %d\n",x,y),fflush(stdout);
return scanf("%d",&x),x;
}
int main()
{
for(scanf("%d",&t);t--;)
{
scanf("%d",&n),k=(n+1)/3;
printf("%d\n",k),fflush(stdout);
col=top=0,vec.clear();
for(int i=1;i<=n;i++)
{
if(!top) st[++top]=i;
else if(top==1) st[++top]=i,col=ask(st[1],st[2]);
else
{
int x=ask(i,st[top]);
if(x==col) st[++top]=i;
else
{
array<int,3> tmp={st[top],st[top-1],i};
if(!x) swap(tmp[1],tmp[2]);
vec.push_back(tmp),top-=2;
}
}
}
printf("! ");
for(int i=1;i<=min(top/2,k);i++) printf("%d %d ",st[2*i-1],st[2*i]);
for(int i=0;i<k-top/2;i++) printf("%d %d ",vec[i][0],vec[i][col+1]);
putchar('\n'),fflush(stdout);
}
return 0;
}
总结
-
博主赛时花 \(\texttt{1.5h}\) 过了 \(\texttt{A}\sim\texttt{E1}\) ，剩下一半时间全花在这道题上，核心难点都突破了，但是没能通过这道题，遗憾错失上大分的机会。
下面请欣赏博主赛时犯下的弱智错误：
for(int i=1;i<=top/2;i++) ;///输出链 for(int i=0;i<k-top/2;i++) ;///输出三角形top/2>k时输出过多，呜呜呜！