A. Sea Battle

Description:

In order to make the “Sea Battle” game more interesting, Boris decided to add a new ship type to it. The ship consists of two rectangles. The first rectangle has a width of $w_{1}$ and a height of $h_{1}$ , while the second rectangle has a width of $w_{2}$ and a height of $h_{2}$ , where $w_{1} \geq w_{2}$ . In this game, exactly one ship is used, made up of two rectangles. There are no other ships on the field.
The rectangles are placed on field in the following way:

the second rectangle is on top the first rectangle;
they are aligned to the left, i.e. their left sides are on the same line;
the rectangles are adjacent to each other without a gap.

See the pictures in the notes: the first rectangle is colored red, the second rectangle is colored blue.
Formally, let’s introduce a coordinate system. Then, the leftmost bottom cell of the first rectangle has coordinates $(1, 1)$ , the rightmost top cell of the first rectangle has coordinates $(w_{1}, h_{1})$ , the leftmost bottom cell of the second rectangle has coordinates $(1, h_{1} + 1)$ and the rightmost top cell of the second rectangle has coordinates $(w_{2}, h_{1} + h_{2})$ .
After the ship is completely destroyed, all cells neighboring by side or a corner with the ship are marked. Of course, only cells, which don’t belong to the ship are marked. On the pictures in the notes such cells are colored green.
Find out how many cells should be marked after the ship is destroyed. The field of the game is infinite in any direction.

Input:

Four lines contain integers $w_{1}, h_{1}, w_{2}$ and $h_{2}$ ( $1 \leq w_{1}, h_{1}, w_{2}, h_{2} \leq 1 0^{8}$ , $w_{1} \geq w_{2}$ ) — the width of the first rectangle, the height of the first rectangle, the width of the second rectangle and the height of the second rectangle. You can’t rotate the rectangles.

Output

Print exactly one integer — the number of cells, which should be marked after the ship is destroyed.

Sample Input:

2 1 2 1

Sample Output:

Sample Input:

2 2 1 2

Sample Output:

题目链接

两个上下相接的矩形求将其包围的方格数

画几个图数一下规律很显然

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[]) {
    ll w1, h1, w2, h2; cin >> w1 >> h1 >> w2 >> h2;
    ll ans = 0;
    ans += 2 * ((h1 + h2) + 2) + 2 * (max(w1, w2) + 2);
    ans -= 4;
    cout << ans << endl;
    return 0;
}

B. Draw!

Description:

You still have partial information about the score during the historic football match. You are given a set of pairs $(a_{i}, b_{i})$ , indicating that at some point during the match the score was " $a_{i}$ : $b_{i}$ ". It is known that if the current score is « $x$ : $y$ », then after the goal it will change to “ $x + 1$ : $y$ ” or “ $x$ : $y + 1$ ”. What is the largest number of times a draw could appear on the scoreboard?
The pairs “ $a_{i}$ : $b_{i}$ ” are given in chronological order (time increases), but you are given score only for some moments of time. The last pair corresponds to the end of the match.

Input:

The first line contains a single integer $n$ ( $1 \leq n \leq 10000$ ) — the number of known moments in the match.
Each of the next $n$ lines contains integers $a_{i}$ and $b_{i}$ ( $0 \leq a_{i}, b_{i} \leq 1 0^{9}$ ), denoting the score of the match at that moment (that is, the number of goals by the first team and the number of goals by the second team).
All moments are given in chronological order, that is, sequences $x_{i}$ and $y_{j}$ are non-decreasing. The last score denotes the final result of the match.

Output

Print the maximum number of moments of time, during which the score was a draw. The starting moment of the match (with a score 0:0) is also counted.

Sample Input:

3
2 0
3 1
3 4

Sample Output:

Sample Input:

3
0 0
0 0
0 0

Sample Output:

Sample Input:

1
5 4

Sample Output:

题目链接

递增的一对数，每次可以对一个数+1，现每轮需达到指定的数对，求两数相等的最大次数

对每轮游戏的指定数对手动模拟一下

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(int argc, char *argv[]) {
    int n; cin >> n;
    vector<pair<ll, ll>> p(n);
    for (auto &it : p) cin >> it.first >> it.second;
    ll ans = min(p[0].first, p[0].second) + 1;
    cerr << ans << endl;
    pair<ll, ll> cur = p[0];
    for (int i = 1; i < n; ++i) {
        if (p[i] == cur) continue;
        if (cur.first < cur.second) {
            if (p[i].first >= cur.second) {
                ans += min(p[i].first, p[i].second) - cur.second + 1;
            }
        }
        else if (cur.second < cur.first) {
            if (p[i].second >= cur.first) {
                ans += min(p[i].first, p[i].second) - cur.first + 1;
            }
        }
        else if (cur.first == cur.second) {
            ans += min(p[i].first, p[i].second) - cur.first;
        }
        cur = p[i];
        cerr << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

C. Birthday

Description:

Cowboy Vlad has a birthday today! There are $n$ children who came to the celebration. In order to greet Vlad, the children decided to form a circle around him. Among the children who came, there are both tall and low, so if they stand in a circle arbitrarily, it may turn out, that there is a tall and low child standing next to each other, and it will be difficult for them to hold hands. Therefore, children want to stand in a circle so that the maximum difference between the growth of two neighboring children would be minimal possible.
Formally, let’s number children from $1$ to $n$ in a circle order, that is, for every $i$ child with number $i$ will stand next to the child with number $i + 1$ , also the child with number $1$ stands next to the child with number $n$ . Then we will call the discomfort of the circle the maximum absolute difference of heights of the children, who stand next to each other.
Please help children to find out how they should reorder themselves, so that the resulting discomfort is smallest possible.

Input:

The first line contains a single integer $n$ ( $2 \leq n \leq 100$ ) — the number of the children who came to the cowboy Vlad’s birthday.
The second line contains integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 1 0^{9}$ ) denoting heights of every child.

Output

Print exactly $n$ integers — heights of the children in the order in which they should stand in a circle. You can start printing a circle with any child.
If there are multiple possible answers, print any of them.

Sample Input:

5
2 1 1 3 2

Sample Output:

1 2 3 2 1

Sample Input:

3
30 10 20

Sample Output:

10 20 30

题目链接

每个人有个高度（身高），现将他们排成圈，求排列后的最小最大相邻身高差

一个人的身边肯定选身高和其相近的人站，所以排序后用双向队列左右依次添加（就是把最低的人放中间然后左右依次排）

AC代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int n; cin >> n;
    vector<int> a(n);
    for (auto &it : a) cin >> it;
    sort(a.begin(), a.end());
    deque<int> Deq;
    bool Flag = true;
    for (auto &it : a) {
        if (Flag) Deq.push_back(it);
        else Deq.push_front(it);
        Flag = !Flag;
    }
    for (auto &it : Deq) cout << it << " ";
    return 0;
}

D. Gourmet choice

Description:

Mr. Apple, a gourmet, works as editor-in-chief of a gastronomic periodical. He travels around the world, tasting new delights of famous chefs from the most fashionable restaurants. Mr. Apple has his own signature method of review — in each restaurant Mr. Apple orders two sets of dishes on two different days. All the dishes are different, because Mr. Apple doesn’t like to eat the same food. For each pair of dishes from different days he remembers exactly which was better, or that they were of the same quality. After this the gourmet evaluates each dish with a positive integer.
Once, during a revision of a restaurant of Celtic medieval cuisine named «Poisson», that serves chestnut soup with fir, warm soda bread, spicy lemon pie and other folk food, Mr. Apple was very pleasantly surprised the gourmet with its variety of menu, and hence ordered too much. Now he’s confused about evaluating dishes.
The gourmet tasted a set of $n$ dishes on the first day and a set of $m$ dishes on the second day. He made a table $a$ of size $n \times m$ , in which he described his impressions. If, according to the expert, dish $i$ from the first set was better than dish $j$ from the second set, then $a_{i j}$ is equal to “>”, in the opposite case $a_{i j}$ is equal to “<”. Dishes also may be equally good, in this case $a_{i j}$ is “=”.
Now Mr. Apple wants you to help him to evaluate every dish. Since Mr. Apple is very strict, he will evaluate the dishes so that the maximal number used is as small as possible. But Mr. Apple also is very fair, so he never evaluates the dishes so that it goes against his feelings. In other words, if $a_{i j}$ is “<”, then the number assigned to dish $i$ from the first set should be less than the number of dish $j$ from the second set, if $a_{i j}$ is “>”, then it should be greater, and finally if $a_{i j}$ is “=”, then the numbers should be the same.
Help Mr. Apple to evaluate each dish from both sets so that it is consistent with his feelings, or determine that this is impossible.

Input:

The first line contains integers $n$ and $m$ ( $1 \leq n, m \leq 1000$ ) — the number of dishes in both days.
Each of the next $n$ lines contains a string of $m$ symbols. The $j$ -th symbol on $i$ -th line is $a_{i j}$ . All strings consist only of “<”, “>” and “=”.

Output

The first line of output should contain “Yes”, if it’s possible to do a correct evaluation for all the dishes, or “No” otherwise.
If case an answer exist, on the second line print $n$ integers — evaluations of dishes from the first set, and on the third line print $m$ integers — evaluations of dishes from the second set.

Sample Input:

3 4
>>>>
>>>>
>>>>

Sample Output:

Yes
2 2 2
1 1 1 1

Sample Input:

3 3
>>>
<<<
>>>

Sample Output:

Yes
3 1 3
2 2 2

Sample Input:

3 2
==
=<
==

Sample Output:

题目链接

有两个数列，给出第一个数列对于第二个数列每个数的大小关系，求两个数列的可能情况

这道题目首先肯定要先把所有相等的数缩到一个数上（利用并查集），之后按照大小关系排序，从小到大依次填数（利用拓扑排序）就好了

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;

int Pre[maxn];
int Find(int Key) {return Pre[Key] == Key ? Key : Pre[Key] = Find(Pre[Key]);}
void Union(int Key1, int Key2) {Pre[Find(Key1)] = Find(Key2);}

int N, M;
string G[maxn];
set<int> R[maxn];
int Deg[maxn];
set<int> Vis;
map<int, int> Ans;
bool Flag;
vector<int> Temp;

void TopoSort() {
    queue<int> Que;
    for (int i = 0; i < N + M; ++i) {
        if (Vis.find(Find(i)) != Vis.end()) continue;
        if (Deg[Find(i)] == 0) {
            Que.push(Find(i));
            Vis.insert(Find(i));
        }
    }
    int Cur = 1;
    while (!Que.empty()) {
        Temp.clear();
        while (!Que.empty()) {
            Temp.push_back(Que.front());
            Que.pop();
        }
        for (auto &i : Temp) {
            Ans[i] = Cur;
            for (auto &j : R[i]) {
                if (Vis.find(j) != Vis.end()) continue;
                Deg[j]--;
                if (Deg[j] == 0) {
                    Que.push(j);
                    Vis.insert(j);
                }
            }
        }
        Cur++;
    }
}

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Flag = true;
    cin >> N >> M;
    for (int i = 0; i < N + M; ++i) Pre[i] = i;
    for (int i = 0; i < N; ++i) {
        cin >> G[i];
        for (int j = 0; j < M; ++j)
            if (G[i][j] == '=')
                if (Find(i) != Find(N + j))
                    Union(i, N + j);
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (G[i][j] == '=') continue;
            int X = Find(i), Y = Find(N + j);
            if (X == Y) Flag = false;
            if (G[i][j] == '>') swap(X, Y);
            if (R[X].find(Y) == R[X].end()) {
                R[X].insert(Y);
                Deg[Y]++;
            }
        }
    }
    if (!Flag) {
        cout << "No" << endl;
        return 0;
    }
    TopoSort();
    for (int i = 0; i < N + M; ++i)
        if (Ans[Find(i)] == 0)
            Flag = false;
    if (Flag) {
        cout << "Yes" << endl;
        for (int i = 0; i < N; ++i) cout << Ans[Find(i)] << " ";
        cout << endl;
        for (int i = N; i < N + M; ++i) cout << Ans[Find(i)] << " ";
        cout << endl;
    }
    else cout << "No" << endl;
    return 0;
}

F. Asya And Kittens

Description:

Asya loves animals very much. Recently, she purchased $n$ kittens, enumerated them from $1$ and $n$ and then put them into the cage. The cage consists of one row of $n$ cells, enumerated with integers from $1$ to $n$ from left to right. Adjacent cells had a partially transparent partition wall between them, hence there were $n - 1$ partitions originally. Initially, each cell contained exactly one kitten with some number.
Observing the kittens, Asya noticed, that they are very friendly and often a pair of kittens in neighboring cells wants to play together. So Asya started to remove partitions between neighboring cells. In particular, on the day $i$ , Asya:

Noticed, that the kittens $x_{i}$ and $y_{i}$ , located in neighboring cells want to play together.
Removed the partition between these two cells, efficiently creating a single cell, having all kittens from two original cells.

Since Asya has never putted partitions back, after $n - 1$ days the cage contained a single cell, having all kittens.
For every day, Asya remembers numbers of kittens $x_{i}$ and $y_{i}$ , who wanted to play together, however she doesn’t remember how she placed kittens in the cage in the beginning. Please help her and find any possible initial arrangement of the kittens into $n$ cells.

Input:

The first line contains a single integer $n$ ( $2 \leq n \leq 150 000$ ) — the number of kittens.
Each of the following $n - 1$ lines contains integers $x_{i}$ and $y_{i}$ ( $1 \leq x_{i}, y_{i} \leq n$ , $x_{i} \neq y_{i}$ ) — indices of kittens, which got together due to the border removal on the corresponding day.
It’s guaranteed, that the kittens $x_{i}$ and $y_{i}$ were in the different cells before this day.

Output

For every cell from $1$ to $n$ print a single integer — the index of the kitten from $1$ to $n$ , who was originally in it.
All printed integers must be distinct.
It’s guaranteed, that there is at least one answer possible. In case there are multiple possible answers, print any of them.

Sample Input:

5
1 4
2 5
3 1
4 5

Sample Output:

3 1 4 2 5

题目链接

一串数列，每个数是单独的一块，现给出 $n - 1$ 次并查集操作，求原始数列

显然把每个并查集用链表存储起来，之后并查集合并的时候进行链表合并即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int Pre[maxn];
int Find(int Key) {return Pre[Key] == Key ? Key : Pre[Key] = Find(Pre[Key]);}
void Union(int Key1, int Key2) {Pre[Find(Key2)] = Find(Key1);}

int N;
list<int> L[maxn];

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) Pre[i] = i;
    for (int i = 1; i <= N; ++i) L[i].push_back(i);
    for (int i = 1, U, V; i < N; ++i) {
        scanf("%d%d", &U, &V);
        L[Find(U)].splice(L[Find(U)].end(), L[Find(V)]);
        Union(U, V);
    }
    for (auto &it : L[Find(1)]) printf("%d ", it);
    printf("\n");
    return 0;
}

Codeforces Round #541 (Div. 2)

A. Sea Battle

Description:

Input:

Output

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

B. Draw!

Description:

Input:

Output

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

C. Birthday

Description:

Input:

Output

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

D. Gourmet choice

Description:

Input:

Output

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

F. Asya And Kittens

Description:

Input:

Output

Sample Input:

Sample Output:

题目链接

AC代码: