## 当前位置：网站首页>Educational codeforces round 127 A-E problem solution

# Educational codeforces round 127 A-E problem solution

2022-04-23 15:18:00 【Cu_ OH_ two】

** 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

【 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

【 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

【 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. Every day, you must start from the cheapest store , It is obvious that
**Sort**Preprocessing ; - 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

【 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. 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. 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

【 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 .

版权声明

本文为[Cu_ OH_ two]所创，转载请带上原文链接，感谢

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

## 边栏推荐

- SSH connects to the remote host through the springboard machine
- thinkphp5+数据大屏展示效果
- Llvm - generate local variables
- Sword finger offer (2) -- for Huawei
- Redis主从同步
- Error: unable to find remote key "17f718f726"“
- Llvm - generate if else and pH
- For 22 years, you didn't know the file contained vulnerabilities?
- Precautions for use of dispatching system
- 填充每个节点的下一个右侧节点指针 II [经典层次遍历 | 视为链表 ]

## 猜你喜欢

Redis主从同步

每日一题-LeetCode396-旋转函数-递推

免费在upic中设置OneDrive或Google Drive作为图床

asp. Net method of sending mail using mailmessage

What exactly does the distributed core principle analysis that fascinates Alibaba P8? I was surprised after reading it

中富金石财富班29800效果如何？与专业投资者同行让投资更简单

UML学习_day2

Comment eolink facilite le télétravail

Tencent has written a few words, Ali has written them all for a month

大文件如何快速上传？

## 随机推荐

22年了你还不知道文件包含漏洞？

Async void caused the program to crash

JS - implémenter la fonction de copie par clic

我的 Raspberry Pi Zero 2W 折腾笔记，记录一些遇到的问题和解决办法

Difference between like and regexp

LeetCode149-直线上最多的点数-数学-哈希表

How to write the keywords in the cover and title? As we media, why is there no video playback

填充每个节点的下一个右侧节点指针 II [经典层次遍历 | 视为链表 ]

Adobe Illustrator menu in Chinese and English

LeetCode165-比较版本号-双指针-字符串

Async keyword

Basic operation of sequential stack

MySQL Basics

The life cycle of key value in redis module programming

thinkphp5+数据大屏展示效果

牛客网数据库SQL实战详细剖析(26-30)

Redis master-slave synchronization

Llvm - generate for loop

8.4 realization of recurrent neural network from zero

【thymeleaf】处理空值和使用安全操作符