Educational Codeforces Round 162 Div 2

发表于 更新于 分类于

比赛忘记打了，只能赛后补题了（悲

D. Slimes

推导一下条件：

  1. 必须严格大的吃严格小的\(\rightarrow\)相同的不能吃\(\rightarrow\)至少要两个不同的数才能一路吃成一个数
  2. 要求最小步数\(\rightarrow\)一个数左右相邻的一串数被吃成一个后，再吃掉这个数本身。

第一步判断不同的数可以\(O(n)\)预处理出上一个不同的数位置，2可以通过在前缀和上二分算出。要特判一下相邻的数直接吃的情况。

总复杂度\(O(nlogn)\)​。

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
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
void work()
{
	cin >> n;
	vector<int> a(n), ans(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++)
		ans[i] = inf;
	auto check = [&](bool rev)
	{
		vector<ll> sum(n), pre(n);
		for (int i = 0; i < n; i++)
			sum[i] = i > 0 ? sum[i - 1] + a[i]
						   : a[i];
		pre[n - 1] = inf;
		for (int i = n - 2; i >= 0; i--)
			pre[i] = a[i] == a[i + 1] ? pre[i + 1]
									  : i + 1;
		for (int i = n - 2; i >= 0; i--)
		{
			
			int it = upper_bound(sum.begin(), sum.end(), sum[i] + a[i]) - sum.begin();
			int ans1, ans2;
			ans1 = (it == n) ? inf : it - i;
			ans2 = pre[i + 1] - i;
			int realID = rev ? (n - i - 1) : i;
			ans[realID] = min(ans[realID], max(ans1, ans2)); 
		}
	};
	for (int i = 0; i < n; i++)
		if ((i > 0 && a[i - 1] > a[i]) || (i < n - 1 && a[i + 1] > a[i]))
			ans[i] = 1;
	check(false);
	reverse(a.begin(), a.end());
	check(true);
	for (auto x : ans)
		cout << (x > (int)3e5 ? -1 : x) << ' ';
	cout << '\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E. Count Paths

可以发现，路径可以分为两种：

  1. 祖先与子孙的
  2. 没有祖孙关系的

同时，当祖先的颜色与子孙相同时，会挡住子孙与上面的通路，也就是贡献被清零了。

考虑直接启发式合并，用n个std::map来维护以某个节点为根子树每种颜色的贡献，直接合并计算即可。

时间复杂度\(O(nlogn)\)，注意多组数据的清空。

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
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
map<int, int> mp[N];
vector<int> son[N];
int col[N];
ll ans = 0;
void dfs(int x, int f)
{
	mp[x][col[x]]++;
	for (auto y : son[x])
	{
		if (y == f)
			continue;
		dfs(y, x);
		if (mp[y].contains(col[x]))
		{
			ans += mp[y][col[x]];
			mp[y].erase(col[x]);
		}
		if (mp[y].size() > mp[x].size())
			swap(mp[x], mp[y]);
		for (auto [key, val] : mp[y])
		{
			if (mp[x].contains(key))
				ans += 1LL * val * mp[x][key];
			mp[x][key] += val;
		}
	}
}
void work()
{
	cin >> n;
	// clear
	for (int i = 1; i <= n; i++)
	{
		mp[i].clear();
		son[i].clear();
	}
	ans = 0;
	
	
	
	for (int i = 1; i <= n; i++)
		cin >> col[i];
	for (int i = 1; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		son[x].emplace_back(y);
		son[y].emplace_back(x);
	}
	dfs(1, 0);
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}