A. Repeating Cipher

Description:

Polycarp loves ciphers. He has invented his own cipher called repeating.
Repeating cipher is used for strings. To encrypt the string $s=s_1{s}_2\dots s_m$s=s1​s2​…sm​ ( $1\le m\le 10$1≤m≤10), Polycarp uses the following algorithm:

• he writes down $s_1$s1​ ones,
• he writes down $s_2$s2​ twice,
• he writes down $s_3$s3​ three times, … he writes down $s_m$sm​ $m$m times.

For example, if $s$s=“bab” the process is: “b” $\to$→ “baa” $\to$→ “baabbb”. So the encrypted $s$s=“bab” is “baabbb”.

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

Input:

The first line contains integer $n$n ( $1\le n\le 55$1≤n≤55) — the length of the encrypted string. The second line of the input contains $t$t — the result of encryption of some string $s$s. It contains only lowercase Latin letters. The length of $t$t is exactly $n$n.
It is guaranteed that the answer to the test exists.

Output:

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

Sample Input:

6
baabbb

Sample Output:

bab

Sample Input:

10
ooopppssss

Sample Output:

oops

Sample Input:

1
z

Sample Output:

z

题目链接

将字符串第 $i$i 个字符写 $i$i 次构成新字符串，求原字符串。

每 $i$i 个字符提取一个字符即可。

AC代码:

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

int T;
int Cnt;
string Str;
string Ans;

int main(int argc, char *argv[]) {
    cin >> T >> Str;
    Cnt = 1;
    for (int i = 1; Cnt <= T; ++i) {
        Ans += Str[Cnt - 1];
        Cnt += i;
    }
    cout << Ans << endl;
    return 0;
}

B. Array Stabilization

Description:

You are given an array $a$a consisting of $n$n integer numbers.
Let instability of the array be the following value: ${\max }_{}^{i=1}{a}_i-{\min }_{}^{i=1}{a}_i$i=1maxn​ai​−i=1minn​ai​.
You have to remove exactly one element from this array to minimize instability of the resulting $(n-1)$(n−1)-elements array. Your task is to calculate the minimum possible instability.

Input:

The first line of the input contains one integer $n$n ( $2\le n\le 10^5$2≤n≤105) — the number of elements in the array $a$a.
The second line of the input contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $1\le a_i\le 10^5$1≤ai​≤105) — elements of the array $a$a.

Output:

Print one integer — the minimum possible instability of the array if you have to remove exactly one element from the array $a$a.

Sample Input:

4
1 3 3 7

Sample Output:

2

Sample Input:

2
1 100000

Sample Output:

0

题目链接

在数列中删去一个数字使数列最大值与最小值之差最小。

显然删去最大值或者最小值。

AC代码:

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

const int maxn = 1e5 + 5;

int N;
int Ans;
int Array[maxn];

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &Array[i]);
    }
    sort(Array + 1, Array + N + 1);
    Ans = min(Array[N - 1] - Array[1], Array[N] - Array[2]);
    printf("%d\n", Ans);
    return 0;
}

C. Powers Of Two

Description:

A positive integer $x$x is called a power of two if it can be represented as $x=2^y$x=2y, where $y$y is a non-negative integer. So, the powers of two are $1,2,4,8,16,\dots$1,2,4,8,16,….
You are given two positive integers $n$n and $k$k. Your task is to represent $n$n as the sum of exactly $k$k powers of two.

Input:

The only line of the input contains two integers $n$n and $k$k ( $1\le n\le 10^9$1≤n≤109, $1\le k\le 2\cdot 10^5$1≤k≤2⋅105).

Output:

If it is impossible to represent $n$n as the sum of $k$k powers of two, print NO.
Otherwise, print YES, and then print $k$k positive integers $b_1,b_2,\dots ,b_k$b1​,b2​,…,bk​ such that each of $b_i$bi​ is a power of two, and ${\sum }_{i=1}^k{b}_i=n$i=1∑k​bi​=n. If there are multiple answers, you may print any of them.

Sample Input:

9 4

Sample Output:

YES
1 2 2 4

Sample Input:

8 1

Sample Output:

YES
8

Sample Input:

5 1

Sample Output:

NO

Sample Input:

3 7

Sample Output:

NO

题目链接

用 $k$k 个 $2^x$2x 数组成和为 $n$n ，输出 $k$k 个数。

对的 $2^x(x\in [0,30\left]\right)$2x(x∈[0,30]) 打表，之后在表中对 $n$n 从第一个小于等于 $2^x$2x 开始依次递减查找凑数即可。

AC代码:

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

long long N, K;

long long Data[31];
vector<long long> Ans;

int main(int argc, char *argv[]) {
    for (int i = 0; i < 31; ++i) {
        Data[i] = (1 << i);
    }
    scanf("%lld%lld", &N, &K);
    if (K > N) {
        printf("NO\n");
        return 0;
    }
    else if (K == N) {
        printf("YES\n");
        for (int i = 1; i <= N; ++i) {
            printf("1 ");
        }
        printf("\n");
        return 0;
    }
    int Index = lower_bound(Data, Data + 31, N) - Data;
    Ans.clear();
    for (int i = Index; i >= 0; --i) {
        while (N - Data[i] >= K - 1 && K >= 1 && N > 0) {
            Ans.push_back(Data[i]);
            N -= Data[i];
            K--;
        }
        if (N == 0 || N < K || K == 0) {
            break;
        }
    }
    if (N == 0 && K == 0) {
        printf("YES\n");
        sort(Ans.begin(), Ans.end());
        for (auto i : Ans) {
            printf("%lld ", i);
        }
    }
    else {
        printf("NO");
    }
    printf("\n");
    return 0;
}

D. Circular Dance

Description:

There are $n$n kids, numbered from $1$1 to $n$n, dancing in a circle around the Christmas tree. Let’s enumerate them in a clockwise direction as $p_1$p1​, $p_2$p2​, …, $p_n$pn​ (all these numbers are from $1$1 to $n$n and are distinct, so $p$p is a permutation). Let the next kid for a kid $p_i$pi​ be kid $p_{i+1}$pi+1​ if $i\&lt;n$i<n and $p_1$p1​ otherwise. After the dance, each kid remembered two kids: the next kid (let’s call him $x$x) and the next kid for $x$x. Each kid told you which kids he/she remembered: the kid $i$i remembered kids $a_{i,1}$ai,1​ and $a_{i,2}$ai,2​. However, the order of $a_{i,1}$ai,1​ and $a_{i,2}$ai,2​ can differ from their order in the circle.
Example: 5 kids in a circle, $p=[3,2,4,1,5]$p=[3,2,4,1,5] (or any cyclic shift). The information kids remembered is: $a_{1,1}=3$a1,1​=3, $a_{1,2}=5$a1,2​=5; $a_{2,1}=1$a2,1​=1, $a_{2,2}=4$a2,2​=4; $a_{3,1}=2$a3,1​=2, $a_{3,2}=4$a3,2​=4; $a_{4,1}=1$a4,1​=1, $a_{4,2}=5$a4,2​=5; $a_{5,1}=2$a5,1​=2, $a_{5,2}=3$a5,2​=3. You have to restore the order of the kids in the circle using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input:

The first line of the input contains one integer $n$n ( $3\le n\le 2\cdot 10^5$3≤n≤2⋅105) — the number of the kids.
The next $n$n lines contain $2$2 integers each. The $i$i-th line contains two integers $a_{i,1}$ai,1​ and $a_{i,2}$ai,2​ ( $1\le a_{i,1},a_{i,2}\le n,a_{i,1}\ne a_{i,2}$1≤ai,1​,ai,2​≤n,ai,1​̸​=ai,2​) — the kids the $i$i-th kid remembered, given in arbitrary order.

Output:

Print $n$n integers $p_1$p1​, $p_2$p2​, …, $p_n$pn​ — permutation of integers from $1$1 to $n$n, which corresponds to the order of kids in the circle. If there are several answers, you may print any (for example, it doesn’t matter which kid is the first in the circle). It is guaranteed that at least one solution exists.

Sample Input:

5
3 5
1 4
2 4
1 5
2 3

Sample Output:

3 2 4 1 5

Sample Input:

3
2 3
3 1
1 2

Sample Output:

3 1 2

题目链接

一个环有 $n$n 个节点，给出每个节点的后面两个节点（无序），求环。

从第一个节点开始找，只要确定前两个节点，则后续节点即可依次递推出。

AC代码:

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

const int maxn = 2e5 + 5;

int N;
int Next[maxn][2];
vector<int> Ans;

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d%d", &Next[i][0], &Next[i][1]);
    }
    Ans.push_back(1);
    int First = Next[1][0];
    if (Next[1][1] == Next[First][0] || Next[1][1] == Next[First][1]) {
        Ans.push_back(Next[1][0]);
    }
    else {
        Ans.push_back(Next[1][1]);
    }
    for (int i = 2; i < N; ++i) {
        int Size = (int)Ans.size();
        int Temp = Ans[Size - 2];
        if (Ans.back() == Next[Temp][0]) {
            Ans.push_back(Next[Temp][1]);
        }
        else {
            Ans.push_back(Next[Temp][0]);
        }
    }
    for (auto i : Ans) {
        printf("%d ", i);
    }
    printf("\n");
    return 0;
}

E. Almost Regular Bracket Sequence

Description:

You are given a bracket sequence $s$s consisting of $n$n opening ‘(’ and closing ‘)’ brackets.
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters ‘1’ and ‘+’ between the original characters of the sequence. For example, bracket sequences “()()”, “(())” are regular (the resulting expressions are: “(1)+(1)”, “((1+1)+1)”), and “)(” and “(” are not.
You can change the type of some bracket $s_i$si​. It means that if $s_i = $ ‘)’ then you can change it to ‘(’ and vice versa.
Your task is to calculate the number of positions $i$i such that if you change the type of the $i$i-th bracket, then the resulting bracket sequence becomes regular.

Input:

The first line of the input contains one integer $n$n ( $1\le n\le 10^6$1≤n≤106) — the length of the bracket sequence.
The second line of the input contains the string $s$s consisting of $n$n opening ‘(’ and closing ‘)’ brackets.

Output:

Print one integer — the number of positions $i$i such that if you change the type of the $i$i-th bracket, then the resulting bracket sequence becomes regular.

Sample Input:

6
(((())

Sample Output:

3

Sample Input:

6
()()()

Sample Output:

0

Sample Input:

1
)

Sample Output:

0

Sample Input:

8
)))(((((

Sample Output:

0

题目链接

给出一个含有 $n$n 个字符（字符仅含 ‘(’、’)’）的字符串，求字符串中有多少个括号改变之后字符串括号完全匹配。

之前做括号匹配问题只知道用栈的模拟做法，但是显然用在这道题上会超时，所以赛后学习官方题解才大开眼界，括号匹配用前缀后缀和做更方便快捷。

首先正序计算字符串前缀和（左括号+1，右括号-1）与前缀和标记，之后倒序计算字符串后缀和（左括号-1，右括号+1）与后缀和标记，枚举字符串每个位置通过前后缀和判断此位置括号改变后整体字符串是否能够达到括号匹配。

AC代码:

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

const int maxn = 1e6 + 5;

int N;
char Str[maxn];
int Prefix[maxn];
int Suffix[maxn];
bool PreFlag[maxn], SufFlag[maxn];
int Ans;

int main(int argc, char *argv[]) {
    scanf("%d%s", &N, Str + 1);
    PreFlag[0] = true;
    for (int i = 1; i <= N; ++i) {
        Prefix[i] = Prefix[i - 1] + (Str[i] == '(' ? 1 : -1);
        PreFlag[i] = PreFlag[i - 1] & (Prefix[i] >= 0);
    }
    SufFlag[N + 1] = true;
    for (int i = N; i >= 1; --i) {
        Suffix[i] = Suffix[i + 1] + (Str[i] == ')' ? 1 : -1);
        SufFlag[i] = SufFlag[i + 1] & (Suffix[i] >= 0);
    }
    for (int i = 1; i <= N; ++i) {
        if (!PreFlag[i - 1] || !SufFlag[i + 1]) {
            continue;
        }
        if (Str[i] == '(') {
            // 若左括号1~i-1区间内字符串中左括号多于右括号且前缀和-后缀和=1（左边区间左括号减右括号比右边区间右括号减左括号多一个）则此位置左括号可以改变为右括号
            if (Prefix[i - 1] > 0 && Prefix[i - 1] - Suffix[i + 1] == 1) {
                ++Ans;
            }
        }
        else {
            // 同理可改变右括号为左括号
            if (Suffix[i + 1] - Prefix[i - 1] == 1) {
                ++Ans;
            }
        }
    }
    printf("%d\n", Ans);
    return 0;
}

F. Make It Connected

Description:

You are given an undirected graph consisting of $n$n vertices. A number is written on each vertex; the number on vertex $i$i is $a_i$ai​. Initially there are no edges in the graph.
You may add some edges to this graph, but you have to pay for them. The cost of adding an edge between vertices $x$x and $y$y is $a_x+a_y$ax​+ay​ coins. There are also $m$m special offers, each of them is denoted by three numbers $x$x, $y$y and $w$w, and means that you can add an edge connecting vertices $x$x and $y$y and pay $w$w coins for it. You don’t have to use special offers: if there is a pair of vertices $x$x and $y$y that has a special offer associated with it, you still may connect these two vertices paying $a_x+a_y$ax​+ay​ coins for it.
What is the minimum number of coins you have to spend to make the graph connected? Recall that a graph is connected if it’s possible to get from any vertex to any other vertex using only the edges belonging to this graph.

Input:

The first line contains two integers $n$n and $m$m ( $1\le n\le 2\cdot 10^5$1≤n≤2⋅105, $0\le m\le 2\cdot 10^5$0≤m≤2⋅105) — the number of vertices in the graph and the number of special offers, respectively.
The second line contains $n$n integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ ( $1\le a_i\le 10^{12}$1≤ai​≤1012) — the numbers written on the vertices.
Then $m$m lines follow, each containing three integers $x$x, $y$y and $w$w ( $1\le x,y\le n$1≤x,y≤n, $1\le w\le 10^{12}$1≤w≤1012, $x\ne y$x̸​=y) denoting a special offer: you may add an edge connecting vertex $x$x and vertex $y$y, and this edge will cost $w$w coins.

Output:

Print one integer — the minimum number of coins you have to pay to make the graph connected.

Sample Input:

3 2
1 3 3
2 3 5
2 1 1

Sample Output:

5

Sample Input:

4 0
1 3 3 7

Sample Output:

16

Sample Input:

5 4
1 2 3 4 5
1 2 8
1 3 10
1 4 7
1 5 15

Sample Output:

18

题目链接

$n$n 个顶点，每个顶点有一个权值，将两顶点相连的花费为两顶点权值之和， $m$m 条边，每条边用 $w$w 花费进行相连（当然也可以用两顶点权值之和），求将 $n$n 个顶点连接为连通图的最小花费。

显然此题是求最小生成树，所以如何建边就是解此题的核心问题，若将任意两顶点都建边（权值为两顶点权值之和）无法存储，所以仅需将 $n$n 个顶点与权值最小的顶点相连建边即可（花费必然优于与其它顶点相连），剩下 $m$m 条边单独建边，用Kruskal/Prim求出MST即可。

AC代码:

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

const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;

struct Edge {
    int U, V;
    long long Dis;

    bool operator < (const Edge &B) const {
        return Dis < B.Dis;
    }
};

int N, M;
int Tot;
int Pre[maxn];
Edge edges[maxn << 4];

void Init() {
    for (int i = 0; i <= N; ++i) {
        Pre[i] = i;
    }
}

int Find(int X) {
    int R = X;
    while (Pre[R] != R) {
        R = Pre[R];
    }
    int I = X, J;
    while (I != R) {
        J = Pre[I];
        Pre[I] = R;
        I = J;
    }
    return R;
}

void Join(int X, int Y) {
    int XX = Find(X);
    int YY = Find(Y);
    if (XX != YY) {
        Pre[XX] = YY;
    }
}

long long Kruskal() {
    sort(edges, edges + Tot);
    Init();
    long long Res = 0;
    for (int i = 0; i < Tot; ++i) {
        Edge Temp = edges[i];
        if (Find(Temp.U) != Find(Temp.V)) {
            Join(Temp.U, Temp.V);
            Res += Temp.Dis;
        }
    }
    return Res;
}

long long Vertex[maxn];
int Min;

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    Min = 1;
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", &Vertex[i]);
        if (Vertex[i] < Vertex[Min]) {
            Min = i;
        }
    }
    Tot = 0;
    for (int i = 1; i <= N; ++i) {
        edges[Tot++] = Edge {i, Min, Vertex[i] + Vertex[Min]};
    }
    for (int i = 1, U, V; i <= M; ++i) {
        long long Coin;
        scanf("%d%d%lld", &U, &V, &Coin);
        edges[Tot++] = Edge{U, V, Coin};
    }
    printf("%lld\n", Kruskal());
    return 0;
}