Codeforces Round #798 (Div. 2)A~D

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

问题解析

题目是说，给你两个字符串，可以从一个字符串中选一些字符删除，再把这些字符去组成一个字符串，每次只能从和上一个不同的字符串中选字符（上次选了a，这次就只能选b），而且每次最多只能选k个字符，直到一个字符串为空后结束操作，问组成的字符串字典序最小的结果。

先对两个字符串进行排序，把小的字符都放在前面，双指针遍历两边的字符串，至于从哪个字符串先开始，就看第一个字符谁小，从小的一方开始，如果一样则两边都无所谓先后。在其中一个字符串中选字符的时候要和另一个字符串的字符进行比较，如果小或相等就继续选，如果大了或者选的字符数大于k了就结束。如果第一个选的字符就比另一个字符串的大，那我们只选一个就行（至少要选一个）。

AC代码

#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pairPII;
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 
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
 
问题解析 
题目是说给你一个数组，让你对这个数组重新排序，每个位置上的数不能和之前一样，问这么排字典序最低结果是什么。 
先对数组排序，把小的数都放到前面就行。再依次对比看是否和之前一样，不一样就定下来，一样就在后面的数里找不等于之前位置的数并交换。如果后面的数里没有满足条件的，我们就从定下的数里找不同的数交换（交换过去的数也不能和之前一样），如果还是找不到就说明无法满足，输出-1。 
AC代码 
#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pairPII;
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;
        vectora(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
 
问题解析 
题目是说有一个二叉树，它的根节点被污染了，被污染的节点每次会污染和他直接连接的节点，你每次可以干掉一个没被污染的节点，这样这个节点的子节点就不会被污染了，问你最后可以使得多少多少节点被救下来。 
可以先通过dfs一次求的每个节点的子树有多少节点（相当于把这个节点砍掉能拯救的节点数），顺便把每个节点的左右子节点分类好（一开始的链接不会分出左右子树，要我们自己分）。 
然后就是计算救下的节点了，每次我们可以选择砍掉左边的节点或砍掉右边的节点，如果砍掉左边节点，那左边的节点我们就能全部救下来，然后右边的子树就会被污染，我们就看右子树的两个子树来决定砍掉哪边的节点，即： 
max(dfs(root->left)+size[root->right],dfs(root->right)+size[root->left]); 
AC代码 
#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pairPII;
const int N = 2e5 + 50;
unordered_mapans;
unordered_mapmysize;
unordered_map>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;
        vectorv(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
 
问题解析 
问题是说，有一个矩阵由白点（W）和黑点（B）组成，让你找到一个点，使得这个点到最远的黑点距离最小。 
其实我们就直接找最远的黑点就行了，最远的黑点只有四个，就是左上、坐下、右上、右下这四个方向的点，我们只要找出这四个点，然后枚举所有点到这四个点的最远距离，选最远距离最小的那个点。 
AC代码 
#include
using namespace std;
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define endl 'n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pairPII;
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;
        vectorv(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;
}

Codeforces Round #798 (Div. 2)A~D

C/C++/C#相关栏目本月热门文章