变色龙之恋[JOISC 2020 Day2]

发表于 分类于

题目链接

链接

题解

刚开始觉得似乎无从下手。

那就从最简单的开始搞吧。假设我现在只询问两只变色龙。

那么这个询问的答案只能是 $1$ 或者 $2$。

当且仅当 $x,y$ 颜色相同，或只有某个喜欢另一个时答案为 $1$。也就是说， 若 $x$ 和其他点都询问一次，答案为 $1$ 则向这个点连一条边，则 $x$ 只会连出去 $1$ 或 $3$ 条边。

当只连出去 $1$ 条边的时候，这条边所对应的点就是原色相同的点啦。

当连出去 $3$ 条边的时候，假设是 $y_1,y_2,y_3$。我们询问 $(x,y_i,y_j)$，那么 $y_i$ 当且仅当喜欢 $x$，$y_j$ 和 $x$ 同颜色的时候答案为 $1$。然后我们可以把这两条边都标记一次。对于每个点都这样做，最后被标记 $2$ 次的边所连接的两个点就是同色的了。

现在得到了一个询问次数 $O(n^2)$ 的做法。

考虑这个算法的瓶颈在于第一部分，即查询每个点 $x$ 与其相连的所有 $y$。

考虑优化这一部分。

这个图是一个二分图，试试用一下这个性质？

假设你已经知道了所有点属于二分图的哪个集合。

考虑对于一个独立集 $A$ 询问的结果，这个答案一定等于 $|A|$。否则这个答案一定不为 $|A|$。

那也就是说明对于一个点 $x$，和一个独立集，可以判断点 $x$ 是否和独立集有边相连了。

那么可以二分处理即可。

但是我们不知道所有点属于二分图的哪个集合哇？也就是说不能直接来，因为不满足询问的点是独立集这个条件。

那么边做边黑白染色就好了。

询问次数 $O(n\log n)$，常数有点小大。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
#include "chameleon.h"
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const int N=1005;
int n,m,ans[N][N];
vector<int> Q,w[2],v[N];
int now,t;
int fa[N]; bool c[N];
bool col(int x){return x==fa[x]?0:c[x]^col(fa[x]);}
int find(int x){return x==fa[x]?x:find(fa[x]);}
inline void merge(int x,int y)
{
	c[find(x)]=1^col(x)^col(y);
	fa[find(x)]=find(y);
}
bool dfs(int l,int r,bool opt)
{
	if(v[now].size()>=3) return 0;
	if(l>r) return 0;
	if(!opt)
	{
		Q.clear(),Q.pb(now); fo(k,l,r) Q.pb(w[t][k]);
		if(Query(Q)>r-l+1) return 0;
	}
	if(l==r)
	{
		v[now].pb(w[t][l]);
		v[w[t][l]].pb(now);
		merge(now,w[t][l]);
		return 1;
	}
	int mid=l+r>>1;
	if(rand()&1)
	{
		opt=dfs(l,mid,0);
		dfs(mid+1,r,!opt);
	}
	else
	{
		opt=dfs(mid+1,r,0);
		dfs(l,mid,!opt);
	}
	return 1;
}
int id[N];
void Solve(int n)
{
	m=2*n;
	fo(i,1,m) fa[i]=i;

	srand(20030227);
	fo(i,1,m) id[i]=i;
	fo(i,1,m) swap(id[i],id[rand()%m+1]);
	//fo(i,1,m) cerr<<id[i]<<endl;
	fo(tim,1,m)
	{
		int i=id[tim];
		fo(k,0,1) w[k].clear();
		fo(j,1,tim-1) w[col(id[j])].pb(id[j]);
		fo(k,0,1) t=k,now=i,dfs(0,w[k].size()-1,0);
	}
	fo(i,1,m)
		if(v[i].size()==1)
			ans[i][v[i][0]]=ans[v[i][0]][i]=2;
		else
		{
			bool flag=0;
			fo(j,0,2)
				fo(k,j+1,2)
				{
					if(flag) continue;
					Q.clear(),Q.pb(i),Q.pb(v[i][j]),Q.pb(v[i][k]);
					if(Query(Q)==1)
					{
						ans[i][v[i][j]]++,ans[v[i][j]][i]++,
						ans[i][v[i][k]]++,ans[v[i][k]][i]++;
						flag=1;
					}
				}
		}
	fo(i,1,m) fo(j,i+1,m) if(ans[i][j]>=2) Answer(i,j);
}