Codeforces|Codeforces Round #481 (Div. 3) 全题解 CodeforcesRound#481(Div.3)全题解

【Codeforces|Codeforces Round #481 (Div. 3) 全题解】A题，题目链接：http://codeforces.com/contest/978/problem/A
解题心得：题意就是让你将这个数列去重，重复的数只保留最右边的那个，最后按顺序打印数列。set+map。

#include using namespace std; const int maxn = 100; int num[maxn],n; map map1,map2; set se; int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d", &num[i]); se.insert(num[i]); map1[num[i]]++; } printf("%d\n",se.size()); for(int i=1; i<=n; i++) { map2[num[i]]++; if(map2[num[i]] == map1[num[i]]) printf("%d ",num[i]); } return 0; }

B题，题目链接http://codeforces.com/contest/978/problem/B
解题心得：让你将字符串中的包含xxx的子串去掉，字符串去掉一个字母之后会自动拼接，问你最少需要去掉多少个字符。一个尺取，三个三个的判断只要有一个xxx就去掉一个字符。

#include using namespace std; const int maxn = 110; char s[maxn]; int main() { int n; scanf("%d",&n); scanf("%s",s+1); int ans = 0; for(int i=1; i<=n-2; i++) { if(s[i] == 'x' && s[i+1] == 'x' && s[i+2] == 'x') { ans++; } } printf("%d",ans); return 0; }

C题，题目链接http://codeforces.com/contest/978/problem/C
解题心得：有ｎ个宿舍群排成一行，每个宿舍群有ai个宿舍，编号1-ai，现在m次询问，问你第ｋ个宿舍在第几个宿舍群的编号。可以先得到前缀和，然后使用二分查找。

#include using namespace std; const int maxn = 2e5+100; typedef long long ll; ll sum[maxn],n,m; void init() { scanf("%lld%lld",&n,&m); for(int i=1; i<=n; i++) { ll temp; scanf("%lld",&temp); sum[i] = sum[i-1] + temp; } }int main() { init(); while(m--) { ll qu; scanf("%lld",&qu); ll pos = lower_bound(sum+1,sum+1+n,qu) - sum; printf("%lld %lld\n",pos,qu-sum[pos-1]); } return 0; }

D题，题目链接http://codeforces.com/contest/978/problem/D
解题心得：题意是给你一个数列，你可以操作一次将一个数+1,-1或者不变，现在要让这个数列变成等差数列，问最少需要操作多少次，如果不能变成等差数列直接输出-1。这个题可以先直接用第二个数减第一个数，得到一个公差，然后枚举这个公差+１、-１、+2、-2，然后枚举第一个数+0、-1、+1作为首项，然后判断是否符合条件，然后得到最小值。

#include using namespace std; const int maxn = 2e5 + 100; typedef long long ll; ll n, num[maxn]; void init() { scanf("%lld", &n); for (int i = 0; i < n; i++) scanf("%lld", &num[i]); }ll get_ans(ll tol) { ll cnt[3],st; cnt[0] = cnt[1] = cnt[2] = 0; for(int i=0; i<3; i++) { if(i == 0) st = num[0]-1; else if(i == 1) st = num[0]; else st = num[0] + 1; for (ll j = 0; j < n; j++) { if(abs(num[j]-st) > 1) { cnt[i] = INT_MAX; break; } cnt[i] += abs(num[j] - st); st += tol; } } if(cnt[0] == cnt[1] && cnt[1] == cnt[2] && cnt[0] == INT_MAX) //无法组成等差数列返回-1 return -1; return min(cnt[0], min(cnt[1], cnt[2])); }int main() { init(); ll Min = INT_MAX,tol; tol = num[1]-num[0]; ll ans = get_ans(tol); if(ans >= 0) Min = min(Min, ans); for (int i = 1; i <= 2; i++) { ans = get_ans(tol-i); if (ans >= 0) Min = min(Min, ans); ans = get_ans(tol+i); if (ans >= 0) Min = min(Min, ans); }if (Min == INT_MAX) printf("-1"); else printf("%lld", Min); return 0; }

E题，题目链接http://codeforces.com/contest/978/problem/E
解题心得：现在有一个公交车，起始里面有多少个人并不知道，现在这个公交车前面有n个站点，公交车的容量为m，每一个站点有一个数x，x如果为一个正数则代表在这个站点要上x人，如果为负数代表要下x人，问这个车在起始时里面人数的可能性。就是一个脑筋急转弯的问题，先假设车上人数为0，然后用一个数k代表现在车上人数的总和，记录k的最大值，如果下车人数大于k，说明假设车上人数为０是错误的，记录超过的人数，直接在最大值上面加上超过的人数，然后将k初始化为0，继续记录。在记录最大值的时候还要判断一下是否超过了车的容量。

#include using namespace std; const int maxn = 1010; typedef long long ll; int n,num[maxn],w; void init() { scanf("%d%d",&n,&w); for(int i=0; i w) printf("0"); else printf("%d",w-Max+1); return 0; }

F题，题目链接：http://codeforces.com/contest/978/problem/F
解题心得：题意就是每个人有一个工作能力值，工作能力大的人可以做工作能力小的人的领导，但是如果他们之间有矛盾则不能成为领导关系。现在给你ｎ个人的能力值和m个矛盾关系，要求输出每一个人的领导有多少个。一个二分查找。先把每一个人的能力值独立出来，排序，然后二分查找得出这个人的领导有多少个，然后处理矛盾关系，每处理一个能力关系工作能力小的那个人的领导数目-1。

#include using namespace std; const int maxn = 2e5 + 1010; typedef long long ll; struct NODE { int va,ans; }node[maxn]; int n,k,num[maxn]; void init() { scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) { scanf("%d",&node[i].va); num[i] = node[i].va; } sort(num+1,num+1+n); for(int i=1; i<=n; i++) { NODE k = node[i]; node[i].ans =lower_bound(num+1,num+1+n,k.va) - num - 1; } }int main() { init(); while(k--) { int a,b; scanf("%d%d",&a,&b); if(node[a].va < node[b].va) { node[b].ans--; } else if(node[b].va < node[a].va) { node[a].ans--; } } for(int i=1; i<=n; i++) printf("%d ",node[i].ans); return 0; }

G题，题目链接：http://codeforces.com/contest/978/problem/G
解题心得：小明有n门考试，每一门考试有一个试题公布时间s，考试时间e，小明需要准备复习的时间，复习时间必须在试题公布时间和考试时间之内。小明在每一天可以选择复习、考试（如果有必须进行）、休息中的一个，现在总共有m天要你给小明安排一个时间，让小明能够充分复习不挂科，输出每一天小明做的事情，如果不能充分复习不挂科输出-1。　其实就是一个贪心的策略，先按照结束时间排序，先选出结束时间短的考试，安排复习从试题公布时间开始依次向后安排（假设那一天没安排事情，否则向后推）。

#include #include #include #include using namespace std; const int maxn = 110; struct Exam { int s,e,days,num; bool operator < (const Exam& a) const { return a.e > e; }}exam[maxn]; int doing[maxn],n,m; void init() { scanf("%d%d",&m,&n); for(int i=1; i<=n; i++) { scanf("%d%d%d",&exam[i].s,&exam[i].e,&exam[i].days); exam[i].num = i; } sort(exam+1,exam+n+1); }int solve() { for(int i=1; i<=n; i++) { int st = exam[i].s; while(exam[i].days) { if(st == exam[i].e) return -1; if(!doing[st]) { doing[st] = exam[i].num; exam[i].days--; } st++; } doing[exam[i].e] = n+1; } return 1; }int main() { init(); int ans = solve(); if(ans < 0) { printf("%d",ans); } else { for(int i=1; i<=m; i++) { printf("%d ",doing[i]); } } return 0; }

比赛心得：
第一次打Div3，真的很简单，大佬们做题贼快，AK的人好多。当时在打这个比赛的时候被D题给卡住了，还以为是一个dp，写了一个二分+dp的东西，弄了好久都没搞出来，心里面贼慌。几乎都没什么难度排序了，难度都是一样的，这样真的很考验手速和读题。感觉打Div3比打Div2还累，Div2还有挂机的时候，Div3全程码代码，对于我这种读题慢的人来说打Div3就是在做英语阅读题。还说Div3很简单，但是好多的大佬打Div3，该掉分的同样掉分，弱鸡在厕所哭泣。
转载于:https://www.cnblogs.com/GoldenFingers/p/9107099.html