https://codeforces.com/contest/1278

B. A and B

 

题意：用正负1到正负n凑出x，每对正负只能且必须选正或负，问最小的n。

观察发现用1到n可以凑出 [(−(1+n)⋅n)/2,(1+n)⋅n/2][(-(1+n)\cdot n)/2,(1+n)\cdot n/2] 的与两端点奇偶性相同的所有数，那就先二分找到，在看如果奇偶性不对，就+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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e8 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int>pii;
int T;
vector<ll>vc;
int main() {
	cin >> T;
	for (int i = 0; i < 100000; i++) {
		vc.push_back(1ll * (1 + i)*i / 2);
	}
	while (T--) {
		ll a, b;
		scanf("%lld%lld", &a, &b);
		if (a == b) { puts("0"); continue; }
		ll x = abs(a - b);
		ll p = lower_bound(vc.begin(), vc.end(), x) - vc.begin();
		while (vc[p] % 2 != x % 2)p++;
		cout << p << endl;
	}
	return 0;
}

 

C. Berry Jam

 

题意：有2n个罐头从中间开始吃，红蓝两种，每次可以吃左边或者右边第一个非空的罐头，要使两种剩余数量相等，问最少操作。

遍历吃到左边的边界，找到对应的右边的位置，比较答案。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int T;
int n, a[N], b[N], c[3];
int sum2[N], sum1[N];
map<int, int>mp;
int main() {
	cin >> T;
	while (T--) {
		scanf("%d", &n);
		mp.clear();
		c[1] = c[2] = 0;
		fill(a, a + 2 * n + 1, 0);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]), c[a[i]]++;
		for (int i = 1; i <= n; i++)scanf("%d", &b[i]), c[b[i]]++;
		reverse(a + 1, a + n + 1);
		mp[0] = 0;
		for (int i = 1; i <= n; i++) {
			sum2[i] = sum2[i - 1] + (b[i] == 1 ? 1 : -1);
			if(!mp.count(sum2[i]))mp[sum2[i]] = i;
			sum1[i] = sum1[i - 1] + (a[i] == 1 ? 1 : -1);

		}
		int nd = c[1] - c[2];
		int ans = INF;
		for (int i = 0; i <= n; i++) {
			if (!mp.count(nd - sum1[i]))continue;
			ans = min(ans, i + mp[nd - sum1[i]]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

D. Segment Tree

 

题意：给定几个区间，连边当且仅当两区间相交（不能包含），问图是否是树。

考虑树的特点：无环，连通，n-1条边。

最后一点是本题关键如果两两连边的话，复杂度是 n2n^2，显然不太行，但是知道了边数最多是 n-1，复杂度就最大是 n 了。

然后就是固定一端排序后，树状数组或set之类的暴力判断相交，连边。一边连边一边判环保证边数小于n。

(1,6),(2,7),(3,8),(4,9),(5,10).

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int>pii;
int n;
int v[N];
pii a[N];
int par[N << 1];
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
void uni(int x, int y) { par[find(x)] = find(y); }
set<pii>st;
int main() {
	scanf("%d", &n);
	init(2 * n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a[i].first, &a[i].second);
	}
	sort(a, a + n);
	for (int i = 0; i < n; i++) {
		while (!st.empty() && (*st.begin()).first <= a[i].first)st.erase(st.begin());
		auto it = st.lower_bound(pii(a[i].second, 0));
		while (it != st.begin()) {
			--it;
			if (find(i) == find((*it).second)) {
				puts("NO");
				return 0;
			}
			uni(i, (*it).second);
		}
		st.insert(pii(a[i].second, i));
	}
	int p = find(0);
	for (int i = 1; i < n; i++)if (find(i) != p) {
		puts("NO");
		return 0;
	}
	puts("YES");
	return 0;
}

 

E. Tests for problem D

 

题意：和D题反过来，给出一棵树，要求构造出符合条件的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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
int n;
int l[N], r[N], tot;
vector<int>G[N];
void dfs(int u, int _fa) {
	for (int v : G[u]) {
		if (v == _fa)continue;
		l[v] = ++tot;
	}
	r[u] = ++tot;
	for (int i = (int)G[u].size() - 1; i >= 0; i--) {
		int v = G[u][i];
		if (v == _fa)continue;
		dfs(v, u);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	l[1] = ++tot;
	dfs(1, 0);
	for (int i = 1; i <= n; i++)printf("%d %d\n", l[i], r[i]);
	return 0;
}