专栏文章

题解：CF1033E Hidden Bipartite Graph

00000pnchexagon
CF1033E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miow8dmt
此快照首次捕获于
2025/12/03 02:10
3 个月前
此快照最后确认于
2025/12/03 02:10
3 个月前
查看原文
先考虑找一个生成树。维护两个集合 S={1},T={2,3,4,⋯ ,n}S=\{1\},T=\{2,3,4,\cdots,n\}，然后考虑每次找一条 SS 里的点向 TT 里点的连边。对于这个可以先二分出 TT 里哪个点（设为 xx）与 SS 里有连边，然后再二分是 SS 里的哪个点 yy 与 xx 有连边。这样可以用 2log⁡∣S∣+2log⁡∣T∣2\log |S|+2\log |T| 的次数得到一条 SS 向 TT 连的边。之后我们把 xx 加到 SS 里，从 TT 里删掉，然后连一条边 (x,y)(x,y)。
得到生成树之后直接黑白染色就可以得到这个图的两部分，然后判断原图是不是二分图可以直接询问两个部分自己里面有没有连边。如果两部分都没连边说明确实是二分图。
如果有连边，不妨设有连边的是左部点 LL，那我们可以通过类似 APIO 2025 T1 的手段在 O(log⁡∣L∣)O(\log |L|) 的时间里找到这条边。具体的，把 LL 平均分成两部分，然后询问两部分里面有没有边，如果其中一部分有边就直接递归，否则一定是两部分点之间的连边，直接套用上面的方法就行了。
找到这条边之后，相当于是往生成树上加了一条边，这一定会形成一个奇环，于是只需要找树上这两个点之间的路径输出即可。
总的询问次数是 4nlog⁡n4n\log n，比较极限。注意写代码的时候如果你只询问一个点的话可以直接跳过，可以省下不少询问次数。
代码：
CPP
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second

int n, cc, col[605], vis[605], nxt[605];
vector<int> g[605], S, T, lc, rc;

int qry(vector<int> vec) {
	int sz = (int)vec.size();
	if (sz <= 1) return 0; 
	cout << "? " << sz << endl;
	for (int i = 0; i < sz; i++) cout << vec[i] << " ";
	cout << endl;
	int x; cin >> x; return x;
}

pii link(vector<int> l, vector<int> r) {
	int L = 0, R = (int)l.size() - 1, cr = qry(r);
	vector<int> res = r, tmp;
	while (L != R) {
		int mid = (L + R) >> 1;
		for (int i = L; i <= mid; i++) res.push_back(l[i]), tmp.push_back(l[i]);
		int tot = qry(res), cl = qry(tmp);
		for (int i = L; i <= mid; i++) res.pop_back(), tmp.pop_back();
		if (tot == cl + cr) L = mid + 1;
		else R = mid;
	}
	cr = l[L], L = 0, R = (int)r.size() - 1, res = {cr};
	while (L != R) {
		int mid = (L + R) >> 1;
		for (int i = L; i <= mid; i++) res.push_back(r[i]), tmp.push_back(r[i]);
		int tot = qry(res), cl = qry(tmp);
		for (int i = L; i <= mid; i++) res.pop_back(), tmp.pop_back();
		if (tot == cl) L = mid + 1;
		else R = mid;
	}
	return {cr, r[L]};
}

pii find(vector<int> vc) {
	if (vc.size() == 2) return {vc[0], vc[1]};
	int mid = ((int)vc.size() - 1) >> 1;
	vector<int> vl, vr;
	for (int i = 0; i <= mid; i++) vl.push_back(vc[i]);
	if (qry(vl)) return find(vl);
	for (int i = mid + 1; i < (int)vc.size(); i++) vr.push_back(vc[i]);
	if (qry(vr)) return find(vr);
	return link(vl, vr);
}

bool dfs(int u, int f, int rt) {
	if (u == rt) return true;
	bool flg = false;
	for (int v : g[u]) if (v != f) {
		if (dfs(v, u, rt)) flg = true, nxt[u] = v;
	}
	cc += flg;
	return flg;
}

int main() {
	cin >> n;
	S.push_back(1), lc.push_back(1); for (int i = 2; i <= n; i++) T.push_back(i);
	while ((int)S.size() != n) {
		pii p = link(S, T);
		T.erase(find(T.begin(), T.end(), p.se)), S.push_back(p.se);
		g[p.fi].push_back(p.se), g[p.se].push_back(p.fi);
		col[p.se] = col[p.fi] ^ 1;
		if (col[p.se]) rc.push_back(p.se);
		else lc.push_back(p.se);
	}
	int cl = qry(lc), cr = qry(rc);
	if (!cl && !cr) {
		cout << "Y " << lc.size() << endl;
		for (int i : lc) cout << i << " ";
		return cout << endl, 0;
	}
	if (!cl) swap(lc, rc);
	pii p = find(lc); dfs(p.fi, 0, p.se);
	cout << "N " << cc + 1 << endl;
	for (int i = p.fi; i != p.se; i = nxt[i]) cout << i << " ";
	return cout << p.se << endl, 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...