Educational Codeforces Round 127 A-E题解

个人思路，仅作记录，可以参考，欢迎交流。

比赛地址：传送门

（这次的A-E题谜之简单，感觉出得还挺有意思的，喜欢）

---

A. String Building

传送门

【题意】给定一个只含’a’和’b’的字符串，判断该字符串是否能由若干”aa”,”aaa”,”bb”,”bbb”拼接而成。

【思路】将若干2和3相加可以得到任何一个大于1的正整数，所以只要把字符串分为若干个只含一种字母的最长子串，判断每个子串的长度是否都大于1即可。

【代码】

void solve()
{
	string s;
	cin >> s;
	int len = s.length();
	int start = 0;
	for (int i = 1; i < len; ++i)
	{
		if (s[i] != s[i - 1])
		{
			if (i - start > 1)
			{
				start = i;
			}
			else
			{
				cout << "NO\n";
				return;
			}
		}
	}
	if (len - start == 1)
	{
		cout << "NO\n";
		return;
	}
	cout << "YES\n";
	return;
}

---

B. Consecutive Points Segment

传送门

【题意】给定一个正整数数组，判断能否在对每个数进行一次+1或-1或+0操作后使得数组成为一个公差为1的等差数列。

【思路】每个数a[i]的变化范围为[a[i]-1,a[i]+1]，而首元素变化后的大小决定了得到的等差数列的首元素大小，即得到的等差数列只有三种可能情况。所以只要枚举出三种情况的等差数列，对每个等差数列判断其是否满足「每个元素都在a[i]的变化范围内」即可，只要有一种等差数列满足要求答案即为YES。

【代码】

int a[200005];

bool InRange(int a, int b)
{
	return a <= b + 1 && a >= b - 1;
}

void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	if (n == 1)
	{
		cout << "YES\n";
		return;
	}
	bool flag = 0;
	int base = a[1] - 1;
	for (int i = 2; i <= n; ++i)
	{
		if (!InRange(a[i], base + i - 1))
		{
			break;
		}
		else if (i == n)
		{
			flag = 1;
		}
	}
	base++;
	for (int i = 2; i <= n; ++i)
	{
		if (!InRange(a[i], base + i - 1))
		{
			break;
		}
		else if (i == n)
		{
			flag = 1;
		}
	}
	base++;
	for (int i = 2; i <= n; ++i)
	{
		if (!InRange(a[i], base + i - 1))
		{
			break;
		}
		else if (i == n)
		{
			flag = 1;
		}
	}
	cout << (flag ? "YES\n" : "NO\n");
	return;
}

---

C. Dolce Vita

传送门

【题意】给定代表n个商店糖价的数组和每天最多能花的钱数x，并且已知：

• 1. 每家店的糖每天会涨价1
• 2. 每家店每天限购1份糖

求最多能买到多少份糖。

【思路】简单分析：

1. 1. 每天肯定要从最便宜的店开始买起，显然要进行排序预处理；
2. 2. 买最便宜的若干家店要知道这些店的总花费，显然要进行前缀和预处理。

所以做法为：先对数组进行排序，再求出前缀和数组，在前缀和数组中找到最初能买到的位置，对每一天的过程进行模拟，使能买到的位置不断左移，直到连第一个位置也买不起为止。为了使时间复杂度降到O(n)，停在同一个位置的所有天数要一次性计算完。具体见代码。

【代码】

long long a[200005];
long long prefix[200005] = { 0 };

void solve()
{
	long long ans = 0;
	long long n, x;
	cin >> n >> x;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++i)
	{
		prefix[i] = prefix[i - 1] + a[i];
	}
	long long p = upper_bound(prefix, prefix + n + 1, x) - 1 - prefix;
	long long day = 0;
	while (p > 0)
	{
		while (prefix[p] + day * p > x)
		{
			p--;
		}
		if (p <= 0)
		{
			break;
		}
		ans += ((x - prefix[p] - day * p) / p + 1) * p;
		day += (x - prefix[p] - day * p) / p + 1;
	}
	cout << ans << '\n';
	return;
}

---

D. Insert a Progression

传送门

【题意】给定一个正整数组和[1, x]内所有自然数组成的数组，求将后者所有元素任意插入前者后得到的新数组的「相邻项之差的绝对值的总和」最小为多少

【思路】考虑正整数组的任意相邻两项a[i]和a[i+1]，将[a[i],a[i+1]]内的任何若干自然数单调地插入这两项中都不会对结果产生影响，而将所有[a[i],a[i+1]]取并集后即为[min(a),max(a)]，所以只要考虑[min(a),max(a)]以外的自然数也即[1,min(a))∪(max(a),+∞]内的自然数插入对结果的影响。

对剩下的两组自然数分别考虑两种插入方法，以在[1,min(a))内的这组自然数为例：

1. 1. 单调插入任意两项a[i],a[i+1]间，使结果增加(min(a[i],a[i+1])-1)*2。显然a[i]和a[i+1]其中一个要为min(a)才能使结果最小，所以最少使结果增加(min(a)-1)*2
2. 2. 单调插入两边边界位置，最少使结果增加min(a[1],a[n])-1

所以只要看两种方法哪个使结果增加得少就选哪个即可。

【代码】

int a[200005];

void solve()
{
	long long ans = 0;
	int n, x;
	cin >> n >> x;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		if (i > 1)
		{
			ans += abs(a[i] - a[i - 1]);
		}
	}
	int maxp = max_element(a + 1, a + 1 + n) - a;
	int minp = min_element(a + 1, a + 1 + n) - a;
	if (x > a[maxp])
	{
		if (maxp == 1 || maxp == n)
		{
			ans += x - a[maxp];
		}
		else
		{
			int add1 = (x - a[maxp]) * 2;
			add1 = min(add1, x - a[1]);
			add1 = min(add1, x - a[n]);
			ans += add1;
		}
	}
	if (a[minp] > 1)
	{
		if (minp == 1 || minp == n)
		{
			ans += a[minp] - 1;
		}
		else
		{
			int add2 = (a[minp] - 1) * 2;
			add2 = min(add2, a[1] - 1);
			add2 = min(add2, a[n] - 1);
			ans += add2;
		}
	}
	cout << ans << '\n';
	return;
}

---

E. Preorder

传送门

【题意】给定一个「结点是一个字符’A’或’B’」的完美二叉树，求对「将其每一组兄弟结点任意互换形成的所有树」进行先序遍历能产生多少种不同的字符串。

【思路】思考过程：

首先简单地想到，若有m个结点的两子互换会导致二叉树变化，则有2^m种操作组合。但是又考虑到一种特殊情况：有两个上述结点，对一个进行两子互换后二叉树变化，对另一个进行两子互换后二叉树又变到了原样。这种情况下答案就会少于2^m。为什么会这样呢？经过分析，发现是因为以这两个结点中较高的那个结点的两子为根的子树是“结构”相同的，即——将以其两子为根的子树中的兄弟结点进行任意互换有可能使这两个子树相同。也可以理解为，将两树中每个结点的「左右位置属性的差异」无视后两树是相同的。所以，较高的这个结点的两子互换并不会改变二叉树的“结构”，即对它进行两子互换的作用可以用「对其它结点进行两子互换」等效替代，所以这个较高的结点不能计入答案。

做法：对树进行DFS，将每个子树的所有结点按照“A左B右”的规则排序——使得排序后的先序遍历字符串字典序最小（以string < string为比较函数即可实现），消除所有结点「左右位置属性的差异」。然后比较每个非叶结点两子的先序遍历字符串，若不同，则说明将两子互换可以使二叉树“结构”改变。统计下这样的非叶结点的个数m，答案即为2^m。记得按题目要求取模。

【代码】

const long long MOD = 998244353;

int n;//[2,18]
string s;//len=(1<<n)-1
long long ans = 1;

string dfs(int now)
{
	if (now < (1 << (n - 1)))
	{
		string lef = dfs(now * 2);
		string rig = dfs(now * 2 + 1);
		if (lef != rig)
		{
			ans *= 2;
			ans %= MOD;
		}
		if (lef > rig)
		{
			swap(lef, rig);
		}
		return s[now] + lef + rig;
	}
	else
	{
		return s[now] + string("");
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> s;
	s = ' ' + s;
	dfs(1);
	cout << ans << '\n';
	return 0;
}

---

偶尔打打CF也算苦中作乐了。

写于集中隔离医学观察的最后一天。