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

关注

Educational Codeforces Round 59 (Rated for Div. 2)

A. Digits Sequence Dividing

Description:

You are given a sequence $s$ consisting of $n$ digits from $1$ to $9$ .
You have to divide it into at least two segments (segment — is a consecutive sequence of elements) (in other words, you have to place separators between some digits of the sequence) in such a way that each element belongs to exactly one segment and if the resulting division will be represented as an integer numbers sequence then each next element of this sequence will be strictly greater than the previous one.
More formally: if the resulting division of the sequence is $t_{1}, t_{2}, \dots, t_{k}$ , where $k$ is the number of element in a division, then for each $i$ from $1$ to $k - 1$ the condition $t_{i} < t_{i + 1}$ (using numerical comparing, it means that the integer representations of strings are compared) should be satisfied.
For example, if $s = 654$ then you can divide it into parts $[6, 54]$ and it will be suitable division. But if you will divide it into parts $[65, 4]$ then it will be bad division because $65 > 4$ . If $s = 123$ then you can divide it into parts $[1, 23]$ , $[1, 2, 3]$ but not into parts $[12, 3]$ .
Your task is to find any suitable division for each of the $q$ independent queries.

Input:

The first line of the input contains one integer $q$ ( $1 \leq q \leq 300$ ) — the number of queries.
The first line of the $i$ -th query contains one integer number $n_{i}$ ( $2 \leq n_{i} \leq 300$ ) — the number of digits in the $i$ -th query.
The second line of the $i$ -th query contains one string $s_{i}$ of length $n_{i}$ consisting only of digits from $1$ to $9$ .

Output

If the sequence of digits in the $i$ -th query cannot be divided into at least two parts in a way described in the problem statement, print the single line “NO” for this query.
Otherwise in the first line of the answer to this query print “YES”, on the second line print $k_{i}$ — the number of parts in your division of the $i$ -th query sequence and in the third line print $k_{i}$ strings $t_{i, 1}, t_{i, 2}, \dots, t_{i, k_{i}}$ — your division. Parts should be printed in order of the initial string digits. It means that if you write the parts one after another without changing their order then you’ll get the string $s_{i}$ .
See examples for better understanding.

Sample Input:

4
6
654321
4
1337
2
33
4
2122

Sample Output:

YES
3
6 54 321
YES
3
1 3 37
NO
YES
2
21 22

题目链接

判断一串数字字符串是否能够被划分为至少两段的严格递增数列

若字符串长度为 $2$ 判断第一位是否小于第二位即可

否则一定可以构造为符合要求的两个数（按照位数划分第一个数一定可以比第二个数位数少）

AC代码:

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

int main(int argc, char *argv[]) {
    int Q; cin >> Q;
    for (int Query = 1; Query <= Q; ++Query) {
        int N; string Str; cin >> N >> Str;
        if (N == 2 && Str[0] >= Str[1]) {
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl << "2" << endl;
        cout << Str[0] << " " << Str.substr(1, N - 1) << endl;
    }
    return 0;
}

B. Digital root

Description:

Today at the lesson of mathematics, Petya learns about the digital root.
The digital root of a non-negative integer is the single digit value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.
Let’s denote the digital root of $x$ as $S (x)$ . Then $S (5) = 5$ , $S (38) = S (3 + 8 = 11) = S (1 + 1 = 2) = 2$ , $S (10) = S (1 + 0 = 1) = 1$ .
As a homework Petya got $n$ tasks of the form: find $k$ -th positive number whose digital root is $x$ .
Petya has already solved all the problems, but he doesn’t know if it’s right. Your task is to solve all $n$ tasks from Petya’s homework.

Input:

The first line contains a single integer $n$ ( $1 \leq n \leq 1 0^{3}$ ) — the number of tasks in Petya’s homework. The next $n$ lines contain two integers $k_{i}$ ( $1 \leq k_{i} \leq 1 0^{12}$ ) and $x_{i}$ ( $1 \leq x_{i} \leq 9$ ) — $i$ -th Petya’s task in which you need to find a $k_{i}$ -th positive number, the digital root of which is $x_{i}$ .

Output

Output $n$ lines, $i$ -th line should contain a single integer — the answer to the $i$ -th problem.

Sample Input:

3
1 5
5 2
3 1

Sample Output:

5
38
19

题目链接

一个数的数根为其所有位数之和直到此数为个位数，求第 $k$ 个数根为 $x$ 的数

观察可得一个数 $x$ 的数根即为 $x m o d 9$ ，所以第 $k$ 个数根为 $x$ 的数即为 $(k - 1) \times 9 + x$

AC代码:

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

int main(int argc, char *argv[]) {
    ll n; cin >> n;
    for (ll i = 0, k, x; i < n; ++i) {
        cin >> k >> x;
        cout << (k - 1) * 9 + x << endl;
    }
    return 0;
}

C. Brutality

Description:

You are playing a new famous fighting game: Kortal Mombat XII. You have to perform a brutality on your opponent’s character.
You are playing the game on the new generation console so your gamepad have $26$ buttons. Each button has a single lowercase Latin letter from ‘a’ to ‘z’ written on it. All the letters on buttons are pairwise distinct.
You are given a sequence of hits, the $i$ -th hit deals $a_{i}$ units of damage to the opponent’s character. To perform the $i$ -th hit you have to press the button $s_{i}$ on your gamepad. Hits are numbered from $1$ to $n$ .
You know that if you press some button more than $k$ times in a row then it’ll break. You cherish your gamepad and don’t want to break any of its buttons.
To perform a brutality you have to land some of the hits of the given sequence. You are allowed to skip any of them, however changing the initial order of the sequence is prohibited. The total damage dealt is the sum of $a_{i}$ over all $i$ for the hits which weren’t skipped.
Note that if you skip the hit then the counter of consecutive presses the button won’t reset.
Your task is to skip some hits to deal the maximum possible total damage to the opponent’s character and not break your gamepad buttons.

Input:

The first line of the input contains two integers $n$ and $k$ ( $1 \leq k \leq n \leq 2 \cdot 1 0^{5}$ ) — the number of hits and the maximum number of times you can push the same button in a row.
The second line of the input contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 1 0^{9}$ ), where $a_{i}$ is the damage of the $i$ -th hit.
The third line of the input contains the string $s$ consisting of exactly $n$ lowercase Latin letters — the sequence of hits (each character is the letter on the button you need to press to perform the corresponding hit).

Output

Print one integer $d m g$ — the maximum possible damage to the opponent’s character you can deal without breaking your gamepad buttons.

Sample Input:

7 3
1 5 16 18 7 2 10
baaaaca

Sample Output:

Sample Input:

5 5
2 4 1 3 1000
aaaaa

Sample Output:

1010

Sample Input:

5 4
2 4 1 3 1000
aaaaa

Sample Output:

1009

Sample Input:

8 1
10 15 2 1 4 8 15 16
qqwweerr

Sample Output:

Sample Input:

6 3
14 18 9 19 2 15
cccccc

Sample Output:

Sample Input:

2 1
10 10
qq

Sample Output:

题目链接

一串由小写字母组成的字符串每个字符均有一个权值，按照下标升序依次拿取字符，相同字符最多可以连续拿 $k$ 次，求可拿的最大权值之和

先处理字符相同的连续区间，之后在区间内拿权值最大的 $k$ 个即可

AC代码:

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

int main(int argc, char *argv[]) {
    int n, k; cin >> n >> k;
    vector<pair<int, char> > a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].first;
    for (int i = 0; i < n; ++i) cin >> a[i].second;
    vector<pair<int, int> > seg;
    for (int l = 0, r = 0; l < n; l = r) {
        while (r < n && a[r].second == a[l].second) r++;
        seg.push_back(make_pair(l, r));
    }
    ll ans = 0;
    for (auto it : seg) {
        sort(a.begin() + it.first, a.begin() + it.second);
        reverse(a.begin() + it.first, a.begin() + it.second);
        for (int i = it.first; i < min(it.second, it.first + k); ++i) ans += a[i].first;
    }
    cout << ans << endl;
    return 0;
}

D. Compression

Description:

You are given a binary matrix $A $ of size $n \times n $ . Let’s denote an $x $ -compression of the given matrix as a matrix $B $ of size $\frac{n}{x} \times \frac{n}{x} $ such that for every $i \in [1, n], j \in [1, n] $ the condition $A [i] [j] = B [⌈ \frac{i}{x} ⌉] [⌈ \frac{j}{x} ⌉] $ is met.
Obviously, $x $ -compression is possible only if $x $ divides $n $ , but this condition is not enough. For example, the following matrix of size $2 \times 2 $ does not have any $2 $ -compression:

$0110$

For the given matrix $A$ , find maximum $x$ such that an $x$ -compression of this matrix is possible.
Note that the input is given in compressed form. But even though it is compressed, you’d better use fast input.

Input:

The first line contains one number $n$ ( $4 \leq n \leq 5200$ ) — the number of rows and columns in the matrix $A$ . It is guaranteed that $n$ is divisible by $4$ .
Then the representation of matrix follows. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$ ). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are 1011, and if the number is $5$ , then the corresponding elements are 0101.
Elements are not separated by whitespaces.

Output

Print one number: maximum $x$ such that an $x$ -compression of the given matrix is possible.

Sample Input:

8
E7
E7
E7
00
00
E7
E7
E7

Sample Output:

Sample Input:

4
7
F
F
F

Sample Output:

题目链接

一个由 $0 、 1$ 组成的 $n \times n$ 矩阵 $A$ 每行按 $16$ 进制给出（矩阵每一位即为 $16$ 进制数在 $2$ 进制下的每一位），求最大的 $x (x ∣ n)$ 使得可以构造出一个 $⌊ \frac{n}{x} ⌋ \times ⌊ \frac{n}{x} ⌋$ 的矩阵使得对于任意 $i \in [1, n], j \in [1, n]$ 满足 $A [i] [j] = B [⌊ \frac{i}{x} ⌋] [⌊ \frac{j}{x} ⌋]$

其实题意就是压缩矩阵使得矩阵分块的每一部分都相等然后压缩为一个数，求压缩后矩阵大小的最大值

枚举压缩后的矩阵大小（因为是求最大值所以可以由 $n$ 开始从大往小枚举），因为在对于不同的 $i 、 j$ 会有相同的 $⌊ \frac{i}{x} ⌋ 、 ⌊ \frac{j}{x} ⌋ $ 所以相同的值就自然被归并到一块内（整除分块），所以必须要求所有块内所有元素相等才可成立，这里可以预处理原矩阵每行、列是否与上一行、列相同进行判断，同一行内若有块内列不与上一列（两列位处同一块内）完全相同则表明块内元素不完全相同即不可压缩，同理同一列内若有块内行不与上一行（两行位处同一块内）完全相同则不可压缩

AC代码:

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

int main(int argc, char *argv[]) {
    int n; cin >> n;
    vector<vector<bool>> matrix(n, vector<bool>(n, false));
    for (int i = 0; i < n; ++i) {
        string hex; cin >> hex;
        for (int j = 0, x; j < hex.length(); ++j) {
            if (isdigit(hex[j])) x = hex[j] - '0';
            else x = hex[j] - 'A' + 10;
            for (int k = 3; k >= 0; --k) {
                int site = 4 - k - 1;
                matrix[i][j * 4 + k] = x & 1;
                x >>= 1;
            }
        }
    }
    vector<bool> r(n, false);
    for (int i = 1; i < n; ++i) {
        r[i] = true;
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] != matrix[i - 1][j]) r[i] = false;
        }
    }
    vector<bool> c(n, false);
    for (int j = 1; j < n; ++j) {
        c[j] = true;
        for (int i = 0; i < n; ++i) {
            if (matrix[i][j] != matrix[i][j - 1]) c[j] = false;
        }
    }
    for (int x = n; x > 0; --x) {
        if (n % x) continue;
        int flag = true;
        for (int i = 0; i < n; ++i) {
            if ((i % x) && (!c[i] || !r[i])) flag = false;
        }
        if (flag) {
            cout << x << endl;
            break;
        }
    }
    return 0;
}