A. Remove Duplicates

Description:

Petya has an array a consisting of n integers. He wants to remove duplicate (equal) elements.

Petya wants to leave only the rightmost entry (occurrence) for each element of the array. The relative order of the remaining unique elements should not be changed.

Input:

The first line contains a single integer n (1≤n≤50) — the number of elements in Petya’s array.

The following line contains a sequence $a_1$a1​, $a_2$a2​,…, $a_n$an​ (1≤ $a_i$ai​≤1000) — the Petya’s array.

Output:

In the first line print integer x — the number of elements which will be left in Petya’s array after he removed the duplicates.

In the second line print x integers separated with a space — Petya’s array after he removed the duplicates. For each unique element only the rightmost entry should be left.

Sample Input:

6
1 5 5 1 6 1

Sample Output:

3
5 6 1

Sample Input:

5
2 4 2 4 4

Sample Output:

2
2 4

Sample Input:

5
6 6 6 6 6

Sample Output:

1
6

题目链接

统计出现数字个数并按照出现顺序倒序输出，统计可以用set作，倒序输出用栈做。

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 = 2e3+5;
const int mod = 1e9+7;
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;
int a[55];
bool vis[1005];
int cnt = 0;
set<int> num;
stack<int> sta;

int main() {
    fre();
    mem(vis, 0);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        if (!num.count(a[i])) {
            num.insert(a[i]);
            cnt++;
        }
    }
    printf("%d\n", cnt);
    for (int i = n - 1; i >= 0; --i) {
        if (!vis[a[i]]) {
            sta.push(a[i]);
            vis[a[i]] = 1;
        }
    }
    printf("%d", sta.top());
    sta.pop();
    while (!sta.empty()) {
        printf(" %d", sta.top());
        sta.pop();
    }
    return 0;
}

B. File Name

Description:

You can not just take the file and send it. When Polycarp trying to send a file in the social network “Codehorses”, he encountered an unexpected problem. If the name of the file contains three or more “x” (lowercase Latin letters “x”) in a row, the system considers that the file content does not correspond to the social network topic. In this case, the file is not sent and an error message is displayed.

Determine the minimum number of characters to remove from the file name so after that the name does not contain “xxx” as a substring. Print 0 if the file name does not initially contain a forbidden substring “xxx”.

You can delete characters in arbitrary positions (not necessarily consecutive). If you delete a character, then the length of a string is reduced by 1. For example, if you delete the character in the position 2 from the string “exxxii”, then the resulting string is “exxii”.

Input:

The first line contains integer n (3≤n≤100) — the length of the file name.

The second line contains a string of length n consisting of lowercase Latin letters only — the file name.

Output:

Print the minimum number of characters to remove from the file name so after that the name does not contain “xxx” as a substring. If initially the file name dost not contain a forbidden substring “xxx”, print 0.

Sample Input:

6
xxxiii

Sample Output:

1

Sample Input:

5
xxoxx

Sample Output:

0

Sample Input:

10
xxxxxxxxxx

Sample Output:

8

题目链接

统计删除几个x字符串中才能够不存在三个连续的x，枚举每个字符，通过记录前两个字符判断计数即可。

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 = 2e3+5;
const int mod = 1e9+7;
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;
string str;
char path_path = str[0], path = str[1];
int cnt = 0;

int main() {
    //fre();
    scanf("%d", &n);
    cin >> str;
    for (int i = 2; str[i] != '\0'; ++i) {
        char now = str[i];
        if (now == 'x') {
            if (path == 'x' && path_path == 'x') {
                cnt++;
                continue;
            }
            else {
                path_path = path;
                path = now;
            }
        }
        else {
            path_path = path;
            path = now;
        }
    }
    printf("%d", cnt);
    return 0;
}

C. Letters

Description:

There are n dormitories in Berland State University, they are numbered with integers from 1 to n. Each dormitory consists of rooms, there are ai rooms in i-th dormitory. The rooms in i-th dormitory are numbered from 1 to $a_i$ai​.

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all n dormitories is written on an envelope. In this case, assume that all the rooms are numbered from 1 to $a_1+a_2+?+a_n$a1​+a2​+?+an​ and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.

For example, in case n=2, $a_1$a1​=3 and $a_2$a2​=5 an envelope can have any integer from 1 to 8 written on it. If the number 7 is written on an envelope, it means that the letter should be delivered to the room number 4 of the second dormitory.

For each of m letters by the room number among all n
dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.

Input:

The first line contains two integers n and m ( $1\le n,m\le 2?10^5$1≤n,m≤2?105) — the number of dormitories and the number of letters.

The second line contains a sequence $a_1,a_2,…,a_n $( $1\le ai\le 10^{10}$1≤ai≤1010), where $a_i$ai​ equals to the number of rooms in the i-th dormitory. The third line contains a sequence $b_1,b_2,\dots ,b_m$b1​,b2​,…,bm​ ( $1\le b_j\le a_1+a_2+?+a_n$1≤bj​≤a1​+a2​+?+an​), where $b_j$bj​ equals to the room number (among all rooms of all dormitories) for the j-th letter. All $b_j$bj​ are given in increasing order.

Output:

Print m lines. For each letter print two integers f and k — the dormitory number f (1≤f≤n) and the room number k in this dormitory (1≤k≤ $a_f$af​) to deliver the letter.

Sample Input:

3 6
10 15 12
1 9 12 23 26 37

Sample Output:

1 1
1 9
2 2
2 13
3 1
3 12

Sample Input:

2 3
5 10000000000
5 6 9999999999

Sample Output:

1 5
2 1
2 9999999994

题目链接

每组数据n个宿舍，m封信。每个宿舍都有相应的房间数，输入送信总房间号，求宿舍号及宿舍内房间号。
在输入宿舍房间数时用一个sum数组记录总房间数，之后用二分快速找到第一个大于等于信封对应房间号的值，通过下标、信封对应房间号和到此下标宿舍的总房间数即可确定答案。

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 int mod = 1e9+7;
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;
ll a[maxn], sum[maxn];
ll ask;
ll _left, _right;
ll mid;

int main() {
    //fre();
    scanf("%d%d", &n, &m);
    scanf("%I64d", &a[1]);
    sum[1] = a[1];
    for (int i = 2; i <= n; ++i) {
        scanf("%I64d", &a[i]);
        sum[i] = a[i] + sum[i - 1];
    }
    while (m--) {
        scanf("%I64d", &ask);
         _left = 0, _right = n;
        while (_left < _right) {
            mid = (_left + _right) >> 1;
            if (sum[mid] >= ask) {
                _right = mid;
            }
            else {
                _left = mid + 1;
            }
        }
        printf("%I64d %I64d\n", _left, ask - sum[_left - 1]);
    }
    return 0;
}

D. Almost Arithmetic Progression

Description:

Polycarp likes arithmetic progressions. A sequence [ $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​] is called an arithmetic progression if for each i ( $1\le i\&lt;n$1≤i<n) the value $a_i+1?a_i$ai​+1?ai​ is the same. For example, the sequences [42], [5,5,5], [2,11,20,29] and [3,2,1,0] are arithmetic progressions, but [1,0,1], [1,9,9] and [2,3,1] are not.

It follows from the definition that any sequence of length one or two is an arithmetic progression.

Polycarp found some sequence of positive integers [ $b_1,b_2,\dots ,b_n$b1​,b2​,…,bn​]. He agrees to change each element by at most one. In the other words, for each element there are exactly three options: an element can be decreased by 1, an element can be increased by 1, an element can be left unchanged.

Determine a minimum possible number of elements in b which can be changed (by exactly one), so that the sequence b becomes an arithmetic progression, or report that it is impossible.

It is possible that the resulting sequence contains element equals 0.

Input:

The first line contains a single integer n (1≤n≤100000) — the number of elements in b.

The second line contains a sequence $b_1,b_2,\dots ,b_n(1\le b_i\le 10^9)$b1​,b2​,…,bn​(1≤bi​≤109).

Output:

If it is impossible to make an arithmetic progression with described operations, print -1. In the other case, print non-negative integer — the minimum number of elements to change to make the given sequence becomes an arithmetic progression. The only allowed operation is to add/to subtract one from an element (can’t use operation twice to the same position).

Sample Input:

4
24 21 14 10

Sample Output:

3

Sample Input:

2
500 500

Sample Output:

0

Sample Input:

3
14 5 1

Sample Output:

-1

Sample Input:

5
1 3 6 9 12

Sample Output:

1

题目链接

给定一个数列，每个数都可以 $+1\mid \mid -1\mid \mid +0$+1∣∣−1∣∣+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 = 1e5+5;
const int mod = 1e9+7;
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;
int a[maxn];
int ans = INF;
int d, s, x, k;

int main() {
    //fre();
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = -1; i < n; ++i) {
        for (int j = -1; j <= 1; ++j) {
            d = (a[1] + j) - (a[0] + i);
            s = abs(i);
            for (k = 1; k < n; ++k) {
                x = abs(a[k] - (a[0] + i + k * d));
                if (x > 1) {
                    break;
                }
                s += x;
            }
            if (k == n) {
                ans = min(ans, s);
            }
        }
    }
    ans = ans == INF ? -1 : ans;
    printf("%d", ans);
    return 0;
}

E. Bus Video System

Description:

The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops.

If x is the number of passengers in a bus just before the current bus stop and y is the number of passengers in the bus just after current bus stop, the system records the number y?x. So the system records show how number of passengers changed.

The test run was made for single bus and n bus stops. Thus, the system recorded the sequence of integers $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​ (exactly one number for each bus stop), where ai is the record for the bus stop i. The bus stops are numbered from 1 to n in chronological order.

Determine the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to w (that is, at any time in the bus there should be from 0 to w passengers inclusive).

Input:

The first line contains two integers n and w (1≤n≤1000,1≤w≤ $10^9$109) — the number of bus stops and the capacity of the bus.

The second line contains a sequence $a_1,a_2,\dots ,a_n(?10^6\le a_i\le 10^6)$a1​,a2​,…,an​(?106≤ai​≤106), where ai equals to the number, which has been recorded by the video system after the i-th bus stop.

Output:

Print the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to w. If the situation is contradictory (i.e. for any initial number of passengers there will be a contradiction), print 0.

Sample Input:

3 5
2 1 -3

Sample Output:

3

Sample Input:

2 4
-1 1

Sample Output:

4

Sample Input:

4 10
2 4 1 2

Sample Output:

2

题目链接

给定公交站数量和公交车最大载客量，通过每一站乘客上下车情况判断车上最初乘客数量可能的情况总数。记录过程中车上最小乘客数和最大乘客数，判断可能数量。

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 = 1e3+5;
const int mod = 1e9+7;
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, w;
ll maxx, minn, num;
int input;
bool flag;
ll ans;

int main() {
    //fre();
    scanf("%d%d", &n, &w);
    maxx = -INF, minn = INF, num = 0;
    flag = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &input);
        num += input;
        if (abs(num) > w) {
            flag = 0;
        }
        if (!flag) {
            continue;
        }
        if (num > maxx) {
            maxx = num;
        }
        if (num < minn) {
            minn = num;
        }
    }
    if (maxx < 0) {
        ans = w - abs(minn) + 1;
    }
    else {
        if (minn < 0) {
            w -= maxx;
            ans = w - abs(minn) + 1;
        }
        else {
            ans = w - maxx + 1;
        }
    }
    if (!flag || ans < 0) {
        ans = 0;
    }
    printf("%I64d", ans);
    return 0;
}

F. Mentors

Description:

In BerSoft n programmers work, the programmer i is characterized by a skill $r_i$ri​.

A programmer a can be a mentor of a programmer b if and only if the skill of the programmer a is strictly greater than the skill of the programmer b ( $r_a\&gt;r_b$ra​>rb​) and programmers a and b are not in a quarrel.

You are given the skills of each programmers and a list of k pairs of the programmers, which are in a quarrel (pairs are unordered). For each programmer i, find the number of programmers, for which the programmer i can be a mentor.

Input:

The first line contains two integers n and k $(2\le n\le 2\times 10^5,0\le k\le min(2\times 10^5,\frac{n\times (n\times 1)}{2}\left)\right)$(2≤n≤2×105,0≤k≤min(2×105,2n×(n×1)​)) — total number of programmers and number of pairs of programmers which are in a quarrel.

The second line contains a sequence of integers $r_1,r_2,\dots ,r_n(1\le ri\le 10^9)$r1​,r2​,…,rn​(1≤ri≤109), where ri equals to the skill of the i-th programmer.

Each of the following k lines contains two distinct integers x, y (1≤x,y≤n, x≠y) — pair of programmers in a quarrel. The pairs are unordered, it means that if x is in a quarrel with ythen y is in a quarrel with x. Guaranteed, that for each pair (x,y) there are no other pairs (x,y) and (y,x) in the input.

Output:

Print n integers, the i-th number should be equal to the number of programmers, for which the i-th programmer can be a mentor. Programmers are numbered in the same order that their skills are given in the input.

Sample Input:

4 2
10 4 10 15
1 2
4 3

Sample Output:

0 0 1 2

Sample Input:

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

Sample Output:

5 4 0 5 3 3 9 0 2 5

题目链接

n个人，k对数据，每个人有一个值r，此人可以收r值比他小的人做徒弟，k对数据中两个人不能建立师徒关系，统计每个人可以收的徒弟数。
用一个数组记录无法建立关系数，在输入k对数据时将此人无法建立关系数+1，之后将r排序，枚举每个人，二分找到第一个小于枚举r的位置，计算小于枚举r的总人数，减去记录的不能建立关系数即为所求答案。

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 int mod = 1e9+7;
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);
}

struct ac {
    int v, s;
    int qua;
};

int n, k;
int minn;
int u, v;
int temp;
int _l, _r;
int ans[maxn];
ac s[maxn];
//bool qua[maxn];

bool cmp(ac a, ac b) {
    return a.s > b.s;
}

int main() {
    //fre();
    scanf("%d%d", &n, &k);
    minn = INF;
    for (int i = 1; i <= n; ++i) {
        s[i].v = i;
        s[i].qua = 0;
        scanf("%d", &s[i].s);
        if (s[i].s < minn) {
            minn = s[i].s;
        }
    }
    while (k--) {
        scanf("%d%d", &u, &v);
        if (s[u].s == s[v].s) {
            continue;
        }
        else if (s[u].s > s[v].s) {
            temp = s[u].v;
        }
        else {
            temp = s[v].v;
        }
        s[temp].qua++;
    }
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        if (s[i].s == minn) {
            ans[s[i].v] = 0;
            continue;
        }
        _l = 1, _r = n;
        while (_l < _r) {
            int mid = (_l + _r) >> 1;
            if (s[mid].s >= s[i].s) {
                _l = mid + 1;
            }
            else {
                _r = mid;
            }
        }
        ans[s[i].v] = n - _l + 1 - s[i].qua;
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d ", ans[i]);
    }
    return 0;
}

G. Petya’s Exams

Description:

Petya studies at university. The current academic year finishes with n special days. Petya needs to pass m exams in those special days. The special days in this problem are numbered from 1 to n.

There are three values about each exam:

• $s_i$si​ — the day, when questions for the i-th exam will be published,
• $d_i$di​ — the day of the i-th exam ( $s_i$si​ < $d_i$di​),
• $c_i$ci​ — number of days Petya needs to prepare for the i-th exam. For the i-th exam Petya should prepare in days between si and di?1, inclusive.

There are three types of activities for Petya in each day: to spend a day doing nothing (taking a rest), to spend a day passing exactly one exam or to spend a day preparing for exactly one exam. So he can’t pass/prepare for multiple exams in a day. He can’t mix his activities in a day. If he is preparing for the i-th exam in day j, then $s_i\le j\&lt;d_i$si​≤j<di​.

It is allowed to have breaks in a preparation to an exam and to alternate preparations for different exams in consecutive days. So preparation for an exam is not required to be done in consecutive days.

Find the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.

Input:

The first line contains two integers n and m (2≤n≤100,1≤m≤n) — the number of days and the number of exams.

Each of the following m lines contains three integers $s_i,d_i,c_i(1\le s_i\&lt;d_i\le n,1\le c_i\le n$si​,di​,ci​(1≤si​<di​≤n,1≤ci​≤n) — the day, when questions for the i-th exam will be given, the day of the i-th exam, number of days Petya needs to prepare for the i-th exam.

Guaranteed, that all the exams will be in different days. Questions for different exams can be given in the same day. It is possible that, in the day of some exam, the questions for other exams are given.

Output:

If Petya can not prepare and pass all the exams, print -1. In case of positive answer, print nintegers, where the j-th number is:

• (m+1), if the j-th day is a day of some exam (recall that in each day no more than one exam is conducted),
• zero, if in the j-th day Petya will have a rest,
• i (1≤i≤m), if Petya will prepare for the i-th exam in the day j (the total number of days Petya prepares for each exam should be strictly equal to the number of days needed to prepare for it).

Assume that the exams are numbered in order of appearing in the input, starting from 1.

If there are multiple schedules, print any of them.

Sample Input:

5 2
1 3 1
1 5 1

Sample Output:

1 2 3 0 3

Sample Input:

3 2
1 3 1
1 2 1

Sample Output:

-1

Sample Input:

10 3
4 7 2
1 10 3
8 9 1

Sample Output:

2 2 2 1 1 0 4 3 4 4

题目链接

有n天准备m场测试，每场测试有开始时间、考试时间和所需复习时间，输出每一天的复习或考试情况。
按照考试时间升序结构体排序，从开始时间筛选所需复习天数天无安排天数。

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-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);
}

struct ac {
    int num;
    int s;
    int d;
    int c;
};

int n, m;
ac ex[maxn];
int ans[maxn];
bool flag;
int cnt;

bool cmp(ac a, ac b) {
    return a.d < b.d;
}

int main() {
    //fre();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        ex[i].num = i;
        scanf("%d%d%d", &ex[i].s, &ex[i].d, &ex[i].c);
    }
    sort(ex + 1, ex + m + 1, cmp);
    mem(ans, -1);
    flag = 1;
    for (int i = 1; i <= m; ++i) {
        cnt = 0;
        int j;
        for (j = ex[i].s; j < ex[i].s + ex[i].c + cnt; ++j) {
            if (j >= ex[i].d) {
                flag = 0;
                break;
            }
            if (ans[j] == -1) {
                ans[j] = ex[i].num;
            }
            else {
                cnt++;
            }
        }
        if (!flag) {
            break;
        }
        if (ans[ex[i].d] == -1) {
            ans[ex[i].d] = m + 1;
        }
        else {
            flag = 0;
            break;
        }
    }
    if (!flag) {
        printf("-1");
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == -1) {
            ans[i] = 0;
        }
        printf("%d ", ans[i]);
    }
    return 0;
}