当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
(POJ - 3579) median (two points)
969. Pancake sorting
Flask框架配置loguru日志庫
滲透測試 ( 1 ) --- 必備 工具、導航
b站 实时弹幕和历史弹幕 Protobuf 格式解析
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
TCP's three handshakes and four waves
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
渗透测试 ( 4 ) --- Meterpreter 命令详解
QT实现圆角窗口
随机推荐
第 300 场周赛 - 力扣(LeetCode)
Essai de pénétration (1) - - outils nécessaires, navigation
Ball Dropping
C basic grammar
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
1689. Ten - the minimum number of binary numbers
Problem - 922D、Robot Vacuum Cleaner - Codeforces
1903. Maximum odd number in string
605. Planting flowers
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
Specify the format time, and fill in zero before the month and days
JS call camera
Understand what is a programming language in a popular way
Interval sum ----- discretization
Openwrt build Hello ipk
Openwrt source code generation image
双向链表—全部操作
[exercise -11] 4 values why sum is 0 (and 4 values of 0)
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Determine the Photo Position