A. Diverse Team

Description:

There are n students in a school class, the ratingof the i-th student on Codehorses is ai. You have to form a team consisting of k students (1≤k≤n) such that the ratings of all team members are distinct.

If it is impossible to form a suitable team, print “NO” (without quotes). Otherwise print “YES”, and then print k distinct numbers which should be the indices of students in the team you form. If there are multiple answers, print any of them.

Input:

The first line contains two integers n and k (1≤k≤n≤100) — the number of students and the size of the team you have to form.

The second line contains n integers $a_{1}, a_{2}, \dots, a_{n}$ (1≤ $a_{i}$ ≤100), where ai is the rating of i-th student.

Output:

If it is impossible to form a suitable team, print “NO” (without quotes). Otherwise print “YES”, and then print k distinct integers from 1 to n which should be the indices of students in the team you form. All the ratings of the students in the team should be distinct. You may print the indices in any order. If there are multiple answers, print any of them.

Assume that the studesnts are numbered from 1 to n.

Sample Input:

5 3
15 13 15 15 12

Sample Output:

YES
1 2 5

Sample Input:

5 4
15 13 15 15 12

Sample Output:

Sample Input:

4 4
20 10 40 30

Sample Output:

YES
1 2 3 4

题目链接

用set判断数字是否重复，vector记录结果。

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 int mod = 1e9+7;
const double eps = 1e-8;
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, k;
int a[maxn];
int cnt;
set<int> vis;
vector<int> ans;

int main(){
    //fre();
    vis.clear(); ans.clear();
    cnt = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if (cnt < k) {
            if (vis.count(a[i]) == 0) {
                vis.insert(a[i]);
                cnt++;
                ans.pb(i);
            }
        }
    }
    if (cnt >= k) {
        printf("YES\n");
        for (auto it : ans) {
            printf("%d ", it);
        }
    }
    else {
        printf("NO\n");
    }
    return 0;
}

B. Substrings Sort

Description:

You are given n strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String a is a substring of string b if it is possible to choose several consecutive letters in b in such a way that they form a. For example, string “for” is contained as a substring in strings “codeforces”, “for” and “therefore”, but is not contained as a substring in strings “four”, “fofo” and “rof”.

Input:

The first line contains an integer n (1≤n≤100) — the number of strings.

The next n lines contain the given strings. The number of letters in each string is from 1 to 100, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

Output:

If it is impossible to reorder n given strings in required order, print “NO” (without quotes).

Otherwise print “YES” (without quotes) and n given strings in required order.

Sample Input:

5
a
aba
abacaba
ba
aba

Sample Output:

YES
a
ba
aba
aba
abacaba

Sample Input:

5
a
abacaba
ba
aba
abab

Sample Output:

Sample Input:

3
qwerty
qwerty
qwerty

Sample Output:

YES
qwerty
qwerty
qwerty

题目链接

按照字符串长度排序，依次判断字符串i是否是i+1字符串的子串。

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 int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
void fre() {
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
}

bool cmp(string a, string b) {
    return a.length() < b.length();
}

int main(){
    //fre();
    int n;
    cin >> n;
    vector<string> str(n);
    for (int i = 0; i < n; ++i) {
        cin >> str[i];
    }
    sort(str.begin(), str.end(), cmp);
    for (int i = 0; i < n - 1; ++i) {
        if (str[i + 1].find(str[i]) == string::npos) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    for (auto it : str) {
        cout << it << endl;
    }
    return 0;
}

C. Equal Sums

Description:

You are given k sequences of integers. The length of the i-th sequence equals to $n_{i}$ .

You have to choose exactly two sequences i and j (i≠j) such that you can remove exactly one element in each of them in such a way that the sum of the changed sequence i (its length will be equal to $n_{i} - 1$ ) equals to the sum of the changed sequence j (its length will be equal to $n_{j} - 1$ ).

Note that it’s required to remove exactly one element in each of the two chosen sequences.

Assume that the sum of the empty (of the length equals 0) sequence is 0.

Input:

The first line contains an integer k ( $2 \leq k \leq 2 \cdot 1 0^{5}$ ) — the number of sequences.

Then k pairs of lines follow, each pair containing a sequence.

The first line in the i-th pair contains one integer $n_{i}$ ( $1 \leq n_{i} < 2 \cdot 1 0^{5}$ ) — the length of the i-th sequence. The second line of the i-th pair contains a sequence of $n_{i}$ integers $a_{i}, 1, a_{i}, 2, \dots, a_{i}, n_{i}$ .

The elements of sequences are integer numbers from − $1 0^{4}$ to $1 0^{4}$ .

The sum of lengths of all given sequences don’t exceed 2⋅ $1 0^{5}$ , i.e. $n_{1} + n_{2} + \dots + n_{k} \leq 2 \cdot 1 0^{5}$ .

Output:

If it is impossible to choose two sequences such that they satisfy given conditions, print “NO” (without quotes). Otherwise in the first line print “YES” (without quotes), in the second line — two integers i, x ( $1 \leq i \leq k, 1 \leq x \leq n_{i}$ ), in the third line — two integers j, y ( $1 \leq j \leq k, 1 \leq y \leq n_{j}$ ). It means that the sum of the elements of the i-th sequence without the element with index x equals to the sum of the elements of the j-th sequence without the element with index y.

Two chosen sequences must be distinct, i.e. i≠j. You can print them in any order.

If there are multiple possible answers, print any of them.

Sample Input:

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

Sample Output:

YES
2 6
1 2

Sample Input:

3
1
5
5
1 1 1 1 1
2
2 3

Sample Output:

Sample Input:

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

Sample Output:

YES
2 2
4 1

题目链接

AC代码:

算出每个数列的和并用map存储数列和减去数列任意一个数之后的值，map对应一个pair方便存储数列序号和删除数的序号，当值算出后判断此值是否已在map中存储，若已存储则说明找到结果，按题目要求输出。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
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 main(){
    //fre();
    map<int, P> m;
    int k;
    scanf("%d", &k);
    for (int i = 0; i < k; ++i) {
        int n,s = 0;
        scanf("%d", &n);
        vector<int> a(n);
        for (int j = 0; j < n; ++j) {
            scanf("%d", &a[j]);
            s += a[j];
        }
        for (int j = 0; j < n; ++j) {
            int k = s - a[j];
            if (m.count(k)) {
                printf("YES\n%d %d\n%d %d", i + 1, j + 1, m[k].first + 1, m[k].second + 1);
                return 0;
            }
        }
        for (int j = 0; j < n; ++j) {
            m[s - a[j]] = mp(i, j);
        }
    }
    printf("NO\n");
    return 0;
}

D. Points and Powers of Two

Description:

There are n distinct points on a coordinate line, the coordinate of i-th point equals to xi. Choose a subset of the given set of points such that the distance between each pair of points in a subset is an integral power of two. It is necessary to consider each pair of points, not only adjacent. Note that any subset containing one element satisfies the condition above. Among all these subsets, choose a subset with maximum possible size.

In other words, you have to choose the maximum possible number of points $x_{i 1}, x_{i 2}, \dots, x_{i m}$ such that for each pair xij, xik
it is true that | $x_{i j}$ − $x_{i k}$ |= $2^{d}$ where d is some non-negative integer number (not necessarily the same for each pair of points).

Input:

The first line contains one integer n ( $1 \leq n \leq 2 \cdot 1 0^{5}$ ) — the number of points.

The second line contains n pairwise distinct integers $x_{1}, x_{2}, \dots, x_{n}$ (− $1 0^{9} \leq x_{i} \leq 1 0^{9}$ ) — the coordinates of points.

Output:

In the first line print m — the maximum possible number of points in a subset that satisfies the conditions described above.

In the second line print m integers — the coordinates of points in the subset you have chosen.

If there are multiple answers, print any of them.

Sample Input:

6
3 5 4 7 10 12

Sample Output:

3
7 3 5

Sample Input:

5
-1 2 5 8 11

Sample Output:

1
8

题目链接

用一个set保存数组中的数字。分析可得答案只有1、2、3三种情况，先从3开始判断，遍历枚举数列中的数字x[i]，判断x[i]-2^?和x[i]+2?是否存在于数列中，之后判断2，遍历枚举数列中的数字x[i]，判断x[i]-2^?是否存在于数列中，最后判断1。
PS:用map存储数据会超时?

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
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 main(){
    //fre();
    set<int> s;
    int n;
    scanf("%d", &n);
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x[i]);
        s.insert(x[i]);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 31; ++j) {
            // set用find寻找容器内没有的值返回set.end()
            // 位运算计算2的阶乘
            if (s.find(x[i] - (1 << j)) != s.end() && s.find(x[i] + (1 << j)) != s.end()) {
                printf("3\n%d %d %d", x[i] - (1 << j), x[i], x[i] + (1 << j));
                return 0;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 31; ++j) {
            if (s.find(x[i] - (1 << j)) != s.end()) {
                printf("2\n%d %d", x[i] - (1 << j), x[i]);
                return 0;
            }
        }
    }
    printf("1\n%d", x[0]);
    return 0;
}

E. Divisibility by 25

Description:

You are given an integer n from 1 to $1 0^{18}$ without leading zeroes.

In one move you can swap any two adjacent digits in the given number in such a way that the resulting number will not contain leading zeroes. In other words, after each move the number you have cannot contain any leading zeroes.

What is the minimum number of moves you have to make to obtain a number that is divisible by 25? Print -1 if it is impossible to obtain a number that is divisible by 25.

Input:

The first line contains an integer n ( $1 \leq n \leq 1 0^{18}$ ). It is guaranteed that the first (left) digit of the number n is not a zero.

Output:

If it is impossible to obtain a number that is divisible by 25, print -1. Otherwise print the minimum number of moves required to obtain such number.

Note that you can swap only adjacent digits in the given number.

Sample Input:

5071

Sample Output:

Sample Input:

705

Sample Output:

Sample Input:

1241367

Sample Output:

-1

题目链接

能被25整除有四种情况，分别为数字末尾是:00、25、50、75，判断能否通过交换相邻数字构成这四种情况。例如数字2533可以构成数字末尾为25的数，交换步骤是先把5交换到最后一位，再把2交换到倒数第二位，若数字为5233则先把2交换到最后一位，再把5交换到倒数第二位，最后把最后两位数字交换即可。若交换后数字开头为0则将第一个非零数交换到第一位。

AC代码:

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

string str;

int check(char a, char b) {
    int Findex = -1, Sindex = -1;
    string Judge = str;
    int ans = 0;
    int ZeroCnt = 0;
    for (int i = Judge.size() - 1; i >= 0; --i) {
        if (Judge[i] == b && Sindex == -1) {
            Sindex = i + 1;
        }
        else if (Judge[i] == a &&Findex == -1) {
            Findex = i + 1;
        }
        if (Findex != -1 && Sindex != -1) {
            break;
        }
    }
    if (Findex == -1 || Sindex == -1) {
        return INF;
    }
    if (Findex > Sindex) {
        swap(Sindex, Findex);
        for (int i = Sindex - 1; i < Judge.size() - 1; ++i) {
            swap(Judge[i], Judge[i + 1]);
            ans++;
        }
        for (int i = Findex - 1; i < Judge.size() - 2; ++i) {
            swap(Judge[i], Judge[i + 1]);
            ans++;
        }
        swap(Judge[Judge.size() - 1], Judge[Judge.size() - 2]);
        ans++;
    }
    else {
        for (int i = Sindex - 1; i < Judge.size() - 1; ++i) {
            swap(Judge[i], Judge[i + 1]);
            ans++;
        }
        for (int i = Findex - 1; i < Judge.size() - 2; ++i) {
            swap(Judge[i], Judge[i + 1]);
            ans++;
        }
    }
    for (int i = 0; Judge[i] != '\0'; ++i) {
        if (Judge[i] == '0') {
            ZeroCnt++;
        }
        else {
            break;
        }
    }
    ans += ZeroCnt;
    return ans;
}

int main(){
    //fre();
    cin >> str;
    int ans = INF;
    ans = min(check('0', '0'), check('2', '5'));
    ans = min(ans, check('5', '0'));
    ans = min(ans, check('7', '5'));
    ans = ans == INF ? -1 : ans;
    printf("%d", ans);
    return 0;
}

F. Rain and Umbrellas

Description:

Polycarp lives on a coordinate line at the point x=0. He goes to his friend that lives at the point x=a. Polycarp can move only from left to right, he can pass one unit of length each second.

Now it’s raining, so some segments of his way are in the rain. Formally, it’s raining on n non-intersecting segments, the i-th segment which is in the rain is represented as [ $l_{i}, r_{i}$ ] ( $0 \leq l_{i} < r_{i} \leq a$ ).

There are m umbrellas lying on the line, the i-th umbrella is located at point xi ( $0 \leq x_{i} \leq a$ ) and has weight $p_{i}$ . When Polycarp begins his journey, he doesn’t have any umbrellas.

During his journey from x=0 to x=a Polycarp can pick up and throw away umbrellas. Polycarp picks up and throws down any umbrella instantly. He can carry any number of umbrellas at any moment of time. Because Polycarp doesn’t want to get wet, he must carry at least one umbrella while he moves from x to x+1 if a segment [x,x+1] is in the rain (i.e. if there exists some i such that $l_{i} \leq x$ and $x + 1 \leq r_{i}$ ).

The condition above is the only requirement. For example, it is possible to go without any umbrellas to a point where some rain segment starts, pick up an umbrella at this point and move along with an umbrella. Polycarp can swap umbrellas while he is in the rain.

Each unit of length passed increases Polycarp’s fatigue by the sum of the weights of umbrellas he carries while moving.

Can Polycarp make his way from point x=0 to point x=a? If yes, find the minimum total fatigue after reaching x=a, if Polycarp picks up and throws away umbrellas optimally.

Input:

The first line contains three integers a, n and m (1≤a,m≤2000,1≤n≤⌈ $\frac{a}{2}$ ⌉) — the point at which Polycarp’s friend lives, the number of the segments in the rain and the number of umbrellas.

Each of the next n lines contains two integers $l_{i}$ and $r_{i}$ (0≤ $l_{i}$ < $r_{i}$ ≤a) — the borders of the i-th segment under rain. It is guaranteed that there is no pair of intersecting segments. In other words, for each pair of segments i and j either $r_{i}$ < $l_{j}$ or $r_{j}$ < $l_{i}$ .

Each of the next m lines contains two integers xi and pi ( $0 \leq x_{i} \leq a, 1 \leq p_{i} \leq 1 0^{5}$ ) — the location and the weight of the i-th umbrella.

Output:

Print “-1” (without quotes) if Polycarp can’t make his way from point x=0 to point x=a. Otherwise print one integer — the minimum total fatigue after reaching x=a, if Polycarp picks up and throws away umbrellas optimally.

Sample Input:

10 2 4
3 7
8 10
0 10
3 4
8 1
1 2

Sample Output:

Sample Input:

10 1 1
0 9
0 5

Sample Output:

Sample Input:

10 1 1
0 9
1 5

Sample Output:

-1

题目链接

这题的关键在于想到怎么dp，及怎样去描述一个状态。

首先想到dp[i]表示到达i位置的最小疲劳值，但发现这样不太对，因为这样的话不好转移（因为转移的时候我们需要知道拿着哪把伞走过一格）；因此想到dp[i][j]表示从i点出发前拿着j雨伞时的最小疲劳值（及拿着j雨伞走完i点的最小疲劳值）。这样的话怎么转移呢

如果这个格子上有j雨伞，那说明j雨伞就是在i这个位置上拿的 dp[i][j] = min( dp[i][j],dp[i-1][k]+id[k] ) 【k=0-m】 (j=0时代表不拿伞, id[i]代表i雨伞的重量)

如果没有j雨伞，那说明在到达i点前就拿到j雨伞了 dp[i][j] = dp[i-1][j] + id[j]
题解转自

Codeforces 988F Rain and Umbrellas 【dp】

AC代码:

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

int a, n, m;
// rain[i]==1为i点有雨,rain[i]==0为i点无雨
bool rain[maxn];
// wi[i]为编号为i伞的重量
int wi[maxn];
// dp[i][j]带便拿着j伞走到i点的最小疲劳值,j=0代表不拿伞
int dp[maxn][maxn];
// um[i]存储i位置上的所有伞编号
vector<int> um[maxn];

int main(){
    //fre();
    mem(rain, 0);
    mem(wi, 0);
    scanf("%d%d%d", &a, &n, &m);
    for (int i = 1; i <= n; ++i) {
        int input_l, input_r;
        scanf("%d%d", &input_l, &input_r);
        // 左闭右开区间标记下雨段
        for (int j = input_l; j < input_r; ++j) {
            rain[j] = 1;
        }
    }
    for (int i = 1; i <= a; ++i) {
        um[i].pb(0);
    }
    // 将伞编号从1开始标记,因为dp[i][0]代表不拿伞而不是拿0编号的伞
    for (int i = 1; i <= m; ++i) {
        int input_x;
        scanf("%d%d", &input_x, &wi[i]);
        um[input_x].pb(i);
    }
    // 位置i
    for (int i = 0; i <= a; ++i) {
        // 伞j
        for (int j = 0; j <= m; ++j) {
            // 判断i点是否有伞j
            bool flag = 0;
            for (int k = 0; k < um[i].size(); ++k) {
                if (um[i][k] == j) {
                    flag = 1;
                }
            }
            // 若i点有雨将dp[i][0]初始化为INF
            if (rain[i] && j == 0){
                dp[i][j] = INF;
            }
            // 特判0点
            else if (i == 0) {
                // 若起点没有伞j将dp[0][j]初始化为INF，否则为0
                if (!flag && j != 0) {
                    dp[i][j] = INF;
                }
                else {
                    dp[i][j] = 0;
                }
            }
            // 若i点有伞j
            else if (flag) {
                // 寻找带上伞j的最小疲劳值
                int cost = INF;
                for (int k = 0; k <= m; ++k) {
                    cost = min(cost, dp[i - 1][k] + wi[k]);
                }
                dp[i][j] = cost;
            }
            // 如果没有j雨伞，那说明在到达i点前就拿到j雨伞了
            else {
                dp[i][j] = min(INF, dp[i - 1][j] + wi[j]);
            }
        }
    }
    int ans = INF;
    for (int i = 0; i <= m; ++i) {
        ans = min(ans, dp[a][i]);
    }
    ans = ans == INF ? -1 : ans;
    printf("%d", ans);
    return 0;
}

Codeforces Round #486 (Div. 3)

A. Diverse Team

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

B. Substrings Sort

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

C. Equal Sums

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

D. Points and Powers of Two

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

E. Divisibility by 25

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

AC代码:

F. Rain and Umbrellas

Description:

Input:

Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Sample Input:

Sample Output:

题目链接

Codeforces 988F Rain and Umbrellas 【dp】

AC代码: