2019-08-08 17:55 已编辑苏州大学算法工程师

关注

Technocup 2019 - Elimination Round 4

A. Right-Left Cipher

Description:

Polycarp loves ciphers. He has invented his own cipher called Right-Left.
Right-Left cipher is used for strings. To encrypt the string $s = s_{1} s_{2} \dots s_{n}$ Polycarp uses the following algorithm:

he writes down $s_{1}$ ,
he appends the current word with $s_{2}$ (i.e. writes down $s_{2}$ to the right of the current result),
he prepends the current word with $s_{3}$ (i.e. writes down $s_{3}$ to the left of the current result),
he appends the current word with $s_{4}$ (i.e. writes down $s_{4}$ to the right of the current result),
he prepends the current word with $s_{5}$ (i.e. writes down $s_{5}$ to the left of the current result),
and so on for each position until the end of $s$ .

For example, if $s$ =“techno” the process is: “t” $\to$ “te” $\to$ “cte” $\to$ “cteh” $\to$ “ncteh” $\to$ “ncteho”. So the encrypted $s$ =“techno” is “ncteho”.

Given string $t$ — the result of encryption of some string $s$ . Your task is to decrypt it, i.e. find the string $s$ .

Input:

The only line of the input contains $t$ — the result of encryption of some string $s$ . It contains only lowercase Latin letters. The length of $t$ is between $1$ and $50$ , inclusive.

Output:

Print such string $s$ that after encryption it equals $t$ .

Sample Input:

ncteho

Sample Output:

techno

Sample Input:

erfdcoeocs

Sample Output:

codeforces

Sample Input:

Sample Output:

题目链接

将一个字符串左右依次放置重新排序，输出原始字符串。

左右依次取字符串压栈，最后从栈输出即可。

AC代码:

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

string Str;
int Len;
int Left, Right;
stack<char> S;

int main(int argc, char *argv[]) {
    cin >> Str;
    Len = (int)Str.length();
    Left = 0, Right = Len - 1;
    if (Len & 1) {
        S.push(Str[Left++]);
    }
    while (Left < Right) {
        S.push(Str[Right--]);
        if (Right < Left) {
            break;
        }
        S.push(Str[Left++]);
    }
    while (!S.empty()) {
        cout << S.top();
        S.pop();
    }
    cout << endl;
    return 0;
}

B. Div Times Mod

Description:

Vasya likes to solve equations. Today he wants to solve $(x <mtext> </mtext> d i v <mtext> </mtext> k) \cdot (x &VeryThinSpace; m o d &VeryThinSpace; k) = n$ , where $d i v$ and $m o d$ stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, $k$ and $n$ are positive integer parameters, and $x$ is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible $x$ . Can you help him?

Input:

The first line contains two integers $n$ and $k$ ( $1 \leq n \leq 1 0^{6}$ , $2 \leq k \leq 1000$ ).

Output:

Print a single integer $x$ — the smallest positive integer solution to $(x <mtext> </mtext> d i v <mtext> </mtext> k) \cdot (x &VeryThinSpace; m o d &VeryThinSpace; k) = n$ . It is guaranteed that this equation has at least one positive integer solution.

Sample Input:

6 3

Sample Output:

Sample Input:

1 2

Sample Output:

Sample Input:

4 6

Sample Output:

题目链接

寻找最小x使 $⌊ \frac{x}{k} ⌋ \times (x % k) = n$ 。

枚举数x%k（1~k），判断取最小值即可。

AC代码:

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

const int INF = 0x3f3f3f3f;

int N, K;
int Ans;

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &K);
    Ans = INF;
    for (int i = 1; i <= K; ++i) {
        if (N % i == 0) {
            int Temp = N / i;
            int X = Temp * K + i;
            if ((X / K) * (X % K) == N) {
                Ans = min(Ans, X);
            }
        }
    }
    printf("%d\n", Ans);
    return 0;
}

C. Connect Three

Description:

The Squareland national forest is divided into equal $1 \times 1$ square plots aligned with north-south and east-west directions. Each plot can be uniquely described by integer Cartesian coordinates $(x, y)$ of its south-west corner.
Three friends, Alice, Bob, and Charlie are going to buy three distinct plots of land $A, B, C$ in the forest. Initially, all plots in the forest (including the plots $A, B, C$ ) are covered by trees. The friends want to visit each other, so they want to clean some of the plots from trees. After cleaning, one should be able to reach any of the plots $A, B, C$ from any other one of those by moving through adjacent cleared plots. Two plots are adjacent if they share a side.

For example, $A = (0, 0)$ , $B = (1, 1)$ , $C = (2, 2)$ . The minimal number of plots to be cleared is $5$ . One of the ways to do it is shown with the gray color. Of course, the friends don’t want to strain too much. Help them find out the smallest number of plots they need to clean from trees.

Input:

The first line contains two integers $x_{A}$ and $y_{A}$ — coordinates of the plot $A$ ( $0 \leq x_{A}, y_{A} \leq 1000$ ). The following two lines describe coordinates $(x_{B}, y_{B})$ and $(x_{C}, y_{C})$ of plots $B$ and $C$ respectively in the same format ( $0 \leq x_{B}, y_{B}, x_{C}, y_{C} \leq 1000$ ). It is guaranteed that all three plots are distinct.

Output:

On the first line print a single integer $k$ — the smallest number of plots needed to be cleaned from trees. The following $k$ lines should contain coordinates of all plots needed to be cleaned. All $k$ plots should be distinct. You can output the plots in any order.
If there are multiple solutions, print any of them.

Sample Input:

0 0
1 1
2 2

Sample Output:

5
0 0
1 0
1 1
1 2
2 2

Sample Input:

0 0
2 0
1 1

Sample Output:

4
0 0
1 0
1 1
2 0

Hint:

The first example is shown on the picture in the legend.

The second example is illustrated with the following image:

题目链接

用最少的单元格打通三个单元格。

最左最右（或者也可以最上最下）的单元格往中间单元格找路径即可，去重相同单元格。

AC代码:

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

struct Point {
    int X, Y;

    void Input() {
        scanf("%d%d", &X, &Y);
    }

    void Output() {
        printf("(%d,%d)\n", X, Y);
    }

    bool operator < (const Point &B) const {
        return X < B.X;
    }
};

Point points[3];
int Ans;
int NX, NY;
set<pair<int, int> > S;

void Solve(int &Origin, int Target, int Other, bool Flag) {
    if (Target > Origin) {
        for (int i = Origin; i <= Target; ++i) {
            if (Flag) {
                if(S.find(make_pair(i, Other)) == S.end()) {
                    S.insert(make_pair(i, Other));
                }
                Origin = i;
            }
            else {
                if (S.find(make_pair(Other, i)) == S.end()) {
                    S.insert(make_pair(Other, i));
                }
                Origin = i;
            }
        }
    }
    else {
        for (int i = Origin; i >= Target; --i) {
            if (Flag) {
                if (S.find(make_pair(i, Other)) == S.end()) {
                    S.insert(make_pair(i, Other));
                }
                Origin = i;
            }
            else {
                if (S.find(make_pair(Other, i)) == S.end()) {
                    S.insert(make_pair(Other, i));
                }
                Origin = i;
            }
        }
    }
}

int main(int argc, char *argv[]) {
    for (int i = 0; i < 3; ++i) {
        points[i].Input();
    }
    sort(points, points + 3);
    S.clear();
    Solve(points[0].X, points[1].X, points[0].Y, true);
    Solve(points[2].X, points[1].X, points[2].Y, true);
    Solve(points[0].Y, points[1].Y, points[0].X, false);
    Solve(points[2].Y, points[1].Y, points[2].X, false);
    printf("%d\n", (int)S.size());
    for (auto i : S) {
        printf("%d %d\n", i.first, i.second);
    }
    return 0;
}

D. Minimum Diameter Tree

Description:

You are given a tree (an undirected connected graph without cycles) and an integer $s$ .
Vanya wants to put weights on all edges of the tree so that all weights are non-negative real numbers and their sum is $s$ . At the same time, he wants to make the diameter of the tree as small as possible.
Let’s define the diameter of a weighed tree as the maximum sum of the weights of the edges lying on the path between two some vertices of the tree. In other words, the diameter of a weighed tree is the length of the longest simple path in the tree, where length of a path is equal to the sum of weights over all edges in the path.
Find the minimum possible diameter that Vanya can get.

Input:

The first line contains two integer numbers $n$ and $s$ ( $2 \leq n \leq 1 0^{5}$ , $1 \leq s \leq 1 0^{9}$ ) — the number of vertices in the tree and the sum of edge weights.
Each of the following $n - 1$ lines contains two space-separated integer numbers $a_{i}$ and $b_{i}$ ( $1 \leq a_{i}, b_{i} \leq n$ , $a_{i} \neq b_{i}$ ) — the indexes of vertices connected by an edge. The edges are undirected.
It is guaranteed that the given edges form a tree.

Output:

Print the minimum diameter of the tree that Vanya can get by placing some non-negative real weights on its edges with the sum equal to $s$ .
Your answer will be considered correct if its absolute or relative error does not exceed $1 0^{- 6}$ .
Formally, let your answer be $a$ , and the jury’s answer be $b$ . Your answer is considered correct if $\frac{∣ a - b ∣}{m a x (1, b)} \leq 1 0^{- 6}$ .

Sample Input:

4 3
1 2
1 3
1 4

Sample Output:

2.000000000000000000

Sample Input:

6 1
2 1
2 3
2 5
5 4
5 6

Sample Output:

0.500000000000000000

Sample Input:

5 5
1 2
2 3
3 4
3 5

Sample Output:

3.333333333333333333

题目链接

分配权值使树上直径权值之和最小。

权值只用平分在树叶的边上即可，最后结果即为平分值的二倍（仅有两个顶点一条边的树同样成立）。

AC代码:

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

const int maxn = 1e5 + 5;

int N, S;
int Cnt[maxn];
int Ans;

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &S);
    memset(Cnt, 0, sizeof(Cnt));
    for (int i = 1, U, V; i < N; ++i) {
        scanf("%d%d", &U, &V);
        Cnt[U]++;
        Cnt[V]++;
    }
    for (int i = 1; i <= N; ++i) {
        if (Cnt[i] == 1) {
            Ans++;
        }
    }
    printf("%.18lf\n", (double)S / (double)(Ans) * 2.0);
    return 0;
}