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