牛客小白月赛62题解

发表于 分类于

一言难尽，$BC$ 数学题？不会。$DE$ 树论，可做，但是写复杂了，没de出来，甚至复杂度炸了一个。

A-幼稚园的树

应该有更优的解，不会。

模拟可过，直接签。

复杂度 $O(n \cdot m)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int h[MAXN];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> h[i];
	int a, k, b, m;
	cin >> a >> k >> b >> m;

	for (int i = 1; i <= n; ++i)
	{
		int tmp = m-1;
		while (tmp--)
		{
			h[i] += a;
			if (h[i] > k) h[i] = b;
		}
		cout << h[i] << ' ';
	}
	cout << '\n';
}

B-剩下的数

不会，改天补。

C-数组划分

不会，改天补。

D-子树的大小

“编号从 $0$ 开始”，不认真读题浪费了半小时。以及 LL 没开全，爆了几次。

从结点 $q$ 开始向下走，直到下一层出现叶子结点，即结点不完全。

分两部分处理。

对于以 $q$ 为根节点的子树的最后一层，找到其最左边结点的编号 $l$，以及最右边结点的编号 $r$，易得结点数量为 $r-l+1$。

对于其他层数，结点数量按照 ${1,k,k^2,…}$ 递增。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL n, k, m;
LL calc(LL q) {
	if (k == 1) return n-q;
	LL ans = 0, l = q, r = q;
	while (l < n)
	{
		ans += min(r, n-1)-l+1;
		l = l*k+1;
		r = r*k+k;
	}
	return ans;
}

void solve() {
	cin >> n >> k >> m;
	while (m--)
	{
		LL q;
		cin >> q;
		cout << calc(q) << '\n';
	}
}

E-剖分

初看想写树剖和线段树，然后看了眼比赛 rating 范围，又看了眼数据范围，剖个 der。

考虑线段树的懒标记思维，存储两个信息，某子树根节点的权重变化，根节点到某点的权重变化。

对于第一种信息，用 $tag1[x]$ 存储点 $x$ 及其子树内的权值变化（修改次数）；

对于第二种信息，用 $tag2[x]$ 存储路径终点的权值变化（修改次数）。

考虑子树内或路径内操作，只需 $tag[x]$++

考虑子树外或路径外操作，转换成对整颗树处理 $tag[1]$++ ，再扣去对应子树或路径 $tag[x]$–。

最后将 $tag1$，$tag2$ 中的信息传递并统计即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int tag1[MAXN], tag2[MAXN], cnt[MAXM];
void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int op, x;
		cin >> op >> x;
		if (op == 1) tag1[x]++;
		else if (op == 2) tag1[1]++, tag1[x]--;
		else if (op == 3) tag2[x]++;
		else if (op == 4) tag2[x]--, tag1[1]++;
	}
	for (int i = 1; i <= n; ++i) tag1[i] += tag1[i>>1];
	for (int i = n; i >= 1; --i) tag2[i>>1] += tag2[i];
	for (int i = 1; i <= n; ++i) cnt[tag1[i]+tag2[i]]++;
	for (int i = 0; i <= m; ++i) cout << cnt[i] << ' ';
}

F-子串的子序列

不会，改天补。