Codeforces Round #800 (Div. 2)

最近做需求太无聊了，7、8 双月如果不太忙的话，codeforces冲波分，补一下最近div2的题找找状态

A、Creep

题意
给你n个0和m个1，构造一个字符串，定义字符串的价值为它的所有前缀字符串中0的数量和1的数量的差值的最大值，构造价值最小的串
做法
可以发现最最小价值就是二者数量的差值，交叉防止0和1即可

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main() {
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, m;
		sc("%d%d", &n, &m);
		if (n < m) {
			for (int i = 0; i < n; i++)
				pr("01");
			for (int i = n; i < m; i++)
				pr("1");
		}
		else
		{
			for (int i = 0; i < m; i++)
				pr("01");
			for (int i = m; i < n; i++)
				pr("0");
		}
		pr("\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

B、Paranoid String

题意
给你一个长度为n的字符串，每次操作你可以将其中的01变成1，10变成0，对于这个字符串的所有子串，在不限制操作次数的前提下，可以将多少个子串的长度变成1
做法
对于一个字符串而言，若干次操作后，只会保留同一个字母的后缀，那么我们只需要确保最后两位是不同的，那么前缀无论如果都可以消除

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[200005];
int main() {
	int T;
	sc("%d", &T);
	while (T--)
	{
		int len;
		sc("%d%s", &len, s + 1);
		ll ans = 0, pre0 = 0, pre1 = 0;
		for (int i = 1; i <= len; i++) {
			if (i == 1 || s[i] != s[i - 1]) {
				ans += i;
			}
			else
				ans++;
		}
		pr("%lld\n", ans);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

C、Directional Increase

题意
有一个长度为n的数组，初始值都为0，有一个指针位于第一个元素上，有两种操作

1. 如果指针不在最后一个元素上，那么将指针所在位置的值加1，然后将指针移动到后下一个元素上
2. 如果指针不在第一个元素上，那么将指针所在位置的值减1，然后将指针移动到前一个元素上

最后，指针必须仍然位于第一个元素上
给你一个长度为n的数组a，问能否通过一些操作将初始值都为0的数字变成数组a

做法

1. 由于最终指针需要位于第一个元素上，所以指针向前移动的距离和向后移动的距离是相等的，即数组a的总和等于0。
2. 并且我们可以将所有移动拆分为若干个子段，即从$a_i$到达$b_i$（$a_i$<$b_i$），再从$b_i$到达$a_i$，本质上是$a_i$增加1，$b_i$减少1，那么对于可以到达的数组了来说是不会出现前缀和<0的情况
3. 通过样例4可以发现，当前缀已经存在和为0的情况，是无法再对后续的数字进行更新的，因此特判前缀和等于0的时候，后续不能再进行更新即可

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll a[200005];
int main() {
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n;
		sc("%d", &n);
		ll pre = 0;
		for (int i = 1; i <= n; i++)
			sc("%lld", &a[i]);
		for (int i = 1; i <= n; i++)
		{
			pre += a[i];
			if (pre < 0) {
				pr("NO\n");
				goto qwe;
			}
			if (pre == 0) {
				for (int j = i + 1; j <= n; j++) {
					if (a[j] != 0) {
						pr("NO\n");
						goto qwe;
					}
				}
				pr("YES\n");
				goto qwe;
			}
		}
		if (pre == 0)
			pr("YES\n");
		else
			pr("NO\n");
	qwe:;
	}
}
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

D、Fake Plastic Trees

题意
有一颗根节点为1的树，初始时每个节点的值都是0，每次操作可以选择以1号节点开始的链（假设链上的节点为$b_1,b_2,...,b_k$），并且为链上的节点的值增加$c_1,c_2,...,c_k$（其中数组C需要满足$0\le c_1\le c_2\le ...\le c_k$），要求最终每个节点 $i$ 的值需要满足 $l_i\le a_i\le r_i$

问至少需要进行多少次操作可以让所有节点的值都满足上述条件

做法

1. 由于每次选择一条链，并且子节点需要大于等于父节点，那么每个叶子节点都需要进行一次操作，并且对于每一个需要进行操作的节点来说，选择最大的 $r_i$ 一定不劣
2. 之后对于每个节点，它的所有子节点的价值总和就是该节点能够不借助操作到达的最大值
3. 如果该节点不借助操作能到达的最大值任然小于该节点期望的最小值$l_i$，那么对这个节点进行一次操作，并将该节点的价值设为$r_i$即可
4. 反之，则取该节点不借助操作能到达的最大值和该节点的上限$r_i$取最小值作为该节点的价值，此时无需额外贡献

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int fa[200005];
int in[200005];
ll val[200005];
ll l[200005];
ll r[200005];
int main() {
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n;
		sc("%d", &n);
		for (int i = 1; i <= n; i++)
			val[i] = 0;
		for (int i = 2; i <= n; i++) {
			int t = 0;
			sc("%d", &t);
			fa[i] = t;
			in[t]++;
		}
		for (int i = 1; i <= n; i++)
			sc("%lld%lld", &l[i], &r[i]);
		ll ans = 0;
		queue<int>q;
		for (int i = 1; i <= n; i++)
			if (in[i] == 0) {
				ans++;
				val[i] = r[i];
				q.push(i);
			}
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			val[fa[u]] += val[u];
			in[fa[u]]--;
			if (in[fa[u]] == 0) {
				if (val[fa[u]] < l[fa[u]]) {
					ans++;
					val[fa[u]] = r[fa[u]];
				}
				else {
					val[fa[u]] = min(r[fa[u]], val[fa[u]]);
				}
				q.push(fa[u]);
			}
		}
		pr("%lld\n", ans);
	}
}
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

E、Keshi in Search of AmShZ

题意
给你n个点，m条边的有向图，你需要从1号节点走到n号节点，每次操作你可以选择删掉一条路，或者随机选择一条路并通过这条路到达下一个节点，求确保你能到达n号节点的最小操作数量
保证至少存在一条道路从1号节点出发，并到达n号节点
做法

1. 题目要求确保能到达n号节点的最小操作数量，那么我们需要确保你每次的选择都是最差的
2. 那么对于每个分叉点，假设我们知道每个分叉点确保到达终点的最小操作次数，那么当我们到达其中一个分叉点的前提是，删除了其他操作次数大于该分叉点的点
3. 那么我们可以考虑反向建边，在跑dij的同时，可以确保每次用到的分叉点都是还没有用过的分叉点中最小操作数量的点，在遍历到这个分叉点是，将对应点的可选边数减一即可
4. 如果存在两个分叉点的最小操作数量一样，根据遍历顺序的不同，其中一条边的操作次数是1，另一条边的操作次数是2，按照之前的定义，这里两条边的操作次数应该都是1，按照这种操作会额外增加$O(logn)$的复杂度。但是由于这里只要保证操作次数是1的价值能够转移过来即可，操作次数为2的边一定不会更优

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
struct edge {
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init() {
	memset(head, -1, sizeof head);
	tot = 1;
}
void add(int a, int b) {
	e[tot] = { b,head[a] };
	head[a] = tot++;
}
ll dis[MAXN];
ll cnt[MAXN];
bool vis[MAXN];
#define Pair pair<ll, int>
int main() {
	init();
	int n, m;
	sc("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		dis[i] = 1e18;
	while (m--) {
		int a, b;
		sc("%d%d", &a, &b);
		add(b, a);
		cnt[a]++;
	}
	auto dij = [&](int st) {
		priority_queue<Pair, vector<Pair>, greater<Pair>>q;
		q.push(Pair{ 0,st });
		dis[st] = 0;
		while (!q.empty()) {
			int u = q.top().second;
			q.pop();
			if (vis[u])
				continue;
			vis[u] = true;
			for (int i = head[u]; i + 1; i = e[i].nex) {
				int to = e[i].to;
				dis[to] = min(dis[to], dis[u] + cnt[to]);
				q.push(Pair{ dis[to], to });
				cnt[to]--;
			}
		}
	};
	dij(n);
	pr("%lld\n", dis[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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56