Codeforces Round #481 (Div. 3) ABCDEFG

xiaoxiao2021-02-28  4

A. Remove Duplicates

传送门:http://codeforces.com/contest/978/problem/A

题目大意:

  给出n个数字,去重,按每个数字最后出现的位置输出。

思路:

  从最后开始查,不重复就入栈,之后输出栈中所有元素。

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e10 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; int n; int a[1010]; int b[1010]; stack<int> ans; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> b[i]; for (int i = n - 1; i >= 0; i--) { if (a[b[i]] == 0) { ans.push(b[i]); a[b[i]] = 1; } } cout << ans.size() << endl; while (!ans.empty()) { cout << ans.top() << ' '; ans.pop(); } cout << endl; return 0; }

B. File Name

传送门:http://codeforces.com/contest/978/problem/B

题目大意:

  给出长为n的字符串,若其中有"xxx",则替换为"xx",问至少替换几次。

思路:

  暴力搜索下,记录连续出现x的个数,3个了答案就+1,并且记录个数变为2,每当一个字符不为x的时候,记录清0。

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e10 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; int n; char a[110]; int main() { cin >> n; getchar(); for (int i = 0; i < n; i++) cin >> a[i]; int cnt = 0, ans = 0; for (int i = 0; i < n; i++) { if (a[i] == 'x') cnt++; else cnt = 0; if (cnt == 3) { cnt--; ans++; } } cout << ans << endl; return 0; }

C. Letters

传送门:http://codeforces.com/contest/978/problem/C

题目大意:

  有n个宿舍,分别有a1,a2,……,an个房间,对于这些房间都有唯一编号,如第一个宿舍的第1个房间编号为1,第二个宿舍的第1个房间的编号就为a1+1。给出n个查询问是第几个宿舍的第几个房间。

思路:

  算前项和,之后找到第一个大于等于的前项和,说明在那个宿舍,之后减一减就是房间号了。

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e10 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; ll n, m; ll a[200010]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2; i <= n; i++) a[i] += a[i - 1]; ll x; while (m--) { cin >> x; int ans = lower_bound(a + 1, a + n + 1, x) - (a + 1); ans++; cout << ans << ' ' << x - a[ans - 1] << endl; } return 0; }

D. Almost Arithmetic Progression

传送门:http://codeforces.com/contest/978/problem/D

题目大意:

  给出n个数字,问这n个数字经过一次+1或-1(或根本不变化),能否组成等差数列。

思路:

  枚举最前的2个数(一共9个组合),求出公差,之后判断后面的数是否能经过改动维持这个公差。记录这9次中变动的最小值即为答案,如果没有一次能成为等差数列则输出-1。

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e9 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; int n; int a[100010]; int b[100010]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; int ans = INF; for(int x=-1;x<=1;x++) for (int y = -1; y <= 1; y++) { for (int i = 1; i <= n; i++) b[i] = a[i]; b[1] += x;b[2] += y; int cha = b[2] - b[1]; int aa = abs(x) + abs(y); for (int i = 3; i <= n; i++) { if (abs(b[i] - b[i - 1] - cha) > 1) { aa = INF; break; } aa += abs(b[i] - b[i - 1] - cha); b[i] = b[i - 1] + cha; } ans = min(ans, aa); } if (ans == INF) ans = -1; cout << ans << endl; return 0; }

E. Bus Video System

传送门:http://codeforces.com/contest/978/problem/E

题目大意:

  一辆公交车,最大容量为w,会经过n站,每站都会有人数变化,问最开始公交车里人数的情况有多少中。(所有站中人数不能超上限,也不能小于0)

思路:

  计算前项和,取出前项和中最大值和最小值,(容量w-最大值)为开始时可以有的最大人数,(0-最小值)为开始时可以有的最小人数。

  注意当最大值小于0时需要置为0,最小值大于0时也需要置为0。

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e10 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; int n, w; int a[1010]; int main() { cin >> n >> w; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 2; i <= n; i++) a[i] += a[i - 1]; int maxx = -1, minn = 1000000001; for (int i = 1; i <= n; i++) { maxx = max(maxx, a[i]); minn = min(minn, a[i]); } if (minn > 0) minn = 0; if (maxx < 0) maxx = 0; int ans = (w - maxx) - (0 - minn) + 1; if (ans < 0) ans = 0; cout << ans << endl; return 0; }

F. Mentors

传送门:http://codeforces.com/contest/978/problem/F

题目大意:

  n个人都有能力值r,并且有k对人会吵架,当a的能力值大于b的能力值并且a、b不吵架的话,a就能指导b。问这n个人每人能指导多少人。

思路:

  答案为(能力值小于该人的人数-能力值小于该人并且两人在吵架的人数),这个式子的前面一项只要将能力值排序,用lower_bound就找到了,而后面一项则可以在输入吵架对的时候,将能力值大的人的结果值直接-1即可。

  所以按着(-能力值小于该人并且两人在吵架的人数+能力值小于该人的人数)这个顺序来操作就行了。

 

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e10 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; int n, m; int rr[200010]; int r[200010]; int ans[200010]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> r[i]; rr[i] = r[i]; } int x, y; for (int i = 1; i <= m; i++) { cin >> x >> y; if (r[x] > r[y]) ans[x]--; else if (r[y] > r[x]) ans[y]--; } sort(r + 1, r + n + 1); for (int i = 1; i <= n; i++) { ans[i] += lower_bound(r + 1, r + n + 1, rr[i]) - r - 1; cout << ans[i] << ' '; } cout << endl; return 0; }

G. Petya's Exams

传送门:http://codeforces.com/contest/978/problem/G

题目大意:

  P有n天以及m场考试。对于每场考试,都有可以开始复习的日子s,考试的日子d,需要复习的天数c。问是否能列出计划使每场考试都能在考前复习完。

思路:

  首先将d先加入到答案数组中。之后先按s排序,将s最小的放最前。之后用一个优先队列,按照d排序,从第一天开始到第n天,这一天如果不考试,都取出队列最前的那场考试复习,如果这场考试的时间已经过了,那么直接输出-1表示无法完成。第n天之后,如果队列还没空,说明还有没复习完的,输出-1表示无法完成,否则输出答案数组。

AC代码:

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<algorithm> #include<utility> #include<queue> #include<vector> #include<set> #include<stack> #include<cmath> #include<map> #define P pair<int,int> #define ll long long #define INF 1e10 #define M 1e9+7 #define MAX 500010 #define lson id*2,l,mid #define rson id*2+1,mid+1,r using namespace std; struct node { int no; int s; int e; }; int n, m; int ans[110]; int num[110]; node a[110]; bool cmp(node a, node b) { if (a.s == b.s) return a.e < b.e; return a.s < b.s; } struct cmp1 { bool operator()(node a, node b) { return a.e > b.e; } }; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) a[i].no = i; for (int i = 1; i <= m; i++) cin >> a[i].s >> a[i].e >> num[i]; for (int i = 1; i <= m; i++) ans[a[i].e] = m + 1; sort(a + 1, a + m + 1, cmp); int cnt = 1; priority_queue<node, vector<node>, cmp1> que; for (int i = 1; i <= n; i++) { while (a[cnt].s == i) que.push(a[cnt++]); if (ans[i] != 0) continue; if (!que.empty()) { if (que.top().e < i) { cout << -1 << endl; return 0; } ans[i] = que.top().no; num[que.top().no]--; if (num[que.top().no] == 0) que.pop(); } } if (!que.empty()) cout << -1 << endl; else { for (int i = 1; i <= n; i++) cout << ans[i] << ' '; cout << endl; } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2649954.html

最新回复(0)