当前位置:网站首页>Codeforces Round #798 (Div. 2)A~D
Codeforces Round #798 (Div. 2)A~D
2022-07-06 16:15:00 【Hello_ Ä】
Codeforces Round #798 (Div. 2)A~D
Problem - A - Codeforces
Kuznecov likes art, poetry, and music. And strings consisting of lowercase English letters.
Recently, Kuznecov has found two strings, a and b, of lengths n and m respectively. They consist of lowercase English letters and no character is contained in both strings.
Let another string c be initially empty. Kuznecov can do the following two types of operations:
Choose any character from the string a, remove it from a, and add it to the end of c.
Choose any character from the string b, remove it from b, and add it to the end of c.
But, he can not do more than k operations of the same type in a row. He must perform operations until either a or b becomes empty. What is the lexicographically smallest possible value of c after he finishes?
A string x is lexicographically smaller than a string y if and only if one of the following holds:
x is a prefix of y, but x≠y;
in the first position where x and y differ, the string x has a letter that appears earlier in the alphabet than the corresponding letter in y.
Input
There are several test cases in the input data. The first line contains a single integer t (1≤t≤100) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains three integers n, m, and k (1≤n,m,k≤100) — parameters from the statement.
The second line of each test case contains the string a of length n.
The third line of each test case contains the string b of length m.
The strings contain only lowercase English letters. It is guaranteed that no symbol appears in a and b simultaneously.
Output
In each test case, output a single string c — the answer to the problem.
Example
input
3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy
output
aabaabaa
aaabbcc
dihktlwlxnyoz
Problem analysis
The title is , Here are two strings , You can select some characters from a string to delete , And then put these characters into a string , You can only select characters from a different string from the previous one at a time ( Last time I chose a, This time I can only choose b), And you can only choose k Characters , End the operation until a string is empty , Ask the result of the smallest lexicographic order of the composed string .
First sort the two strings , Put small characters in front , Double pointers traverse the strings on both sides , As for which string to start with , It depends on who is small in the first character , Start with the small side , If the two sides are the same, there is no priority . When selecting a character in one string, compare it with the character in the other string , If it is small or equal, continue to choose , If it is large or the number of selected characters is greater than k It's over . If the first selected character is larger than the other string , Then let's just choose one ( At least choose one ).
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;
int n, m;
bool cmp(PII a, PII b)
{
return a.first > b.first;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, m, k;
string a, b, c, d;
cin >> n >> m >> k;
cin >> a >> b;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int l = 0, r = 0, st = -1;
if (a[l] < b[r])st = 1;
else st = 2;
while (l < n && r < m)
{
if (st == 1)
{
st = 2;
int ans = 0;
while (l<n&&ans < k && a[l] < b[r])c += a[l++], ans++;
if (ans == 0)c += a[l++];
}
else if (st == 2)
{
st = 1;
int ans = 0;
while (r<m&&ans < k && b[r] < a[l])c += b[r++], ans++;
if (ans == 0)c += b[r++];
}
}
cout << c << endl;
}
return 0;
}
Problem - B - Codeforces
Monocarp is a little boy who lives in Byteland and he loves programming.
Recently, he found a permutation of length n. He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position.
More formally, if the old permutation is p1,p2,…,pn and the new one is q1,q2,…,qn it must hold that
p1≠q1,p2≠q2,…,pn≠qn.
Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?
Input
There are several test cases in the input data. The first line contains a single integer t (1≤t≤200) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains a positive integer n (1≤n≤1000) — the length of the permutation.
The second line of each test case contains n distinct positive integers p1,p2,…,pn (1≤pi≤n). It’s guaranteed that p is a permutation, i. e. pi≠pj for all i≠j.
It is guaranteed that the sum of n does not exceed 1000 over all test cases.
Output
For each test case, output n positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output −1 instead.
Example
input
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
output
2 3 1
1 2 3 4 5
1 2 4 3
-1
Problem analysis
The title is to give you an array , Let you reorder this array , The number in each position cannot be the same as before , What is the lowest result of such a typesetting sequence .
Sort the array first , Just put the small numbers in front . Then compare it in turn to see if it is the same as before , Decide if it's different , Just find the number that is not equal to the previous position in the following number and Exchange . If none of the following numbers meet the conditions , We will exchange different numbers from the set numbers ( The exchange of past numbers cannot be the same as before ), If you still can't find it, it means you can't be satisfied , Output -1.
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;
int n, m;
bool cmp(PII a, PII b)
{
return a.first > b.first;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, res = 0;
cin >> n;
vector<int>a(n), b(n), mymap(n);
for (int i = 0; i < n; i++)cin >> a[i];
bool flag = true;
for (int i = 0; i < n; i++)
{
int ans = 1e9, pos = -1;
for (int j = 0; j < n; j++)
{
if (mymap[j] == 0 && a[i] != a[j])
{
if (ans > a[j])
{
ans = a[j];
pos = j;
}
}
}
if (ans == 1e9)
{
bool st = false;
for (int j = res - 1; j >= 0; j--)
{
if (a[i] != b[j] && a[j] != a[i])
{
b[i] = b[j];
b[j] = a[i];
mymap[i] = 1;
st = true;
break;
}
}
if (!st)
{
flag = false;
break;
}
}
else
{
b[i] = ans, res++;
mymap[pos] = 1;
}
}
if (flag)
{
for (auto i : b)cout << i << " ";
cout << endl;
}
else cout << -1 << endl;
}
return 0;
}
Problem - C - Codeforces
Byteland is a beautiful land known because of its beautiful trees.
Misha has found a binary tree with n vertices, numbered from 1 to n. A binary tree is an acyclic connected bidirectional graph containing n vertices and n−1 edges. Each vertex has a degree at most 3, whereas the root is the vertex with the number 1 and it has a degree at most 2.
Unfortunately, the root got infected.
The following process happens n times:
Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.
Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).
As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).
Input
There are several test cases in the input data. The first line contains a single integer t (1≤t≤5000) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains one integer n (2≤n≤3⋅10^ 5) — the number of vertices of the tree.
The i-th of the following n−1 lines in the test case contains two positive integers ui and vi (1≤ui,vi≤n), meaning that there exists an edge between them in the graph.
It is guaranteed that the graph is a binary tree rooted at 1. It is also guaranteed that the sum of n over all test cases won’t exceed 3⋅10^ 5.
Output
For each test case, output the maximum number of vertices Misha can save.
Example
input
4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
output
0
2
2
10
Problem analysis
The title is that there is a binary tree , Its root node is polluted , Each time a contaminated node pollutes the node directly connected to it , You can kill one uncontaminated node at a time , In this way, the child nodes of this node will not be polluted , Ask how many nodes you can save in the end .
You can go through it first dfs How many nodes does the subtree of each node have at one time ( It is equivalent to cutting down the number of nodes that can be saved ), By the way, classify the left and right child nodes of each node ( At the beginning, the link will not be divided into left and right subtrees , Let's divide by ourselves ).
Then there is the node saved by calculation , Each time we can choose to cut off the left node or the right node , If you cut off the left node , Then we can save all the nodes on the left , Then the subtree on the right will be polluted , Let's look at the two subtrees of the right subtree to decide which side of the node to cut , namely :
max(dfs(root->left)+size[root->right],dfs(root->right)+size[root->left]);
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;
unordered_map<int, PII>ans;
unordered_map<int, int>mysize;
unordered_map<int, vector<int>>mymap;
int dfs(int x,int y)
{
if (x == 0)return 0;
int res = 0, st = 1;
for (auto i : mymap[x])
{
if (i != y)
{
if (st == 1)
{
st = 2;
ans[x].first = i;
res += dfs(i, x);
}
else
{
ans[x].second = i;
res += dfs(i, x);
}
}
}
mysize[x] = res;
return res + 1;
}
int dfs2(int x)
{
if (x == 0)return 0;
int res = 0;
res = max(res, mysize[ans[x].second] + dfs2(ans[x].first));
res = max(res, mysize[ans[x].first] + dfs2(ans[x].second));
return res;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
ans.clear();
mysize.clear();
mymap.clear();
int n, a, b;
cin >> n;
vector<int>v(n);
for (int i = 0; i < n-1; i++)
{
cin >> a >> b;
mymap[a].push_back(b);
mymap[b].push_back(a);
}
int res = 0;
dfs(1, 0);
res=dfs2(1);
cout << res << endl;
}
return 0;
}
Problem - D - Codeforces
Lena is a beautiful girl who likes logical puzzles.
As a gift for her birthday, Lena got a matrix puzzle!
The matrix consists of n rows and m columns, and each cell is either black or white. The coordinates (i,j) denote the cell which belongs to the i-th row and j-th column for every 1≤i≤n and 1≤j≤m. To solve the puzzle, Lena has to choose a cell that minimizes the Manhattan distance to the farthest black cell from the chosen cell.
More formally, let there be k≥1 black cells in the matrix with coordinates (xi,yi) for every 1≤i≤k. Lena should choose a cell (a,b) that minimizes
m a x = ( ∣ a − x i ∣ + ∣ b − y i ∣ ) . max=(|a−xi|+|b−yi|). max=(∣a−xi∣+∣b−yi∣).
As Lena has no skill, she asked you for help. Will you tell her the optimal cell to choose?
Input
There are several test cases in the input data. The first line contains a single integer t (1≤t≤10000) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains two integers n and m (2≤n,m≤1000) — the dimensions of the matrix.
The following n lines contain m characters each, each character is either ‘W’ or ‘B’. The j-th character in the i-th of these lines is ‘W’ if the cell (i,j) is white, and ‘B’ if the cell (i,j) is black.
It is guaranteed that at least one black cell exists.
It is guaranteed that the sum of n⋅m does not exceed 106.
Output
For each test case, output the optimal cell (a,b) to choose. If multiple answers exist, output any.
Example
input
5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB
output
2 1
2 2
1 2
3 3
6 5
Problem analysis
The problem is that , There is a matrix consisting of white dots (W) And black spots (B) form , Let you find a point , Minimize the distance from this point to the farthest black spot .
In fact, we can directly find the farthest black spot , There are only four farthest black spots , It's the top left 、 Sit down 、 The upper right 、 Points in the four directions at the bottom right , We just need to find out these four points , Then enumerate the farthest distance from all points to these four points , Choose the point with the longest distance and the smallest .
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(PII a, PII b)
{
if (a.first != b.first)return a.first < b.first;
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 n, m;
cin >> n >> m;
vector<string>v(n);
PII a = { 1e9,1e9 }, b = { -1,-1 }, c = { 0,1e9 }, d = { 1e9,0 };
for (int i = 0; i < n; i++)
{
cin >> v[i];
for (int j = 0; j < m; j++)
{
if (v[i][j] == 'B')
{
if (i + j <= a.first + a.second)a = { i,j };
if (i + j >= b.first + b.second)b = { i,j };
if (i - j >= c.first - c.second)c = { i,j };
if (i - j <= d.first - d.second)d = { i,j };
}
}
}
int dis = 1e9, x = -1, y = -1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
int res = 0;
res = max(res, abs(i - a.first) + abs(j - a.second));
res = max(res, abs(i - b.first) + abs(j - b.second));
res = max(res, abs(i - c.first) + abs(j - c.second));
res = max(res, abs(i - d.first) + abs(j - d.second));
if (res < dis)
{
dis = res;
x = i;
y = j;
}
}
}
cout << x + 1 << " " << y + 1 << endl;
}
return 0;
}
边栏推荐
- C language must memorize code Encyclopedia
- Openwrt source code generation image
- (POJ - 3579) median (two points)
- 807. Maintain the urban skyline
- Penetration test (3) -- Metasploit framework (MSF)
- D - function (HDU - 6546) girls' competition
- QT实现圆角窗口
- Borg maze (bfs+ minimum spanning tree) (problem solving report)
- Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
- 浏览器打印边距,默认/无边距,占满1页A4
猜你喜欢
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
(POJ - 3579) median (two points)
The "sneaky" new asteroid will pass the earth safely this week: how to watch it
628. Maximum product of three numbers
Maximum product (greedy)
力扣——第298场周赛
2027. Minimum number of operations to convert strings
Penetration test (1) -- necessary tools, navigation
807. Maintain the urban skyline
Determine the Photo Position
随机推荐
指定格式时间,月份天数前补零
AcWing:第56场周赛
(POJ - 2739) sum of constructive prime numbers (ruler or two points)
计算时间差
QNetworkAccessManager实现ftp功能总结
Nodejs crawler
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
Codeforces Round #799 (Div. 4)A~H
第 300 场周赛 - 力扣(LeetCode)
antd upload beforeUpload中禁止触发onchange
Penetration test (7) -- vulnerability scanning tool Nessus
Opencv learning log 29 -- gamma correction
409. Longest palindrome
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
If you want to apply for a programmer, your resume should be written like this [essence summary]
Understand what is a programming language in a popular way
The concept of C language array
input 只能输入数字,限定输入
frida hook so层、protobuf 数据解析