当前位置:网站首页>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
边栏推荐
- Ffmpeg installation error: NASM / yasm not found or too old Use --disable-x86asm for a clipped build
- TLS / SSL protocol details (30) RSA, DHE, ecdhe and ecdh processes and differences in SSL
- Precautions for use of dispatching system
- Elk installation
- Detailed explanation of C language knowledge points -- first understanding of C language [1] - vs2022 debugging skills and code practice [1]
- MySQL Basics
- Llvm - generate for loop
- 小红书 timestamp2 (2022/04/22)
- TLS / SSL protocol details (28) differences between TLS 1.0, TLS 1.1 and TLS 1.2
- adobe illustrator 菜单中英文对照
猜你喜欢
asp. Net method of sending mail using mailmessage
UML学习_day2
How to design a good API interface?
X509 certificate cer format to PEM format
Reptile exercises (1)
Leetcode167 - sum of two numbers II - double pointer - bisection - array - Search
eolink 如何助力遠程辦公
Detailed explanation of C language knowledge points - data types and variables [2] - integer variables and constants [1]
Have you really learned the operation of sequence table?
大文件如何快速上传?
随机推荐
My raspberry PI zero 2W tossing notes record some problems encountered and solutions
API gateway / API gateway (III) - use of Kong - current limiting rate limiting (redis)
asp. Net method of sending mail using mailmessage
Sword finger offer (1) -- for Huawei
中富金石财富班29800效果如何?与专业投资者同行让投资更简单
Nacos程序连接MySQL8.0+ NullPointerException
Comment eolink facilite le télétravail
Analysis of common storage types and FTP active and passive modes
MySQL sync could not find first log file name in binary log index file error
Redis master-slave synchronization
买卖股票的最佳时机系列问题
Example of time complexity calculation
MySQL installation process (steps for successful installation)
nuxt项目:全局获取process.env信息
Detailed explanation of C language knowledge points -- first understanding of C language [1] - vs2022 debugging skills and code practice [1]
What is the effect of Zhongfu Jinshi wealth class 29800? Walk with professional investors to make investment easier
Wechat applet customer service access to send and receive messages
1990年1月1日是星期一,定义函数date_to_week(year,month,day),实现功能输入年月日后返回星期几,例如date_to_week(2020,11,1),返回:星期日。 提示:
Basic operation of sequential stack
Flink DataStream 类型系统 TypeInformation