QOJ 4218. Hidden Graph

link

第一次遇到这个套路，不看题解真看不懂这个条件是干什么用的 /ll。

这个条件能转化为原图存在 \(k+1\) 染色的方案。

初始 \(1\) 个点子图必定存在 \(k+1\) 染色。考虑 \(i\) 个点的导出子图，找到其中 \(d\le k\) 的点 \(u\)，则除去点 \(u\) 的 \(i-1\) 个点的子图存在 \(k+1\) 染色方案，而因为 \(d_u\le k\)，则 \(u\) 必定能染成 \(k+1\) 中一种。而这个过程意味着每次从图中找到 \(d\le k\) 的点删去，能将所有点删去，故整个图的边数上界为 \(nk\)。

有了这个条件，每次找出其中一种颜色的集合，每个点向每种颜色的集合询问直到不存在边，询问到 \((-1,-1)\) 有 \(k+1\) 次，总共有 \(n(k+1)\)，其他情况每种边只会被询问一次，均摊 \(nk\)，故询问次数 \(n(k+1)+nk=2nk+n\) 刚好足够。

Takanashi Rikka

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define intz(x,a) memset(x,a,sizeof(x))
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=2005;
int cnt,k,n;
set<int>p;bool fl[N][N];
vector<pii>ans;
inline pii ask(auto s){
	cout<<"? "<<s.size()<<' ';
	for(int i:s)cout<<i<<' ';cout<<endl;
	int x,y;cin>>x>>y;
	if(x!=-1)fl[x][y]=fl[y][x]=1,ans.pb(mp(x,y));
	return mp(x,y);
}
void color(set<int>p){
//	for(int i:p)cerr<<i<<' ';cerr<<'\n';
	if(!p.size())return;
	set<int>res,w;int u;
	res.insert(u=*p.begin());
	for(int i:p)if(i^u){
		res.insert(i);
		if(ask(res)!=mp(-1,-1))
			res.erase(i),w.insert(i);
	}
	for(int i:w){
		set<int>l;l.insert(i);
		for(int j:res)
			if(!fl[i][j])l.insert(j);pii x;
		while(l.size()>1&&(x=ask(l))!=mp(-1,-1))
			l.erase(x.fi==i?x.se:x.fi);
	}
	color(w);
}
void UesugiErii(){
	cin>>n;
	for(int i=1;i<=n;i++)p.insert(i);
	color(p);
	cout<<"! "<<ans.size()<<'\n';
	for(pii i:ans)cout<<i.fi<<' '<<i.se<<'\n';
}
signed main(){
	cfast;
	int _=1;//cin>>_;
	for(;_;_--)UesugiErii();
	return 0;
}