# Educational codeforces round 127 A-E problem solution

2022-04-23 15:18:00

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;

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;
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;
long long prefix = { 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,a[n])-1

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

【 Code 】

``````int a;

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;
}
}
if (a[minp] > 1)
{
if (minp == 1 || minp == n)
{
ans += a[minp] - 1;
}
else
{
int add2 = (a[minp] - 1) * 2;
}
}
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 .

https://yzsam.com/2022/04/202204231508075663.html