Educational Codeforces Round 76题解报告题目链接A、Two Rival StudentsB、Minimize the PermutationC、Dominated SubarrayD、Yet Another Monster Killing ProblemE、The ContestF、Make Them Similar

71 阅读 0 评论 47 点赞

我是靠谱客的博主结实乐曲，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 76题解报告题目链接A、Two Rival StudentsB、Minimize the PermutationC、Dominated SubarrayD、Yet Another Monster Killing ProblemE、The ContestF、Make Them Similar，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

A、Two Rival Students

【题意、思路、解题过程】

题意大概是长度为n的路，可以将相邻两个数交换至多k次，问两个人最远距离是多少。
思路就是尽量把两个人往两把放即可，水题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n,t,k,a,b;
cin >> t;
while(t--)
{
cin >> n >> k >> a >> b;
int l = min(a,b) - 1;
int r = n - max(a,b);
int sum = l+r;
if(k>=sum)
cout << sum+max(a,b)-min(a,b) <<endl;
else
cout << k+max(a,b)-min(a,b) <<endl;
}
return 0;
}

B、Minimize the Permutation

不是Educational Codeforces Round 76这场比赛的。
这个题应该是放错了，昨天刚做过，过。

C、Dominated Subarray

【题意、思路、解题过程】

题意大概是，问数组中距离最近两个相同的数相距多少。
用了桶排序的思想，记录每个数的位置，如果该数已被记录，那么记录其距离看是否为最小距离。

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=2000010;
int a[maxn];
int p[maxn];
int n;
int main()
{
int t;
cin >> t;
while(t--)
{
cin >> n;
int num=inf;
memset(p,0,sizeof p);
for(int i=1; i<=n; i++)
{
cin >> a[i];
if(p[a[i]])
{
num=min(num,i-p[a[i]]+1);
}
p[a[i]]=i;
}
cout << (num==inf?-1:num) <<endl;
}
return 0;
}

D、Yet Another Monster Killing Problem

【题意、思路、解题过程】

题意大概是，地牢里有n个怪兽，第i怪兽力量为a[i]；共m个英雄，第i个英雄力量s[i]和耐力p[i]。每天你可以派一名英雄去地牢，如果该英雄的力量大于这个怪物的力量，那么英雄就会打败它，否则他会撤退。每打败一只怪物，英雄的耐力会减一，当英雄的耐力为0或者地牢的怪全被打完时或者这只怪物的力量大于该英雄的力量时，该英雄会撤退。问清理地牢最少要花多少天。怪物必须按照顺序去清理。
大体思路是，首先判断英雄力量最大值是否比怪物最大值大，如果英雄大，则继续，反之则无法清理地牢，输出-1.
先将英雄按照力量排序，对英雄的耐力与力量预处理，二分查找力量大于i前所有a[i]的英雄，看其耐力是否将前面的全部处理，如果能，则算在一天，如果不能，则天数加一，具体看代码。
代码里面用了lower_bound，很实用。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5+10;
struct node
{
ll s,p;
} b[N];
bool cmp(node a,node b)
{ return a.s < b.s; }
ll a[N],pp[N],h[N];
int main()
{
ll n,t,m;
cin >> t;
while(t--)
{
cin >> n;
ll maxm=-1,maxh=-1;
for(int i=0; i<n; i++)
{
cin >> a[i];
maxm = max(maxm,a[i]);
}
cin >> m;
for(int i=0; i<m; i++)
{
cin >> b[i].s >> b[i].p;
maxh = max(maxh,b[i].s);
}
if(maxh<maxm)
{
cout << -1 <<endl;
continue;
}
sort(b,b+m,cmp);
ll maxp=-1;
for(int i=m-1;i>=0;i--)
{
maxp = max(maxp,b[i].p);
pp[i] = maxp;
}
for(int i=0; i<m; i++)
h[i] = b[i].s;
maxm = -1;
ll pos,ans=1,day=0;
for(int i=0;i<n;i++)
{
maxm = max(a[i],maxm);
pos = lower_bound(h,h+m,maxm) - h;
if(pp[pos]<(i-day+1))
{
day = i;
maxm = a[i];
ans++;
}
}
cout << ans <<endl;
}
return 0;
}

E、The Contest

【题意、思路、解题过程】

大体题意给三个序列k1,k2,k3，每个序列有一堆数，k1是前缀，k3是后缀，k2是中间，现可以从任意序列中选择一个数加入到另外的序列中，问最小操作次数还原成1-n的原序列（序列内部操作是任意的，不计入操作次数）大
题思路有是k1,k2,k3分别排一下序，然后k1,k2,k3拼成一个序列，求这个序列的最长上升子序列的长度，然后n - lis就是答案。
这道题当时也只是看了看题意，待补