概述
A. Dungeon
题目传送门：
A. Dungeon
题目大意：
三个怪物具有a,b,c的血量，每发射一次炮弹，会对一个怪物造成一点伤害。每发射6次之后，第7次就是蓄力炮，对三个怪物同时造成一点伤害。问三个怪物能不能被同一个蓄力炮同时杀死。
思路：
如果a + b + c 的和sum是9的倍数原因是只有9的倍数才可能被蓄力炮同时秒掉。且min(a,b,c)>=sum/9 ，因为在最后一次蓄力炮之前，每个怪物都不能死。
AC Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int sum=a+b+c;
if(sum%9) printf("NOn");
else
{
int k=sum/9;
if(a>=k&&b>=k&&c>=k) printf("YESn");
else printf("NOn");
}
}
//system("pause");
return 0;
}
B. Find The Array
题目传送门：
B. Find The Array
题目大意：
给你一个序列a，问你能不能构造出一个序列b满足
1、bi % bi+1 == 0 或 bi+1%bi==0
2、
思路：
我们发现
X=1 + a [ 2 ] + 1 + a [ 4 ] + 1 ……
Y=a [ 1 ] + 1 + a [ 3 ] + 1 + a [ 5 ] + ……
Wx = S - X = a [ 1 ] + a [ 3 ] + a [ 5 ] + ……- n/2
Wy = S - Y =a [ 2 ] + a [ 4 ] + a [ 6 ] ……- n/2
Wx + Wy = S - n
那么显然Wx和Wy中必然有以一种 <= (S-n) / 2 。满足题目要求
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[55];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
LL sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum=sum+a[i];
}
LL ans=0;
for(int i=1;i<=n;i=i+2)
ans=ans+a[i]-1;
if(ans*2<=sum)
{
for(int i=1;i<=n;i++)
{
if(i%2) printf("1 ");
else printf("%d ",a[i]);
}
}
else
{
for(int i=1;i<=n;i++)
{
if(i%2) printf("%d ",a[i]);
else printf("1 ");
}
}
printf("n");
}
//system("pause");
return 0;
}
C. Busy Robot
题目传送门：
C. Busy Robot
题目大意：
有n条指令，每条指令为在ti时刻，另机器人向xi点处移动，当机器人正在移动时，机器人会忽略指令，直到完成当前指令。在[ ti , t i+1 ] 时间内，机器人移动到目标点xi，则res++。（注意包括被忽略的指令）
思路：
其实就是一个比较恶心的模拟，具体细节见代码。
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL ti[N],x[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&ti[i],&x[i]);
ti[n+1]=1e10;//将n+1点的时间设置为无限大
int idx=1;
LL now=0,pos=0;
int flag=0,res=0;
while(idx<=n)
{
LL y=pos;
LL b=ti[idx];
now=ti[idx]+abs(x[idx]-pos);
if(x[idx]<pos) flag=-1;//机器人的行进方向
else flag=1;
pos=x[idx];
int k=idx+1;//中间要跳过的指令
while(ti[k]<now&&k<=n)
k++;
for(int i=idx;i<k;i++)
{
LL st=min(ti[i],now);
LL ed=min(ti[i+1],now);
LL stx=y+flag*(st-b);
LL edx=y+flag*(ed-b);
if(x[i]>=min(stx,edx)&&x[i]<=max(stx,edx)) res++;//判断满足条件的指令数量
}
idx=k;
}
printf("%dn",res);
}
//system("pause");
return 0;
}
D. Pairs
题目传送门：
D. Pairs
题目大意
将2n个数，分成n对。其中x对进行取小操作，剩下的数进行取大操作。给你一个n个元素的序列a。问你x可以为多少种数，能得到a数组。
思路：
知道最少有多少个数需要取小得到和最少多少个数需要取大得到。n - 两者的数量 + 1 即为答案。
如何取呢。以计算最少需要取小的数为例。记sum为比当前的数小且不在序列a中且还未被匹配的数。
那么如果sum>0，那么我们就可以找一个比当前小的数，那么当前这一对进行的就是取大的操作。（能进行取大操作就尽量取大，因为我们现在求的是取小的最少次数）
如果sum==0,那么当前这一个数就只能找不在序列中且未匹配的最大的数，进行取小操作。
AC Code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int a[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int minn=0,maxn=0;//取小的最小次数，和取大的最小次数
int sum=0;
for(int i=1;i<=n;i++)
{
sum=sum+a[i]-a[i-1]-1;
if(!sum) minn++;
else sum--;
}
a[n+1]=2*n+1;
sum=0;
for(int i=n;i>=1;i--)
{
sum=sum+a[i+1]-a[i]-1;
if(!sum) maxn++;
else sum--;
}
printf("%dn",n-minn-maxn+1);
}
//system("pause");
return 0;
}
最后
以上就是乐观钥匙为你收集整理的Educational Codeforces Round 100 A—D题题解A. DungeonB. Find The ArrayC. Busy RobotD. Pairs的全部内容，希望文章能够帮你解决Educational Codeforces Round 100 A—D题题解A. DungeonB. Find The ArrayC. Busy RobotD. Pairs所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复