Codeforces Round #797 (Div. 3)无F
这打的也太屎了，白天把G补了才知道简单的很，但f还是没头绪呜呜呜
Problem - A - Codeforces
Given the integer n — the number of available blocks. You must use all blocks to build a pedestal.
The pedestal consists of 3 platforms for 2-nd, 1-st and 3-rd places respectively. The platform for the 1-st place must be strictly higher than for the 2-nd place, and the platform for the 2-nd place must be strictly higher than for the 3-rd place. Also, the height of each platform must be greater than zero (that is, each platform must contain at least one block).
Example pedestal of n=11 blocks: second place height equals 4 blocks, first place height equals 5 blocks, third place height equals 2 blocks.
Among all possible pedestals of n blocks, deduce one such that the platform height for the 1-st place minimum as possible. If there are several of them, output any of them.
Input
The first line of input data contains an integer t (1≤t≤104) — the number of test cases.
Each test case contains a single integer n (6≤n≤105) — the total number of blocks for the pedestal. All n blocks must be used.
It is guaranteed that the sum of n values over all test cases does not exceed 106.
Output
For each test case, output 3 numbers h2,h1,h3 — the platform heights for 2-nd, 1-st and 3-rd places on a pedestal consisting of n blocks (h1+h2+h3=n, 0<h3<h2<h1).
Among all possible pedestals, output the one for which the value of h1 minimal. If there are several of them, output any of them.
Example
input
6
11
6
10
100000
7
8
output
4 5 2
2 3 1
4 5 1
33334 33335 33331
2 4 1
3 4 1
问题解析
签到题，意思是说给你n个方块，用这n个方块搭建三个柱子，中间柱子高度要严格大于左边的，左边柱子高度要严格大于右边的，让你写出个搭法让中间的柱子尽可能矮。
先看n能不能被3整除，如果可以，答案就是：n/3，n/3+1，n/3-1。
如果不能被3整除，就看余数的奇偶性：
如果是奇数，答案就可以是：n/3+余数/2，n/3+余数/2+2，n/3-1。
如果是偶数，答案就可以是：n/3+余数/2，n/3+余数/2+1，n/3-1。
AC代码
#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 = 1e3 + 50;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
string s;
cin >> t;
while (t--)
{
int n;
cin >> n;
int ans = n / 3;
if (n % 3 == 0)
{
cout << ans << " " << ans + 1 << " " << ans - 1 << endl;
}
else
{
int res = n % 3;
if (res % 2 == 0)
cout << ans + res / 2 << " " << ans + 1 + res / 2 << " " << ans - 1 << endl;
else
cout << ans + res / 2 << " " << ans + 2 + res / 2 << " " << ans - 1 << endl;
}
}
return 0;
}
Problem - B - Codeforces
Kristina has two arrays a and b, each containing n non-negative integers. She can perform the following operation on array a any number of times:
apply a decrement to each non-zero element of the array, that is, replace the value of each element ai such that ai>0 with the value ai?1 (1≤i≤n). If ai was 0, its value does not change.
Determine whether Kristina can get an array b from an array a in some number of operations (probably zero). In other words, can she make ai=bi after some number of operations for each 1≤i≤n?
For example, let n=4, a=[3,5,4,1] and b=[1,3,2,0]. In this case, she can apply the operation twice:
after the first application of the operation she gets a=[2,4,3,0];
after the second use of the operation she gets a=[1,3,2,0].
Thus, in two operations, she can get an array b from an array a.
Input
The first line of the input contains an integer t (1≤t≤104) —the number of test cases in the test.
The descriptions of the test cases follow.
The first line of each test case contains a single integer n (1≤n≤5?104).
The second line of each test case contains exactly n non-negative integers a1,a2,…,an (0≤ai≤109).
The third line of each test case contains exactly n non-negative integers b1,b2,…,bn (0≤bi≤109).
It is guaranteed that the sum of n values over all test cases in the test does not exceed 2?105.
Output
For each test case, output on a separate line:
YES, if by doing some number of operations it is possible to get an array b from an array a;
NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).
Example
input
6
4
3 5 4 1
1 3 2 0
3
1 2 1
0 1 0
4
5 3 7 2
1 1 1 1
5
1 2 3 4 5
1 2 3 4 6
1
8
0
1
4
6
output
YES
YES
NO
NO
YES
NO
问题解析
这题是说给你两个数组a和b，每次可以进行一个操作，把a数组的所有非0整数-1，问a数组最后能不能变成b数组。
可以先用一个数组c把a[i]和b[i]的差值c[i]记录下来，再用一个数组记录一下b[i]是否为0（我这里用的pair，把两个数组合并成一个）,再随便取个b[i]不为0的差值做标准。注意，如果有一个a[i]大于b[i]，那就是NO。
然后遍历一遍c数组，如果当前元素等于我们之前记录的标准就去找下一个元素，如果不等于就看这个位置的b[i]是否为0，如果c[i]小于
标准，且b[i]等于0，那这个也是合理的，反之如果b[i]不为0，或者c[i]大于标准，都是NO。
AC代码
#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 = 1e3 + 50;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
string s;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int>a(n), b(n);
vector<PII>ans(n);
for (int i = 0; i < n; i++)cin >> a[i];
bool flag = true;
int res = 1e9;
for (int i = 0; i < n; i++)
{
cin >> b[i];
if (b[i] > a[i])flag = false;
ans[i].first = a[i] - b[i];
ans[i].second = 0;
if (b[i] == 0)ans[i].second = -1;
else res = ans[i].first;
}
if (!flag)
{
cout << "NO" << endl;
continue;
}
if (n == 1)
{
cout << "YES" << endl;
continue;
}
for (int i = 0; i < n; i++)
{
if (ans[i].first != res)
{
if (ans[i].first < res && ans[i].second == -1)continue;
else flag = false;
}
}
if (flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
Problem - C - Codeforces
Recently, Polycarp completed n successive tasks.
For each completed task, the time si is known when it was given, no two tasks were given at the same time. Also given is the time fi when the task was completed. For each task, there is an unknown value di (di>0) — duration of task execution.
It is known that the tasks were completed in the order in which they came. Polycarp performed the tasks as follows:
As soon as the very first task came, Polycarp immediately began to carry it out.
If a new task arrived before Polycarp finished the previous one, he put the new task at the end of the queue.
When Polycarp finished executing the next task and the queue was not empty, he immediately took a new task from the head of the queue (if the queue is empty — he just waited for the next task).
Find di (duration) of each task.
Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The descriptions of the input data sets follow.
The first line of each test case contains one integer n (1≤n≤2?105).
The second line of each test case contains exactly n integers s1<s2<?<sn (0≤si≤109).
The third line of each test case contains exactly n integers f1<f2<?<fn (si<fi≤109).
It is guaranteed that the sum of n over all test cases does not exceed 2?105.
Output
For each of t test cases print n positive integers d1,d2,…,dn — the duration of each task.
Example
input
4
3
0 3 7
2 10 11
2
10 15
11 16
9
12 16 90 195 1456 1569 3001 5237 19275
13 199 200 260 9100 10000 10914 91066 5735533
1
0
1000000000
output
2 7 1
1 1
1 183 1 60 7644 900 914 80152 5644467
1000000000
问题解析
这题是说你有n个任务要完成，给你两个数组a和b，这些任务会在a[i]时发给你，你会在b[i]时完成，问你完成这个任务一共花了多少时间。如果在你做任务时你有任务在进行，那么这个任务会等着，等你做完了才会开始这个任务。
O(n)的模拟，用一个变量记录当前时间res，如果当前任务的分发时间a[i]大于你当前的时间，那么说明我们现在啥事都没有，时间一到就可以接收任务并在b[i]把它完成，那么所用时间就是b[i]-a[i]，并把时间更新到完成任务那一刻。如果当前任务分发时间大于你的当前时间，说明这个任务在分发的时候你在完成其它任务，你在完成上一个任务后立刻接收这个任务，并且还是在b[i]时完成了它，所以你完成这个任务所用时间是b[i]-res，并把时间更新到完成任务那一刻。
AC代码
#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 = 1e3 + 50;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
string s;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int>a(n), b(n);
for (int i = 0; i < n; i++)cin >> a[i];
for (int i = 0; i < n; i++)cin >> b[i];
int res = a[0];
for (int i = 0; i < n; i++)
{
if (res <= a[i])
{
cout << b[i] - a[i] << " ";
res = b[i];
}
else
{
cout << b[i] - res << " ";
res = b[i];
}
}
cout << endl;
}
return 0;
}
Problem - D - Codeforces
You have a stripe of checkered paper of length n. Each cell is either white or black.
What is the minimum number of cells that must be recolored from white to black in order to have a segment of k consecutive black cells on the stripe?
If the input data is such that a segment of k consecutive black cells already exists, then print 0.
Input
The first line contains an integer t (1≤t≤104) — the number of test cases.
Next, descriptions of t test cases follow.
The first line of the input contains two integers n and k (1≤k≤n≤2?10^5). The second line consists of the letters ‘W’ (white) and ‘B’ (black). The line length is n.
It is guaranteed that the sum of values n does not exceed 2?10^5.
Output
For each of t test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of k consecutive black cells.
Example
input
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
output
1
2
0
1
问题解析
题目是说给你一个只由‘B’和‘W’组成的字符串，你每次可以选一个’W’变成‘B’，问你要使得这个字符串有个长度为k的子串全由’B’组成，最少要进行多少次操作。
这里我用的是前缀和（也可以用滑动窗口），先预处理个前缀和数组，‘W’当作0，‘B’当作1来计算前缀和，然后计算长度为k的区间，区间和为多少就说明我们要进行多少次操作，维护一下最小值即可。
AC代码
#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;
int n, m;
string s;
int sum[N];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
cin >> s;
for (int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + (s[i - 1] == 'W' ? 1 : 0);
}
int res=1e9;
for (int i = m; i <= n; i++)
{
res=min(res,sum[i]-sum[i-m]);
}
cout<<res<<endl;
}
return 0;
}
Problem - E - Codeforces
A batch of n goods (n — an even number) is brought to the store, i-th of which has weight ai. Before selling the goods, they must be packed into packages. After packing, the following will be done:
There will be n/2 packages, each package contains exactly two goods;
The weight of the package that contains goods with indices i and j (1≤i,j≤n) is ai+aj.
With this, the cost of a package of weight x is always ?x/k? burles (rounded down), where k — a fixed and given value.
Pack the goods to the packages so that the revenue from their sale is maximized. In other words, make such n2 pairs of given goods that the sum of the values ?xik?, where xi is the weight of the package number i (1≤i≤n2), is maximal.
For example, let n=6,k=3, weights of goods a=[3,2,7,1,4,8]. Let’s pack them into the following packages.
In the first package we will put the third and sixth goods. Its weight will be a3+a6=7+8=15. The cost of the package will be ?153?=5 burles.
In the second package put the first and fifth goods, the weight is a1+a5=3+4=7. The cost of the package is ?7/3?=2 burles.
In the third package put the second and fourth goods, the weight is a2+a4=2+1=3. The cost of the package is ?3/3?=1 burle.
With this packing, the total cost of all packs would be 5+2+1=8 burles.
Input
The first line of the input contains an integer t (1≤t≤104) —the number of test cases in the test.
The descriptions of the test cases follow.
The first line of each test case contains two integers n (2≤n≤2?10^5) and k (1≤k≤1000). The number n — is even.
The second line of each test case contains exactly n integers a1,a2,…,an (0≤ai≤10^9).
It is guaranteed that the sum of n over all the test cases does not exceed 2?10^5.
Output
For each test case, print on a separate line a single number — the maximum possible total cost of all the packages.
Example
input
6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2
output
8
4
0
2
1
5
问题解析
题目是说有n个货物，每个货物重量ki，再给个数k，你要把他们两两打包起来，打包获得的利益是这两个货物的重量之和除于k，求最大的利益是多少。
首先，既然是重量之和除于k得到的是我们的利益，那么单个货物重量除于k的利益就是我们必得的部分，我们可以先计算出单个物品能获得的利益。要想两两组合增加新的利益，那就应该让这两个货物对k的余数相加大于等于k，这样就可以多获得一点利益。那么我们就可以在计算单个货物利益时，把他们变成%k。再从小到大排个序，用双指针头尾向中间推进，如果当前的最小值+最大值的和不能大于等于k，那就去找一个稍大一点的最小值，当他俩之和大于等于k后，我们头指针和尾指针都向中间走一步，同时利益++。
因为当前所有货物重量都是k的余数了，所以两个货物最大能获得的能量只能是1，达不到2的，所以这么解是可以得到最大利益的。
AC代码
#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;
int n, m;
string s;
bool cmp2(PII a, PII b)
{
if (a.first > b.first)return true;
else if (a.first < b.first)return false;
return a.second < b.second;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int res = 0;
cin >> n >> m;
vector<ll>v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
res += v[i] / m;
v[i] %= m;
}
sort(v.begin(), v.end());
int l = 0, r = n - 1;
while (l < r)
{
if (v[l] + v[r] < m)l++;
else
{
res++;
r--;
l++;
}
}
cout << res << endl;
}
return 0;
}
Problem - G - Codeforces
There are n of independent carriages on the rails. The carriages are numbered from left to right from 1 to n. The carriages are not connected to each other. The carriages move to the left, so that the carriage with number 1 moves ahead of all of them.
The i-th carriage has its own engine, which can accelerate the carriage to ai km/h, but the carriage cannot go faster than the carriage in front of it. See example for explanation.
All carriages start moving to the left at the same time, and they naturally form trains. We will call trains — consecutive moving carriages having the same speed.
For example, we have n=5 carriages and array a=[10,13,5,2,6]. Then the final speeds of the carriages will be [10,10,5,2,2]. Respectively, 3 of the train will be formed.
There are also messages saying that some engine has been corrupted:
message “k d” means that the speed of the k-th carriage has decreased by d (that is, there has been a change in the maximum speed of the carriage ak=ak?d).
Messages arrive sequentially, the processing of the next message takes into account the changes from all previous messages.
After each message determine the number of formed trains.
Input
The first line of input data contains a single integer t (1≤t≤104) —the number of input test cases.
This is followed by descriptions of the test cases.
The first line of each test case is empty.
The second line of the test case contains two integers n and m (1≤n,m≤105) —the number of carriages and the number of messages to slow down the carriage, respectively.
The third line contains n integers: a1,a2,…,an (0≤ai≤109) — the number ai means that the carriage with number i can reach a speed of ai km/h.
The next m lines contain two integers kj and dj (1≤kj≤n, 0≤dj≤akj) —this is the message that the speed of the carriage with number kj has decreased by dj. In other words, there has been a change in its maximum speed akj=akj?dj. Note that at any time the speed of each carriage is non-negative. In other words, ai≥si, where si —is the sum of such dj that kj=i.
It is guaranteed that the sum of n over all test cases does not exceed 105. Similarly, it is guaranteed that the sum of m over all test cases does not exceed 105.
Output
Print t lines. On each line print the answer for the corresponding test case.
For each test case print m numbers: the number of trains formed after each message.
Example
input
3
4 2
6 2 3 7
3 2
4 7
5 4
10 13 5 2 6
2 4
5 2
1 5
3 2
13 4
769 514 336 173 181 373 519 338 985 709 729 702 168
12 581
6 222
7 233
5 117
output
3 4
4 4 2 3
5 6 6 5
问题解析
这题是说一开始有n个车厢，开动后他们会以a[i]km/h的速度向左走，右边的会跟在左边速度慢的车后面连成一整个车厢。然后有k次操作，每次会把第x个车厢的初始速度调慢y，问开动后列车一共会形成几个车厢。
首先可以知道，右边的会跟在前面速度慢的后面，比如样例的：10,13,5,2,6，就会变成10,10,5,2,2，一共是三节车厢。经过第一次操作后第二节车厢的初始速度减少了4，就变成：10,9,5,2,6，这样开动后就会变成：10,9,5,2,2。如果第二个车厢的速度变的比后面还慢，比如：10,4,5,2,6，那最后就会是10,4,4,2,2。也就是说我们我们需要一个能很快找到对应位置的车厢，而且能合并后面速度比它快的车厢的数据结构，这里我用的是map，以车厢的编号（下标）做key，车厢的速度做val。
初始可以先用一个很大的变量做标准，当插入的元素大于这个标准时，我们就不插入map中（当作这个车厢和前面的车厢合并），如果有车厢的速度小于标准，我们把这个车厢插入map中，并且把标准变成当前车厢的速度，这样map的size就是开动后车厢的数量了。
至于降低车厢速度的操作，可以按照下标把这个降低速度后的元素插入map中，再根据find函数找到这个位置的迭代器，再根据prev函数获取这个迭代器前面的迭代器（类似链表一样），以此看前面的车厢速度是否小于我们插入的车厢，如果小于，说明这个车厢即使降了速度也会接到前面的车厢中，那这次降速其实没有任何意义，因为想要降速使得车厢数量改变，则应该始它的速度小于前面的车厢。那么我们就直接把这个新插入的车厢删除即可，然后记录当前map的size，就是车箱数了。
如果降速后这个车厢速度小于前面的车厢，那我们就要持续同化后面的车厢，我们可以用next函数获取当前迭代器的下一个迭代器，然后看后面的车厢速度是否小于我们新插入的车厢，如果小于就把后面这个车厢删除（同化到我们车厢的后面去了），直到后面没有车厢或者后面有速度更慢的车厢为止。之后map的size就是车厢的数量了。
AC代码
#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;
int n, m;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, m, x, y, index = 1e10;
cin >> n >> m;
vector<int>v(n + 1);
map<int, int>mymap;
for (int i = 1; i <= n; i++)
{
cin >> v[i];
if (v[i] < index)mymap[i] = v[i],index=v[i];
}
vector<int>cnt;
while (m--)
{
cin >> x >> y;
v[x] -= y;
mymap[x] = v[x];
auto ans = mymap.find(x);
if (ans != mymap.begin() && (*ans).second >= (*prev(ans)).second)
{
mymap.erase(ans);
cnt.push_back(mymap.size());
continue;
}
while(next(ans)!=mymap.end()&&(*ans).second<=(*next(ans)).second)mymap.erase(next(ans));
cnt.push_back(mymap.size());
}
for (auto i : cnt)cout << i << " ";
cout << endl;
}
return 0;
}