http://codeforces.com/contest/1508

A. Binary Literature

 

题意：给定三个 2n 长度的01串，要求构造一个长度不超过 3n 的01串，是的给定的三个串中至少有两个是构造出的串的子序列。

构造

假设有两个串都满足：0的个数大于等于1的个数，那么0的个数一定大于等于n。则先选其中一个一个串，再把另一个串插入其中，必定满足需要插入的次数小于等于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
#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 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n;
char s[3][N], ans[N];
int c[3];
void sol(int x, int y, char cc) {
	int p1 = 0, p2 = 0, cnt = 0, n = strlen(s[x]), m = 0;
	while (p1 < n || p2 < n) {
		if (p1 >= n) {
			ans[m++] = s[y][p2++];
			continue;
		}
		if (p2 >= n) {
			ans[m++] = s[x][p1++];
			continue;
		}
		if (s[x][p1] == s[y][p2]) {
			ans[m++] = s[x][p1];
			p1++; p2++;
		}
		else {
			if (s[x][p1] != cc) {
				ans[m++] = s[x][p1++];
			}
			else {
				ans[m++] = s[y][p2++];
			}
		}
	}
	ans[m] = 0;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		scanf("%s%s%s", s[0], s[1], s[2]);
		for (int i = 0; i < 3; i++) {
			c[i] = 0;
			for (int j = 0; s[i][j]; j++)c[i] += s[i][j] - '0';
		}
		if (c[0] >= n && c[1] >= n)sol(0, 1, '1');
		else if (c[0] >= n && c[2] >= n)sol(0, 2, '1');
		else if (c[1] >= n && c[2] >= n)sol(1, 2, '1');
		else if (c[0] <= n && c[1] <= n)sol(0, 1, '0');
		else if (c[0] <= n && c[2] <= n)sol(0, 2, '0');
		else if (c[1] <= n && c[2] <= n)sol(1, 2, '0');
		printf("%s\n", ans);
	}
	return 0;
}

 

B. Almost Sorted

 

题意：定义“几乎有序”：ai+1≥ai−1a_{i+1}\ge a_i-1。要求给出一个 nn 的排列，满足是第 kk 小的几乎有序排列。

容易发现几乎有序的排列一定是在递增排列的基础上翻转一些不相交的区间。如下图。

所以长度为 nn 的几乎有序排列可以通过枚举段数，并分割得到，所以长度为 nn 的几乎有序数列的个数为 ∑i=1nCn−1i−1\sum\limits_{i=1}^nC_{n-1}^{i-1}，由二项式定理得到等于 2n−12^{n-1}。

所以问题就变成了类似于二进制转化的问题。

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
#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 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
ll n, k;
int a[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%lld%lld", &n, &k);
		if (n <= 60 && k > (1ll << (n - 1))) {
			puts("-1");
			continue;
		}
		for (int i = 1; i <= n; i++)a[i] = i;
		for (int i = 1; i < n; i++) {
			if ((n - i - 1) > 60 || (1ll << (n - i - 1) >= k)) {
				continue;
			}
			else {
				int j = i;
				while (k > (1ll << (n - j - 1)) && j < n) {
					k -= (1ll << (n - j - 1));
					j++;
				}
				reverse(a + i, a + j + 1);
				i = j;
			}
		}
		for (int i = 1; i <= n; i++)printf("%d%c", a[i], " \n"[i == n]);
	}
	return 0;
}

 

C. Complete the MST

 

题意：有一张带权无向完全图，给出了一些边的边权，要求构造为给定边的边权，使得所有边权的异或和为 0，且最小生成树最小，输出最小生成树值。

并查集+dfs+STL

首先容易想到只要未给定边中至少有一条边不在最小生成树里，那么就可以使得最小生成树中的所有未给定边的边权为 0。

如果未给定边构成环，那么一定满足上述情况，而不构成环，则一定有未给定边数是 O(n)O(n) 的。

对于第一种情况：

先dfs求出未给定边组成的图的生成森林，再在此基础上求出整张图的最小生成树。

直接dfs显然是 O(n2)O(n^2) 的，不可行。所以通过维护一个未访问节点的set，每次只遍历连向set中的点的边。复杂度为 O(nlog⁡n)O(n\log n).

对于第二种情况：

未给定边数是 O(n)O(n) 的，给定边数是 O(m)O(m) 的，而总边数是 O(n2)O(n^2)，则给定边数一定是 O(n2)O(n^2) 的，也就是说 nn 一定是 O(m)O(\sqrt{m}) 的。

那么直接暴力枚举一条未给定边的边权等于所有给定边权的异或和，其它未给定边的边权都为 0，此时如果暴力求最小生成树，复杂度为 O(nm)O(nm)，不可行。但是由于最小生成树是贪心地边权从小到大遍历的，所以如果在原图中不是最小生成树中的边，那么在加了一些边之后，必定不会是新图的最小生成树中的边。

所以先求出给定边构成的图的最小生成树，之后用这棵最小生成树代替这张给定边构成的图。

复杂度为 O(n2)=O(m)O(n^2)=O(m).

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
97
98
99
100
#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 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m;
struct E {
	int u, v; ll w;
	bool operator<(const E& b)const {
		return w < b.w;
	}
};
vector<int>G[N];
vector<E>es, tes, tmp, mst;
int par[N];
void init(int n) { for (int i = 1; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void unit(int x, int y) { par[find(x)] = find(y); }
bool same(int x, int y) { return find(x) == find(y); }
set<int>st;
void dfs(int u) {
	st.erase(u);
	for (int i = 0; i < (int)G[u].size() - 1; i++) {
		int x = G[u][i], y = G[u][i + 1], v;
		while (!st.empty() && st.upper_bound(x) != st.end() && (v = (*st.upper_bound(x))) < y) {
			tes.push_back({ u, v, 0 });
			dfs(v);
		}
	}
}
ll sum;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		G[u].push_back(v);
		G[v].push_back(u);
		es.push_back({ u, v, w });
		sum ^= w;
	}
	for (int i = 1; i <= n; i++) {
		G[i].push_back(0);
		G[i].push_back(n + 1);
		sort(G[i].begin(), G[i].end());
	}
	for (int i = 1; i <= n; i++)st.insert(i);
	while (!st.empty())dfs(*st.begin());
	sort(es.begin(), es.end());
	ll ans = 0;
	if ((1ll * n*(n - 1) / 2 - m) >= n) {
		init(n);
		for (E& e : tes) {
			int u = e.u, v = e.v;
			if (!same(u, v))unit(u, v);
		}
		for (E& e : es) {
			int u = e.u, v = e.v;
			if (!same(u, v)) {
				unit(u, v);
				ans += e.w;
			}
		}
		printf("%lld\n", ans);
	}
	else {
		init(n);
		for (E& e : es) {
			if (!same(e.u, e.v)) {
				mst.push_back(e);
				unit(e.u, e.v);
			}
		}
		ll ans = inf;
		for (E& e : tes) {
			tmp.clear();
			e.w = sum;
			tmp.insert(tmp.end(), tes.begin(), tes.end());
			tmp.insert(tmp.end(), mst.begin(), mst.end());
			sort(tmp.begin(), tmp.end());
			ll res = 0;
			init(n);
			for (E& p : tmp) {
				if (!same(p.u, p.v)) {
					unit(p.u, p.v);
					res += p.w;
				}
			}
			ans = min(ans, res);
			e.w = 0;
		}
		printf("%lld\n", ans);
	}
	return 0;
}