当前位置:网站首页>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
边栏推荐
- The win10 taskbar notification area icon is missing
- Tencent has written a few words, Ali has written them all for a month
- Leetcode162 - find peak - dichotomy - array
- Detailed explanation of C language knowledge points -- first understanding of C language [1] - vs2022 debugging skills and code practice [1]
- Fill in the next right node pointer II of each node [classical hierarchy traversal | regarded as linked list]
- API gateway / API gateway (III) - use of Kong - current limiting rate limiting (redis)
- async关键字
- LeetCode149-直线上最多的点数-数学-哈希表
- Have you really learned the operation of sequence table?
- Basic operation of sequential stack
猜你喜欢
asp. Net method of sending mail using mailmessage
The win10 taskbar notification area icon is missing
Leetcode167 - sum of two numbers II - double pointer - bisection - array - Search
UML学习_day2
How to design a good API interface?
What is the role of the full connection layer?
Redis主从同步
UML learning_ Day2
Leetcode153 - find the minimum value in the rotation sort array - array - binary search
LeetCode167-两数之和II-双指针-二分-数组-查找
随机推荐
tcp_ Diag kernel related implementation 1 call hierarchy
LeetCode165-比较版本号-双指针-字符串
Sword finger offer (1) -- for Huawei
【thymeleaf】处理空值和使用安全操作符
Borui data and F5 jointly build the full data chain DNA of financial technology from code to user
Have you really learned the operation of sequence table?
redis-shake 使用中遇到的错误整理
Introduction to distributed transaction Seata
Five data types of redis
Ffmpeg installation error: NASM / yasm not found or too old Use --disable-x86asm for a clipped build
Elk installation
like和regexp差别
TLS / SSL protocol details (28) differences between TLS 1.0, TLS 1.1 and TLS 1.2
Fill in the next right node pointer II of each node [classical hierarchy traversal | regarded as linked list]
Async void caused the program to crash
kubernetes之常用Pod控制器的使用
8.3 language model and data set
LeetCode149-直线上最多的点数-数学-哈希表
The wechat applet optimizes the native request through the promise of ES6
Set onedrive or Google drive as a drawing bed in upic for free