[数据结构与算法]Educational Codeforces Round 127 (Rated for Div. 2) A~E 题解

A. String Building

题意：

问是否可以用 $aa、aaa、bb、bbb$ 拼成所给字符串。

思路：

将原字符串分成连续的 $a、b$ 构成的子串，看是否有长度为 $1$ 的即可。

时间复杂度：$O（n）$

signed main() {
	cf{
		string res;
		cin >> res;
		int a = 0, b = 0;
		bool st = true;
 
		for (auto i : res)
			if (i == 'a') {
				a++;
				if (b == 1) {
					st = false;
					break;
				} else
					b = 0;
			} else if (i == 'b') {
				b++;
				if (a == 1) {
					st = false;
					break;
				} else
					a = 0;
			}
		if (a == 1 || b == 1)
			st = false;
		if (st)
			puts("YES");
		else
			puts("NO");
	}
	return 0;
}

B. Consecutive Points Segment

题意：

给出一连串严格递增的正整数点，每个点都可以选择向左或右移动一格，又或是保持原位置。
问是否可以将其构造为长度为n的连续序列（$s[i+1]?s[i]==1，1\le i<n$）。

思路：

一道思维题，亦或是分类讨论。
将原序列中的 $n?1$ 个间隔长度单独拿出来：

• 如果其中最大长度 $>3$ ，那么必定不可能，因为左右两个点是无法相邻的；
• 如果其中最大长度 $==3$ ，那么有且只能有一个，并且不能够存在长度 $==2$ 的间隔，因为为了让长度 $==3$ 的左右两个点相邻，所有点都必须靠近这里，也就是说这 $n$ 个点都必须操作。这样一来，那么长度 $==2$ 的间隔也就相应无法填补；
• 如果其中最大长度 $==2$ ，那么最多只能有两个，也就是中间那一段不动，左右两边向中间靠近。加入存在三个长度 $==2$ 的间隔，那么原序列就会被分为 $4$ 段，根本不可能合并。

时间复杂度：$O（n）$

int n;
int s[N];
signed main() {
	cf{
		sf(n);
		for (int i = 1; i <= n; i++)
			sf(s[i]);
 
		int a = 0, b = 0;
		bool st = true;
		for (int i = 1; i < n; i++)
			if (s[i + 1] - s[i] == 2)
				a++;
			else if (s[i + 1] - s[i] == 3)
				b++;
			else if (s[i + 1] - s[i] > 3)
				st = false;
 
		if (b > 1)
			st = false;
		else if (b == 1 && a)
			st = false;
		else if (a > 2)
			st = false;
 
		if (!st)
			puts("NO");
		else
			puts("YES");
 
	}
	return 0;
}

C. Dolce Vita

题意：

有 $n$ 家商店，每家商店每天都会卖一包糖，但是所有的商店每天价格都会比昨天 $+1$ ；而你每天都会有数量为 $m$ 的金钱。，问最终最多能够买多少包糖。

思路：

一道明显的贪心。因为所有商店的涨价速度相同，我们每天肯定要把最便宜的商店尽可能买爆，那么思路就是遍历 $n$ 家商店，求出每家商店在每天都将比它便宜的商店买完并且有余钱的情况下，最多能够买多少天。

但是，直接算的时间复杂度是 $O(n^2)$ ，毫无疑问会 $T$，我们需要在遍历到第 $i$ 家商店时，可以将所有比它便宜的商店带来的影响消除。
因为涨价幅度一样，那么尝试着将其进行统一计算，那么剩余的影响就只有原价了。理论成立，尝试推式子。
设第 $i$ 家店的商品初始价值为 $s[i]$ ，最多买 $j$ 天：$$m\ge \sum _{k=1}^{i}s[i]+(j?1)?i$$这样就能 $O(n)$ 内算出结果。

时间复杂度：$O（n）$

int n, m;
int s[N];
signed main() {
	cf{
		sf2(n, m);
		for (int i = 1; i <= n; i++)
			sf(s[i]), s[i]--;//这里为了计算j方便
			
		sort(s + 1, s + 1 + n);
		int res = 0;
		for (int i = 1; i <= n; i++) {
			if (m < s[i] + 1)
				break;
			int j = (m - s[i]) / i;
			res += j;
			m -= s[i];
		}
		pfn(res);
	}
	return 0;
}

D. Insert a Progression

题意：

有一个长度为 $n$ 的正整数序列与 $1\dots \dots m$ 这 $m$ 个数，你需要将这 $m$ 个数插入到原序列中，使其 ${\sum }_{i=1}^{n+m?1}abs(s[i+1]?s[i])$ 的值最小。

思路：

这道题好无聊的，如果是算相邻数的方差会好玩很多（）。

首先我们先把原序列的相邻两数的差值绝对值之和求出来，因为它是肯定存在的；
其次，我们可以贪心的把 $1\dots \dots m$ 中在原序列的范围内的数都塞进去，并且保证不会造成更多的代价，多一事不如少一事嘛；

那么现在剩下的，就只有：假设原序列中的所有数都在 $[l,r]$ 的范围中，如果 $l>1$ ，那么 $1\dots \dots l?1$ 还没有插入；如果 $r<m$ ，那么 $r+1\dots \dots m$ 还没有插入。
对于这些“凸出来”的数，我们有两种方法去处置他：

1. 将其放到原序列的两端，好处是只会造成一倍的代价，坏处是差值会有些大；
2. 将 $1\dots \dots l?1$ 与原序列中的最小值放到一起， $r+1\dots \dots m$ 与原序列中的最大值放到一起。好处是差值的绝对值一定是最小的，坏处是因为最小值与最大值所在的地方可能不是原序列的两端，那么意思就是这个代价可能需要倍计算两倍。

我们只需要分别计算出两种方式所造成的代价，并取两者中代价较小的即可。

时间复杂度：$O（n）$

int n, m;
int s[N];
signed main() {
	cf{
		sf2(n, m);
		int l = N, r = 0;
		for (int i = 1; i <= n; i++) {
			sf(s[i]);
			l = min(l, s[i]);
			r = max(r, s[i]);
		}
		
		int res = 0;
		for (int i = 1; i < n; i++)
			res += abs(s[i + 1] - s[i]);
			
		PII L, R;
		L.x = R.x = 1;
		while (s[L.x] != l)
			L.x++;
		while (s[R.x] != r)
			R.x++;
		L.y = R.y = n;
		while (s[L.y] != l)
			L.y--;
		while (s[R.y] != r)
			R.y--;
 
		if (l > 1) {
			int tmp = l - 1;
			if (L.x > 1 && L.y < n)
				tmp *= 2;
			tmp = min(tmp, min(s[1], s[n]) - 1);
			res += tmp;
		}
		if (r < m) {
			int tmp = m - r;
			if (R.x > 1 && R.y < n)
				tmp *= 2;
			tmp = min(tmp, m - max(s[1], s[n]));
			res += tmp;
		}
		pfn(res);
	}
	return 0;
}

E. Preorder

题意：

给你一个根节点下标为 $1$ 的满二叉树，每个节点上都有 $A、B$ 中的一个字符，设为 $a[i]$，每个非叶子节点 $u$ 的权值 $s[u]$ 可以表示为 $s[u]=a[u]+s[u?2]+s[u?2+1]$ 。
现在有一种操作，你可以交换任意一个非叶子节点的左右子树，并且这个操作可以进行无限次。
请问根节点的权值有多少种，结果对 $998244353$ 取模。

思路：

一个结论很……怪的题。
我们先从叶子节点的上一层开始讨论：
如果它的叶子节点为 $[A、B]$ 或 $[B、A]$ ，那么只要它交换，根节点的权值也一定会变化，这一点是可以保证的。

那么当我们遍历到第 $u$ 层，它的左右两颗子树分别可以造成 $l，r$ 的变化次数（姑且这么说），当我们想要交换它的左右子树，就不得不考虑到它的两个子树是否完全相同这个问题。

• 如果左右两个子树不同，那么一旦我交换左右两棵子树，根节点的权值必然会变化；
• 如果左右两个子树完全相同，那么必然会出现，交换左右子树之后，根节点的权值不变的情况；

那么这就意味着，如果节点 $u$ 的左右子树不同，那么交换当前节点的左右子树，可以对根节点的权值造成 $2?l?r$ 种变化；而节点 $u$ 的左右子树相同时，我交换左右子树，不会造成任何变化，因为左子树的状态，右子树同样可以达到，因此节点 $u$ 为根节点的子树只能够造成 $l?r$ 种变化。

这样，我们的问题就只剩下一种：如何判断两个满二叉树是完全相同的？
其实，这里我们可以取一个巧，就是将它们都强制转化为一种状态，即将 $[A、B]$ 或 $[B、A]$ ，或者说是将子树的根节点的权值调成为字典序最大的形态。这样，当且仅当两颗完全相同的满二叉树，它们的权值一定会相同。

时间复杂度：$O（n）$

int n;
char s[N];
string d[N];
int res;
int dfs(int u, int k) {
	if (k == n) {
		if (s[u] == 'A')
			d[u] = "0";
		else
			d[u] = "1";
		return 1ll;
	} else {
		int l = dfs(u * 2, k + 1), r = dfs(u * 2 + 1, k + 1);
		if (d[u * 2] < d[u * 2 + 1])
			swap(d[u * 2], d[u * 2 + 1]);
		if (s[u] == 'A')
			d[u] = "0";
		else
			d[u] = "1";
		d[u] += d[u * 2] + d[u * 2 + 1];
 
		if (d[u * 2] == d[u * 2 + 1]) 
			return l * r % mod;
		else return l * r % mod * 2 % mod;
	}
}
signed main() {
	sf(n);
	scanf("%s", s + 1);
	res = dfs(1, 1);
	pfn(res);
	return 0;
}

阅读世界，共赴山海

423全民读书节，邀你共读