https://codeforces.com/contest/1187

C. Vasya And Array

 

题意：有一个数组，已知某几个区间非递减，某几个不是非递减，要求构造出这个数组。

构造

要尽可能地构造出尽量多的不是非递减的区间，所以在满足非递减区间的基础上，其它都安排为递减。

设vis[i]表示第i位大于等于第i-1位，则所有已知非递减的区间除左端点外都vis=1.

从前往后遍历，遇到vis=1的就设置该位等于前一位，否则等于前一位-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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, m;
typedef pair<int, int>pii;
vector<pii>vc;
int vis[N], a[N];
int main() {
	scanf("%d%d", &n, &m);
	while (m--) {
		int t, l, r;
		scanf("%d%d%d", &t, &l, &r);
		if (t) {
			for (int i = l + 1; i <= r; i++)vis[i] = 1;
		}
		else {
			vc.push_back(pii(l, r));
		}
	}
	a[1] = n;
	for (int i = 2; i <= n; i++) {
		if (vis[i])a[i] = a[i - 1];
		else a[i] = a[i - 1] - 1;
	}
	for (pii p : vc) {
		if (a[p.first] == a[p.second]) { puts("NO"); return 0; }
	}
	puts("YES");
	for (int i = 1; i <= n; i++)printf("%d%s", a[i], i == n ? "\n" : " ");
	return 0;
}

 

D. Subarray Sorting

 

题意：给定两个数列，要求操作第一个数列得到第二个数列，每次操作选一个区间从小到大排序。

线段树

显然是可以相当于选两个数交换位置。所以和冒泡排序有些类似。

从前往后安排每一位，仅当前面所有没有移动过的位都比当前位大时，当前位才可以移动到指定位置。

线段树维护a数组的最小值，遍历b的每一位，先确定要把a中哪个移到b的位置，然后判断a中第1位到该位的最小值是否位b中这一位。每安排好一位，就把a中该位变为INF。

由于从前往后安排，所以a中必定是只会只会有从后往前移动（类似冒泡），并且一定要跨过原a中所有前面的位，所以只要每次都查询前缀的最小值即可。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 3e5 + 10;
int T;
int n;
int a[N], b[N];
vector<int>s[N], t[N];
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int mn[N << 2];
void up(int rt) {
	mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
	if (l == r) {
		mn[rt] = a[l];
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
void cg(int q, int x, int l, int r, int rt) {
	if (l == r) {
		mn[rt] = x;
		return;
	}
	if (q <= mid)cg(q, x, lson);
	else cg(q, x, rson);
	up(rt);
}
int qry(int ql, int qr, int l, int r, int rt) {
	if (ql <= l && qr >= r)return mn[rt];
	int ans = INF;
	if (ql <= mid)ans = min(ans, qry(ql, qr, lson));
	if (qr > mid)ans = min(ans, qry(ql, qr, rson));
	return ans;
}
int r[N];
bool ck() {
	for (int i = 1; i <= n; i++) {
		if (s[i].size() != t[i].size())return false;
		for (int j = 0; j < (int)s[i].size(); j++) {
			r[t[i][j]] = s[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		if (qry(1, r[i], 1, n, 1) != b[i])return false;
		cg(r[i], INF, 1, n, 1);
	}
	return true;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)s[i].clear(), t[i].clear();
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			s[a[i]].push_back(i);
		}
		for (int i = 1; i <= n; i++) {
			scanf("%d", &b[i]);
			t[b[i]].push_back(i);
		}
		build(1, n, 1);
		if (!ck())puts("NO");
		else puts("YES");
	}
	return 0;
}

 

E. Tree Painting

 

题意：给定一棵树，每次选择一个节点变为黑色，并获得该结点所在白色联通块大小的奖励。直到所有点都变为黑丝。要求奖励最多。

换根dp

在确定第一个点的情况下，方案也就确定了，一定是从该点出发向外bfs。

所以把第一个点看作根，枚举根，比较作为根时的奖励。

转移方程为 dp[v]=dp[u]+n−2∗size[v]dp[v]=dp[u]+n-2*size[v]，size[v]size[v] 为 1 作根时v的子树大小。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n;
vector<int>G[N];
ll dp[N], ans;
int sz[N];
void dfs(int u, int _fa) {
	sz[u] = 1;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
}
void dfs2(int u, int _fa) {
	for (int v : G[u]) {
		if (v == _fa)continue;
		dp[v] = dp[u] + n - 2 * sz[v];
		dfs2(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);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++)dp[1] += sz[i];
	dfs2(1, 0);
	for (int i = 1; i <= n; i++)ans = max(ans, dp[i]);
	printf("%lld\n", ans);
	return 0;
}