Educational codeforces round 127 A-E problem solution

Personal thinking , For record only , You can refer to , Welcome to exchange .

Address of the competition ： Portal

（ This time A-E The simplicity of the puzzle , It feels very interesting , like ）

---

A. String Building

Portal

【 The question 】 Let's give one that only contains ’a’ and ’b’ String , Determine whether the string can be composed of several ”aa”,”aaa”,”bb”,”bbb” Splicing into .

【 Ideas 】 Will several 2 and 3 Add up to get any one greater than 1 The positive integer , So just divide the string into several longest substrings with only one letter , Determine whether the length of each substring is greater than 1 that will do .

【 Code 】

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

Portal

【 The question 】 Given an array of positive integers , Judge whether each number can be tested once +1 or -1 or +0 After the operation, make the array a tolerance of 1 Equal difference sequence of .

【 Ideas 】 Number of each a[i] The range of variation is [a[i]-1,a[i]+1], The size of the first element after the change determines the size of the first element of the resulting arithmetic sequence , That is, there are only three possible cases of the resulting sequence of equal differences . So just list the arithmetic sequence of three cases , Judge whether each sequence of equal differences satisfies 「 Every element is in a[i] Within the range of 」 that will do , As long as there is an equal difference sequence that meets the requirements, the answer is YES.

【 Code 】

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

Portal

【 The question 】 Given represents n An array of store sugar prices and the maximum amount of money you can spend per day x, And known ：

• 1. The price of sugar in every store increases every day 1
• 2. Every shop is limited to 1 Share sugar

Ask how many servings of sugar you can buy at most .

【 Ideas 】 Simple analysis ：

1. 1. Every day, you must start from the cheapest store , It is obvious that Sort Preprocessing ;
2. 2. Buy some of the cheapest stores and know the total cost of these stores , It is obvious that The prefix and Preprocessing .

So the practice is ： Sort the array first , Then find the prefix and array , Find the first place you can buy in the prefix and array , Simulate the process of each day , Keep moving the position you can buy to the left , Until you can't even afford the first position . In order to reduce the time complexity to O(n), All the days of stopping at the same position shall be calculated at one time . See code for details .

【 Code 】

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

Portal

【 The question 】 Given a positive integer array and [1, x] An array of all natural numbers in , Find the value of the new array obtained by arbitrarily inserting all elements of the latter into the former 「 The sum of the absolute values of the difference between adjacent terms 」 What's the minimum

【 Ideas 】 Consider any two adjacent terms of a group of positive integers a[i] and a[i+1], take [a[i],a[i+1]] Monotonically inserting any number of natural numbers in these two terms will not affect the result , And put all [a[i],a[i+1]] After taking the union set, it is [min(a),max(a)], So just consider [min(a),max(a)] Other than natural numbers, that is [1,min(a))∪(max(a),+∞] The effect of natural number insertion on the result .

Consider two insertion methods for the remaining two groups of natural numbers , In the [1,min(a)) Take this group of natural numbers in as an example ：

1. 1. Monotonically insert any two terms a[i],a[i+1] between , Increase the result (min(a[i],a[i+1])-1)*2. obviously a[i] and a[i+1] One of them should be min(a) To minimize the result , So at least increase the result (min(a)-1)*2
2. 2. Monotonically insert the boundary position on both sides , At least increase the result min(a[1],a[n])-1

So just look at the two methods, which makes the result increase less, and choose which one .

【 Code 】

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

Portal

【 The question 】 Given a 「 A node is a character ’A’ or ’B’」 Of Perfect binary tree , Right 「 All trees formed by arbitrarily exchanging each group of sibling nodes 」 Conduct The first sequence traversal How many different strings can be generated .

【 Ideas 】 Thinking process ：

First, simply think of , If you have any m The exchange of two children of a node will lead to the change of binary tree , Then there are 2^m A combination of operations . But considering a special situation ： There are two of the above nodes , A binary tree changes after two children are exchanged , After exchanging two children of the other, the binary tree becomes the same again . In this case, the answer will be less than 2^m. Why is this so ？ Through the analysis of , The discovery is because the subtree with the two children of the higher node as the root is “ structure ” same , namely —— It is possible to make the two subtrees the same by arbitrarily exchanging the sibling nodes in the subtree with its two children as the root . It can also be understood as , The of each node in the two trees 「 Difference between left and right position attributes 」 Ignore that the last two trees are the same . therefore , The exchange of two children of the higher node does not change the “ structure ”, That is, the function of exchanging two children can be used 「 Exchange two sub nodes of other nodes 」 Equivalent substitution , So this higher node cannot be included in the answer .

practice ： Do... On trees DFS, All nodes of each subtree are divided into “A Left B Right ” The order of the rules —— Minimize the dictionary order of the sorted pre traversal string （ With string < string For the comparison function, you can realize ）, Eliminate all nodes 「 Difference between left and right position attributes 」. Then compare the pre order traversal strings of the two children of each non leaf node , If different , Then it shows that exchanging the two children can make the binary tree “ structure ” change . Count the number of such non leaf nodes m, The answer is 2^m. Remember to take the mold according to the requirements of the topic .

【 Code 】

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;
}

---

Fight occasionally CF It's fun in pain .

Written on the last day of centralized isolation medical observation .