当前位置：网站首页>Educational Codeforces Round 130 (Rated for Div. 2)A~C
Educational Codeforces Round 130 (Rated for Div. 2)A~C
2022-07-06 16:15:00 【Hello_ Ä】
Educational Codeforces Round 130 (Rated for Div. 2)A~C
It's hard to write so fast , result d It's a good interaction. I haven't seen it directly after work , It's over in half an hour. It's so fast
Problem - A - Codeforces
You are walking through a parkway near your house. The parkway has n+1 benches in a row numbered from 1 to n+1 from left to right. The distance between the bench i and i+1 is ai meters.
Initially, you have m units of energy. To walk 1 meter of distance, you spend 1 unit of your energy. You can’t walk if you have no energy. Also, you can restore your energy by sitting on benches (and this is the only way to restore the energy). When you are sitting, you can restore any integer amount of energy you want (if you sit longer, you restore more energy). Note that the amount of your energy can exceed m.
Your task is to find the minimum amount of energy you have to restore (by sitting on benches) to reach the bench n+1 from the bench 1 (and end your walk).
You have to answer t independent test cases.
Input
The first line of the input contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.
The first line of the test case contains two integers n and m (1≤n≤100; 1≤m≤104).
The second line of the test case contains n integers a1,a2,…,an (1≤ai≤100), where ai is the distance between benches i and i+1.
Output
For each test case, print one integer — the minimum amount of energy you have to restore (by sitting on benches) to reach the bench n+1 from the bench 1 (and end your walk) in the corresponding test case.
Example
input
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
output
3
8
0
Problem analysis
The title is that there is n A chair , The distance between the chair and the previous chair is a[i], You initially have m A little energy , Every meter you walk consumes 1 A little energy , When you walk to the chair, you can recover your energy （ As many times as you want ）, Ask you how much energy you need to recover at least when you walk to the last chair .
Look directly at the position of the last chair , That is all a[i] The sum of , Then see whether your energy is enough or not , If enough, you don't need to rest , Total recovery 0 energy , If it's not enough , To recover sum-m A little energy .
AC Code
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n,m;
cin >> n >> m;
vector<int>v(n);
int res = 0;
for (int i = 0; i < n; i++)
{
cin >> v[i];
res += v[i];
}
if (res <= m)cout << 0 << endl;
else cout << res - m << endl;
}
return 0;
}
Problem - B - Codeforces
The store sells n items, the price of the i-th item is pi. The store’s management is going to hold a promotion: if a customer purchases at least x items, y cheapest of them are free.
The management has not yet decided on the exact values of x and y. Therefore, they ask you to process q queries: for the given values of x and y, determine the maximum total value of items received for free, if a customer makes one purchase.
Note that all queries are independent; they don’t affect the store’s stock.
Input
The first line contains two integers n and q (1≤n,q≤2⋅105) — the number of items in the store and the number of queries, respectively.
The second line contains n integers p1,p2,…,pn (1≤pi≤106), where pi — the price of the i-th item.
The following q lines contain two integers xi and yi each (1≤yi≤xi≤n) — the values of the parameters x and y in the i-th query.
Output
For each query, print a single integer — the maximum total value of items received for free for one purchase.
Example
input
5 3
5 3 1 5 2
3 2
1 1
5 3
output
8
5
6
Problem analysis
This question means that when you go shopping, you encounter a discount , Buy enough x Something , Then the cheapest one y Goods can be free , Now here you are n Price of items and m Time to ask , I'll give you one for each inquiry x and y, Ask what is the maximum value of the goods you can free .
Greedy practices , Sort the price of goods in descending order , Calculate the prefix and （ I prefix and subscript from 1 Start ）.x It's the quantity of goods you bought , We want free goods to be the most valuable , Then the things you buy are naturally the most expensive , The prices of these goods are sorted by us in descending order , The top ones are the most expensive , therefore sum[x] It is the sum of the value of the goods we bought , among y A cheap one will be free , So what is not free is x-y individual , Their value is sum[x-y], Then the value of free goods is :sum[x]-sum[x-y].
AC Code
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
bool cmp(int a, int b)
{
return a > b;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int>v(n), sum(n + 1);
int res = 0;
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
sort(v.begin(), v.end(), cmp);
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + v[i - 1];
}
while (m--)
{
int x, y;
cin >> x >> y;
cout << sum[x] - sum[x - y] << endl;
}
return 0;
}
Problem - C - Codeforces
You are given two strings s and t, both of length n. Each character in both string is ‘a’, ‘b’ or ‘c’.
In one move, you can perform one of the following actions:
choose an occurrence of “ab” in s and replace it with “ba”;
choose an occurrence of “bc” in s and replace it with “cb”.
You are allowed to perform an arbitrary amount of moves (possibly, zero). Can you change string s to make it equal to string t?
Input
The first line contains a single integer q (1≤q≤104) — the number of testcases.
The first line of each testcase contains a single integer n (1≤n≤105) — the length of strings s and t.
The second line contains string s of length n. Each character is ‘a’, ‘b’ or ‘c’.
The third line contains string t of length n. Each character is ‘a’, ‘b’ or ‘c’.
The sum of n over all testcases doesn’t exceed 105.
Output
For each testcase, print “YES” if you can change string s to make it equal to string t by performing an arbitrary amount of moves (possibly, zero). Otherwise, print “NO”.
Example
input
5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab
output
YES
NO
YES
YES
NO
Problem analysis
This question is to give you two strings a and b, You have two operations , First, string a A substring in “ab” become “ba”, The other is string a A substring in “bc“ become ”cb“, Ask if it is possible for you to a Variable sum b equally .
So let's analyze that ,
- First of all, we can only "ab" become ”ba", But you can't put ”ba“ become ”ab“, The second operation is the same , and ,”ac“ It can't become ”ca“.
- since ”ab” Can become “ba”, Let's postpone it ,“abbb” Can become “babb”、“bbab” and “bbba”, Similarly, the second operation “bc” Extended application “bccc” Is the same .
- But what if there are other characters on the road ？ such as “abbb” become “abcbb”, Then it can only be changed into “bacbb” and “acbbb”, because ac It can't be exchanged , So you will encounter c Stuck when . If “bccc" become “bcacc“, It can only become “cbacc”, because ac Can't change ,ba Nor can it change .
- because ac Can't be ca, So in a string ,a The location of can only be through ab become ba To move backwards , Can't move forward ;c The position of can only move forward, not backward .
The above is our conclusion , And then for convenience , We can traverse the string from back to front ：（ In this process, we should ensure that the position characters we have traversed are equal ）
When the traversal position is the same as the character position , Let's go to the next position .
If different , We will judge the situation according to the characters of the first string and the characters of the second string ：
- When the character of the first string is ‘a’ when , No matter the character of the second string is ’b’ still ‘c’, We all want to a Send it to the front , Exchange the characters we need , Because we traverse from back to front , And we guarantee that the traversed characters are equal , So you can't send the character of the current position to the later position , In this way, the characters in the following positions are not equal . And just like our conclusion 4 Yes ,a Cannot move forward , So when the character of the first string is ’a’ when , Direct output no.
- When the character of the first string is ‘b’ when , If the character of the second string is ’c’, It means that we should find a ‘c’ Change to our position , But it's like 4 Yes ,c Cannot move back , So direct output no. If it is ’a’, According to the conclusion 2 We'll go ahead and find the nearest ‘a’ Exchange it , And just like the conclusion 3 If you encounter characters on the way ’c‘, It means that we cannot ’a’ Move to the back , because ac The positions cannot be interchanged , So if we can find the nearest ‘a’, And I didn't meet on the road ’c’, Then we'll exchange two characters , Otherwise output no.
- When the character of the first string is ‘c’ when , If the character of the second string is ’a’, Because we can't let ac swap , So it can output no, If it is ‘b’, Let's draw a conclusion 2 Go straight ahead and find the nearest ’b’ Change it over , If you encounter characters on the road ‘a’, Output directly no.
If there is no output after traversal no, It outputs yes.
AC Code
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n;
string a, b;
cin >> n >> a >> b;
if (a == b)
{
cout << "YES" << endl;
continue;
}
if (n == 1)
{
cout << "NO" << endl;
continue;
}
bool flag = true;
int l = n - 1, r = n - 1;
while (l >= 0 && r >= 0)
{
if (a[l] == b[r])l--, r--;
else
{
if (a[l] == 'a')
{
flag = false;
break;
}
else if (a[l] == 'b')
{
if (b[r] == 'a')
{
int pos = l - 1;
bool st = false;
while (pos >= 0)
{
if (a[pos] == 'b')pos--;
else if (a[pos] == 'a')
{
st = true;
break;
}
else break;
}
if (!st)
{
flag = false;
break;
}
else swap(a[pos], a[l]);
}
else
{
flag = false;
break;
}
}
else
{
if (b[r] == 'b')
{
int pos = l - 1;
bool st = false;
while (pos >= 0)
{
if (a[pos] == 'c')pos--;
else if (a[pos] == 'b')
{
st = true;
break;
}
else break;
}
if (!st)
{
flag = false;
break;
}
else swap(a[pos], a[l]);
}
else
{
flag = false;
break;
}
}
}
}
if (flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
But in extreme cases, it will get stuck n^2, So I optimized .
When we look for the nearest characters above, we look for them one by one , so much trouble , But in fact, you can preprocess the position of all characters first , Then when looking for the target character, just look at whether there are other characters on the path , In this way, it can be optimized to On.
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n;
string a, b;
vector<int>x, y;
cin >> n >> a >> b;
for (int i = 0; i < n; i++)
{
if (a[i] == 'a' || a[i] == 'c')x.push_back(i);
if (a[i] == 'b' || a[i] == 'a')y.push_back(i);
}
bool flag = true;
int l = n - 1, r = n - 1;
while (l >= 0 && r >= 0)
{
while (!x.empty()&&l <= x.back())x.pop_back();
while (!y.empty()&&l <= y.back())y.pop_back();
if (a[l] == b[r])l--, r--;
else
{
if (a[l] == 'a')
{
flag = false;
break;
}
else if (a[l] == 'b')
{
if (b[r] == 'a')
{
int pos ;
bool st = false;
while (!x.empty()&&!st)
{
if (a[x.back()] == 'a')st = true;
else break;
}
if (!st)
{
flag = false;
break;
}
else
{
swap(a[x.back()], a[l]);
x.pop_back();
}
}
else
{
flag = false;
break;
}
}
else
{
if (b[r] == 'b')
{
bool st = false;
while (!y.empty()&&!st)
{
if (a[y.back()] == 'b')st = true;
else break;
}
if (!st)
{
flag = false;
break;
}
else
{
swap(a[y.back()], a[l]);
y.pop_back();
}
}
else
{
flag = false;
break;
}
}
}
}
if (flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
边栏推荐
- 栈的经典应用—括号匹配问题
- Analysis of protobuf format of real-time barrage and historical barrage at station B
- C language is the watershed between low-level and high-level
- Auto.js入门
- Opencv learning log 26 -- detect circular holes and mark them
- 860. Lemonade change
- AcWing——第55场周赛
- Suffix expression (greed + thinking)
- Penetration test (7) -- vulnerability scanning tool Nessus
- 969. Pancake sorting
猜你喜欢
Penetration test (7) -- vulnerability scanning tool Nessus
Penetration test (8) -- official document of burp Suite Pro
Borg maze (bfs+ minimum spanning tree) (problem solving report)
The concept of C language array
Nodejs+vue online fresh flower shop sales information system express+mysql
![[exercise-5] (UVA 839) not so mobile (balance)](/img/8e/48dcf75f7347b36301df6fc129c09d.png)
[exercise-5] (UVA 839) not so mobile (balance)
1855. Maximum distance of subscript alignment
拉取分支失败，fatal: ‘origin/xxx‘ is not a commit and a branch ‘xxx‘ cannot be created from it
Maximum product (greedy)
读取和保存zarr文件
随机推荐
浏览器打印边距，默认/无边距，占满1页A4
Penetration test (8) -- official document of burp Suite Pro
Alice and Bob (2021 Niuke summer multi school training camp 1)
力扣——第298场周赛
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
[exercise-2] (UVA 712) s-trees
渗透测试 ( 4 ) --- Meterpreter 命令详解
第 300 场周赛 - 力扣（LeetCode）
useEffect，函数组件挂载和卸载时触发
Pyside6 signal, slot
指定格式时间，月份天数前补零
Suffix expression (greed + thinking)
Codeforces Round ＃801 (Div. 2)A~C
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
Classic application of stack -- bracket matching problem
Problem - 1646C. Factorials and Powers of Two - Codeforces
快速转 TypeScript 指南
Is the sanic asynchronous framework really so strong? Find truth in practice
605. Planting flowers
875. 爱吃香蕉的珂珂 - 力扣（LeetCode）