A. Wrong Subtraction

Description:

Little girl Tanya is learning how to decrease a number by one, but she does it wrong with a number consisting of two or more digits. Tanya subtracts one from a number by the following algorithm:

if the last digit of the number is non-zero, she decreases the number by one;
if the last digit of the number is zero, she divides the number by 10 (i.e. removes the last digit).

You are given an integer number n. Tanya will subtract one from it k times. Your task is to print the result after all k subtractions.

It is guaranteed that the result will be positive integer number.

Input:

The first line of the input contains two integer numbers n and k (2≤n≤10⁹, 1≤k≤50) — the number from which Tanya will subtract and the number of subtractions correspondingly.

Output:

Print one integer number — the result of the decreasing n by one k times.

It is guaranteed that the result will be positive integer number.

Sample Input:

512 4

Sample Output:

Sample Input:

1000000000 9

Sample Output:

题目连接

直接模拟

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

ll n, k;

ll work(ll x) {
    ll temp = x % 10;
    if (temp == 0) {
        return x / 10;
    }
    else {
        return x - 1;
    }
}

int main() {
    //fre();
    scanf("%I64d %I64d", &n, &k);
    for (int i = 0; i < k; ++i) {
        n = work(n);
    }
    printf("%I64d", n);
    return 0;
}

B. Two-gram

Description:

Two-gram is an ordered pair (i.e. string of length two) of capital Latin letters. For example, “AZ”, “AA”, “ZA” — three distinct two-grams.

You are given a string s consisting of n capital Latin letters. Your task is to find any two-gram contained in the given string as a substring (i.e. two consecutive characters of the string) maximal number of times. For example, for string s = “BBAABBBA” the answer is two-gram “BB”, which contained in s three times. In other words, find any most frequent two-gram.

Note that occurrences of the two-gram can overlap with each other.

Input:

The first line of the input contains integer number n (2≤n≤100) — the length of string s. The second line of the input contains the string s consisting of n capital Latin letters.

Output:

Print the only line containing exactly two capital Latin letters — any two-gram contained in the given string s as a substring (i.e. two consecutive characters of the string) maximal number

Sample Input:

7
ABACABA

Sample Output:

Sample Input:

5
ZZZAA

Sample Output:

题目连接

暴力枚举统计

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

string str[100];
int n;
int cnt;
string s;
int _count[100];
int ans;
int book;

int main() {
    //fre();
    cnt = 0;
    for (int i = 0; i < 100; ++i) {
        str[i].clear();
    }
    mem(_count, 0);
    cin >> n >> s;
    for (int i = 0; i < n - 1; ++i) {
        string temp;
        temp += s[i]; temp += s[i + 1];
        bool flag = 0;
        for (int i = 0; i < cnt; ++i) {
            if (str[i] == temp) {
                _count[i]++;
                flag = 1;
                break;
            }
        }
        if (!flag) {
            str[cnt] = temp;
            _count[cnt++]++;
        }
    }
    ans = 0;
    for (int i = 0; i < cnt; ++i) {
        if (_count[i] > ans) {
            ans = _count[i];
            book = i;
        }
    }
    cout << str[book];
    return 0;
}

C. Less or Equal

Description:

You are given a sequence of integers of length n and integer number k. You should print any integer number x in the range of [ $1; 1 0^{9}$ ] (i.e. 1≤x≤ $1 0^{9}$ ) such that exactly k elements of given sequence are less than or equal to x.

Note that the sequence can contain equal elements.

If there is no such x, print “-1” (without quotes).

Input:

The first line of the input contains integer numbers n and k ( $1 \leq n \leq 2 \times 1 0^{5}$ , $0 \leq k \leq n$ ). The second line of the input contains n integer numbers $a_{1}, a_{2}, \dots, a_{n} (1 \leq a i \leq 1 0^{9})$ — the sequence itself.

Output:

Print any integer number x from range [ $1; 1 0^{9}$ ] such that exactly k elements of given sequence is less or equal to x.

If there is no such x, print “-1” (without quotes).

Sample Input:

7 4
3 7 5 1 10 3 20

Sample Output:

Sample Input:

7 2
3 7 5 1 10 3 20

Sample Output:

-1

题目连接

直接排序判断第k个数和第k+1个数是否相等，若相等直接输出-1，否则输出第k个数即可。注
意特判k=0的情况。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

ll n, k;
ll a[maxn];
ll ans;

int main() {
    //fre();
    ans = -1;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a, a + n);
    if (k > 0) {
        if (a[k - 1] != a[k]) {
            ans = a[k - 1];
        }
    }
    else {
        if (a[0] > 1) {
            ans = a[0] - 1;
        }
    }
    cout << ans;
    return 0;
}

D. Divide by three, multiply by two

Description:

Polycarp likes to play with numbers. He takes some integer number x, writes it down on the board, and then performs with it n−1 operations of the two kinds:

divide the number x by 3 (x must be divisible by 3);
multiply the number x by 2.

After each operation, Polycarp writes down the result on the board and replaces x by the result. So there will be n numbers on the board after all.

You are given a sequence of length n — the numbers that Polycarp wrote down. This sequence is given in arbitrary order, i.e. the order of the sequence can mismatch the order of the numbers written on the board.

Your problem is to rearrange (reorder) elements of this sequence in such a way that it can match possible Polycarp’s game in the order of the numbers written on the board. I.e. each next number will be exactly two times of the previous number or exactly one third of previous number.

It is guaranteed that the answer exists.

Input:

The first line of the input contatins an integer number n (2≤n≤100) — the number of the elements in the sequence. The second line of the input contains n integer numbers a1,a2,…,an (1≤ai≤3×10¹⁸) — rearranged (reordered) sequence that Polycarp can wrote down on the board.

Output:

Print n integer numbers — rearranged (reordered) input sequence that can be the sequence that Polycarp could write down on the board.

It is guaranteed that the answer exists.

Sample Input:

6
4 8 6 3 12 9

Sample Output:

9 3 6 12 4 8

Sample Input:

4
42 28 84 126

Sample Output:

126 42 84 28

Sample Input:

2
1000000000000000000 3000000000000000000

Sample Output:

3000000000000000000 1000000000000000000

题目连接

枚举第一个数，深搜找到符合的序列。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> p;
const int inf = 0x3f3f3f3f;
const int maxn = 1e2+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

int n;
ull a[maxn];
ull ans[maxn];
bool flag;
bool vis[maxn];

void dfs(ull x, int step) {
    ans[step] = x;
    if (step == n) {
        flag = 1;
        return;
    }
    if (x % 3 == 0) {
        ull temp = x / 3;
        for (int i = 0; i < n; ++i) {
            if (!vis[i] && a[i] == temp) {
                vis[i] = 1;
                dfs(a[i], step + 1);
                if (flag) {
                    return;
                }
                vis[i] = 0;
                break;
            }
        }
    }
    ull temp = x * 2;
    for (int i = 0; i < n; ++i) {
        if (!vis[i] && a[i] == temp) {
            vis[i] = 1;
            dfs(a[i], step + 1);
            if (flag) {
                return;
            }
            vis[i] = 0;
        }
    }
}

int main() {
    //fre();
    flag = 0;
    cin >> n;
    mem(vis, 0);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        dfs(a[i], 1);
        if (flag) {
            break;
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << " ";
    }
    return 0;
}

E. Cyclic Components

Description:

You are given an undirected graph consisting of n vertices and m edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex a is connected with a vertex b, a vertexb is also connected with a vertex a). An edge can’t connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices u and v belong to the same connected component if and only if there is at least one path along edges connecting u and v.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

the first vertex is connected with the second vertex by an edge,
the second vertex is connected with the third vertex by an edge,
…
the last vertex is connected with the first vertex by an edge,
all the described edges of a cycle are distinct.

A cycle doesn’t contain any other edges except described above. By definition any cycle contains three or more vertices.

There are 6 connected components, 2 of them are cycles: [7,10,16] and [5,11,9,15].

Input:

The first line contains two integer numbers n and m ( $1 \leq n \leq 2 \times 1 0^{5}, 0 \leq m \leq 2 \times 1 0^{5}$ ) — number of vertices and edges.

The following m lines contains edges: edge i is given as a pair of vertices $v_{i}$ , $u_{i} (1 \leq v_{i}, u_{i} \leq n, u_{i} \neq v_{i})$ . There is no multiple edges in the given graph, i.e. for each pair ( $v_{i}, u_{i}$ ) there no other pairs $(v_{i}, u_{i})$ and $(u_{i}, v_{i})$ in the list of edges.

Output:

Print one integer — the number of connected components which are also cycles.

Sample Input:

5 4
1 2
3 4
5 4
3 5

Sample Output:

Sample Input:

17 15
1 8
1 12
5 11
11 9
9 15
15 5
4 13
3 13
4 3
10 16
7 10
16 7
14 3
14 4
17 6

Sample Output:

题目连接

枚举顶点dfs深搜判断是否成环。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> p;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

int n, m;
bool flag;
bool vis[maxn];
int ans;
vector<int> Adj[maxn];

void dfs(int x) {
    if (Adj[x].size() != 2 || vis[x]) {
        flag = 0;
        return;
    }
    vis[x] = 1;
    for (auto it = Adj[x].begin(); it != Adj[x].end(); ++it) {
        int v = *it;
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    //fre();
    ans = 0;
    mem(vis, 0);
    scanf("%d%d", &n, &m);
    while (m--) {
        int input_u, input_v;
        scanf("%d%d", &input_u, &input_v);
        Adj[input_u].pb(input_v);
        Adj[input_v].pb(input_u);
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            flag = 1;
            dfs(i);
            if (flag) {
                ans++;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

F. Consecutive Subsequence

Description:

You are given an integer array of length n.

You have to choose some subsequence of this array of maximum length such that this subsequence forms a increasing sequence of consecutive integers. In other words the required sequence should be equal to [x,x+1,…,x+k−1] for some value x and length k.

Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. You can erase any elements, not necessarily going successively. The remaining elements preserve their order. For example, for the array [5,3,1,2,4] the following arrays are subsequences: [3], [5,3,1,2,4], [5,1,4], but the array [1,3] is not.

Input:

The first line of the input containing integer number n ( $1 \leq n \leq 2 \times 1 0^{5}$ ) — the length of the array. The secondline of the input containing n integer numbers $a_{1}, a_{2}, \dots, a_{n} (1 \leq a_{i} \leq 1 0^{9})$ — the array itself.

Output:

On the first line print k — the maximum length of the subsequence of the given array that forms an increasing sequence of consecutive integers.

On the second line print the sequence of the indices of the any maximum length subsequence of the given array that forms an increasing sequence of consecutive integers.

Sample Input:

7
3 3 4 7 5 6 8

Sample Output:

4
2 3 5 6

Sample Input:

6
1 3 5 2 4 6

Sample Output:

2
1 4

Sample Input:

4
10 9 8 7

Sample Output:

1
1

Sample Input:

9
6 7 8 3 4 5 9 10 11

Sample Output:

6
1 2 3 7 8 9

题目连接

dp[i]记录以i结尾序列的最大连续增长长度，寻找最大值并记录输出。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> p;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
}

int n;
ll a[maxn];
map<int, int> dp;
ll ans, book;
ll res[maxn];

int main() {
    //fre();
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%I64d", &a[i]);
    }
    ans = 0; book = 0;
    for (int i = 0; i < n; ++i) {
        dp[a[i]] = dp[a[i] - 1] + 1;
        if (ans < dp[a[i]]) {
            ans = dp[a[i]];
            book = a[i];
        }
    }
    int temp = ans - 1;
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] == book) {
            res[temp--] = i + 1;
            book--;
        }
    }
    printf("%I64d\n", ans);
    for (int i = 0; i < ans; ++i) {
        printf("%I64d ", res[i]);
    }
    return 0;
}

Codeforces Round #479 (Div. 3)

A. Wrong Subtraction

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目连接

AC代码:

B. Two-gram

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目连接

AC代码:

C. Less or Equal

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目连接

AC代码:

D. Divide by three, multiply by two

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目连接

AC代码:

E. Cyclic Components

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目连接

AC代码:

F. Consecutive Subsequence

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目连接

AC代码: