http://codeforces.com/contest/1470

D. Strange Housing

题意：给定一张无向图，要求对一些点染色，再保留包含染色点的边，满足新图包含所有原图上的点且连通，且新图上每条边恰有一个染色点。

生成树

先求出任意一个生成树，dfs，如果与它相邻的点没有被染色的，则染它。

显然这样不会有边两端点都染色。再证明必定包含所有点且联通。

假设不连通，有两个连通块，则生成树必定有一条边的两个端点都未染色。设为 u,v,fa[v]=uu,v,fa[v]=u，uu 由于某种原因未染色，当dfs到 vv 时，不染 vv 必定是因为之前被dfs过的点中存在 被染色且与 vv 在原图上相连的点，而这个点必定是 vv 的子树外的点，所以 vv 的子树必定已经与其它点连通了。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n, m;
int par[N];
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
int find(int i) { return par[i] == i ? i : par[i] = find(par[i]); }
void unit(int x, int y) { par[find(x)] = find(y); }
vector<int>G[N], g[N];
bool ck() {
	for (int i = 2; i <= n; i++)if (find(i) != find(1))return false;
	return true;
}
int vis[N];
vector<int>vc;
void dfs(int u, int _fa) {
	if (!vis[u]) {
		vc.push_back(u);
		for (int v : g[u])vis[v] = 1;
	}
	for (int v : G[u]) {
		if (v != _fa)dfs(v, u);
	}
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		init(n);
		for (int i = 1; i <= n; i++)G[i].clear(), vis[i] = 0, g[i].clear();
		for (int i = 1; i <= m; i++) {
			int u, v;
			scanf("%d%d", &u, &v);
			g[u].push_back(v);
			g[v].push_back(u);
			if (find(u) != find(v)) {
				unit(u, v);
				G[u].push_back(v);
				G[v].push_back(u);
			}
		}
		if (!ck()) { puts("NO"); continue; }
		vc.clear();
		dfs(1, 0);
		puts("YES");
		printf("%d\n", (int)vc.size());
		for (int u : vc)printf("%d ", u);
		puts("");
	}
	return 0;
}

 

C. Strange Shuffle

 

题意：交互题。有 nn 个人排成环形，初始每人有 kk 点，每轮每个人给左边的人 ⌊ai2⌋\lfloor \frac{a_i}{2}\rfloor，给右边的人 ⌈ai2⌉\lceil \frac{a_i}{2}\rceil，aia_i 为这个人现在有的点数。这 nn 个人中有一个内鬼，他会给左边的人 00，给右边的人 aia_i。要求用不超过 10001000 次询问，每次问一个人当前的点数，每次询问后即过一轮，要找出内鬼。

思维

打表发现，内鬼始终等于 kk，内鬼左侧第 ii 轮有 ii 个人小于 kk，右侧第 ii 轮有 ii 个人大于 kk。

从任意一点开始，第 ii 轮向右跳 ii 个人，询问，若 大于或小于 kk，则再向左或向右逐个询问，直到找到等于 kk 的位置就是内鬼。

每次跳 ii 个人保证了在 n\sqrt{n} 步内一定能找到大于或小于 kk 的位置，再由于每轮大于或小于 kk 的人数只加 1，所以在 n\sqrt{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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, k;
int ask(int p) {
	cout << "? " << p << endl;
	int x;
	cin >> x;
	return x;
}
int main() {
	cin >> n >> k;
	int p = 1;
	for (int i = 0; i < 500; i++) {
		p = (p - 1 + i) % n + 1;
		int x = ask(p);
		if (x > k) {
			while (1) {
				p = (p - 1 - 1 + n) % n + 1;
				if (ask(p) == k) {
					cout << "! " << p << endl;
					return 0;
				}
			}
		}
		else if (x < k) {
			p = (p - 1 + 1) % n + 1;
			if (ask(p) == k) {
				cout << "! " << p << endl;
				return 0;
			}
		}
	}
	cout << "! " << p << endl;
	return 0;
}