变色龙之恋
在 JOI 动物园中，有着 (2N) 只变色龙，编号为 (1ldots 2N)。其中，有 (N) 只变色龙的性别为 X，其余 (N) 只的性别为 Y。
每只变色龙都有一个原色。关于原色的可公开情报如下：
- 所有性别为 X 的变色龙的原色不同。
- 对于每只性别为 X 的变色龙，都存在唯一的原色与其相同的变色龙，且性别为 Y。
现在，JOI 动物园迎来了恋爱的季节。每只变色龙都爱上了另一只变色龙。关于恋爱对象的可公开情报如下：
- 每只变色龙都很专一于唯一一只异性的变色龙。
- 一只变色龙和它的恋爱对象的原色不同。
- 不存在两只变色龙同时追求另一只变色龙。
你可以召集一部分变色龙来组织一场会议。对于一只参加会议的变色龙 (s)，令 (t) 为它的恋爱对象。(s) 的肤色由以下方式决定：
- 如果 (t) 参加了这场会议，则 (s) 的肤色为 (t) 的原色。
- 如果 (t) 没参加这场会议，则 (s) 的肤色为 (s) 的原色。
一只变色龙的肤色可以在不同的会议间发生改变。对于你组织的一场会议，你可以得到场上所有变色龙的肤色的种类数。
由于变色龙也会感到厌烦，所以你最多只能组织 (20\,000) 场会议。同时你需要根据你得到的信息，确定有哪些变色龙的原色相同。
请你写一个程序在组织不超过 (20\,000) 场会议的前提下确定所有相同原色的变色龙。
(2 le N le 500)。
题解
https://hk-cnyali.com/2020/03/24/「JOISC-2020-Day2」变色龙之恋-交互-二分图/
https://blog.csdn.net/zxyoi_dreamer/article/details/105255333
先规定一些记号：
-
(x')：与(x)同色的点。
-
(L(x))：(x)喜欢的点。
-
(L^{-1}(x))：喜欢(x)的点。
考虑先把所有大小为(2)的集合的答案问出来，不难发现答案只可能是(1)或(2)。
答案为(1)的三种情况：({x,x'},{x,L(x)},{x,L^{-1}(x)})。后两种会出现当且仅当(L(x) eq L^{-1}(x))。
我们给答案为(1)的点对((x, y))连一条边，那么每个点的度数只可能是(1)或(3)。
-
若一个点度数为(1)，则可以直接得到同色的点。
-
若一个点度数为(3)，设它为(x)，三条边分别为((x,x'),(x,L(x)),(x,L^{-1}(x)))。只需询问({x,x',L(x)},{x,x',L^{-1}(x)},{x,L(x),L^{-1}(x)})，这三个集合，答案分别为(2,1,2)，那么我们就能得到(L(x))和(L^{-1}(L(x)))。最后我们简单处理一下就能得到同色点了。
这样就得到了询问(O(n^2))的做法了。
考虑优化前半部分的复杂度。
不难发现这些边连成的图是二分图，设当前要处理(i)点与(1 sim i - 1)点之间的连边，考虑将(1 sim i - 1)这些点分成两个独立集，满足集合内部没有边（可以暴力染色处理）。
我们可以根据独立集的性质来判断是否有边: 一个集合(S)是独立集当且仅当( exttt{Query}(S) = |S|)。也就是说，点(i)和一个独立集(S)有边当且仅当( exttt{Query}({S, i}) e |S| + 1)。
于是可以通过二分来逐条找边了。复杂度(O(n log n))。
CO int N=1e3+10;
vector<int> to[N];
int col[N];
vector<int> node[2];
int L[N],vis[N];
void dfs(int x,int c){
col[x]=c,node[c].push_back(x);
for(int y:to[x])if(col[y]==-1) dfs(y,!c);
}
void calc(vector<int> vec,int x){
while(1){
vec.push_back(x);
if(Query(vec)==(int)vec.size()) return;
vec.pop_back();
int l=0,r=vec.size()-1,goal=-1;
while(l<=r){
int mid=(l+r)>>1;
vector<int> tmp(vec.begin()+l,vec.begin()+mid+1);
tmp.push_back(x);
if(Query(tmp)!=(int)tmp.size()) goal=mid,r=mid-1;
else l=mid+1;
}
if(goal==-1) return;
int y=vec[goal];
to[x].push_back(y),to[y].push_back(x);
vec.erase(vec.begin()+goal);
}
}
void get_edges(int x){
node[0].clear(),node[1].clear();
fill(col,col+x,-1);
for(int i=1;i<x;++i)if(col[i]==-1) dfs(i,0);
calc(node[0],x),calc(node[1],x);
}
void Solve(int n){
for(int i=1;i<=2*n;++i) get_edges(i);
for(int i=1;i<=2*n;++i)if(to[i].size()==3){
for(int j=0;j<3;++j){
vector<int> vec={i};
for(int k=0;k<3;++k)if(k!=j)
vec.push_back(to[i][k]);
if(Query(vec)==1) {L[i]=to[i][j]; break;}
}
}
for(int i=1;i<=2*n;++i){
if(to[i].size()==1){
if(!vis[i] and !vis[to[i][0]])
Answer(i,to[i][0]),vis[i]=vis[to[i][0]]=1;
continue;
}
for(int j=0;j<3;++j){
if(L[i]==to[i][j] or L[to[i][j]]==i) continue;
if(!vis[i] and !vis[to[i][j]])
Answer(i,to[i][j]),vis[i]=vis[to[i][j]]=1;
}
}
}