A. Dungeon
题目传送门：
A. Dungeon
题目大意：
三个怪物具有a,b,c的血量，每发射一次炮弹，会对一个怪物造成一点伤害。每发射6次之后，第7次就是蓄力炮，对三个怪物同时造成一点伤害。问三个怪物能不能被同一个蓄力炮同时杀死。
思路：
如果a + b + c 的和sum是9的倍数原因是只有9的倍数才可能被蓄力炮同时秒掉。且min(a,b,c)>=sum/9 ，因为在最后一次蓄力炮之前，每个怪物都不能死。
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#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内容请搜索靠谱客的其他文章。
发表评论 取消回复