Java编程

牛客网算法竞赛

~__~花了大半个小时水了点题,将究看看。

比赛首页 A 大吉大利,今晚吃鸡——枪械篇 21035827

在绝地求生(吃鸡)游戏里,不同的枪支有不同的威力,更是可以搭配不同的配件,以提升枪支的性能。

牛客网算法竞赛

每一把枪都有其威力及其可装备配件种类。每一个配件有其所属种类,可以为枪支提供威力的百分比加成。每一把枪只能装备一个同类配件。给你n把枪支和m个配件,枪的威力为p,可装备的配件数量为k,为k个不同类型的配件,同种类配件只可以装备一个。配件种类用数字q表示,配件威力加成用一个小数b表示。请你挑选一把枪并为其搭配配件使其威力最大。

假设一把枪的威力是p,装配的k个配件的威力加成是bi,那么枪最后的威力w=p*(1+b1+b2+…+bk)。

题目思路:枚举所有的配件,只统计出每种型号的配件的可提供的最高伤害;然后依次枚举每种枪械。

1 提交的代码 2 3 提交时间:2018-01-21 语言:C++ 运行时间: 56 ms 占用内存:3556K 状态:答案正确 4 5 #include cstdio 6 #include iostream // 7 #include cmath 8 #include algorithm 9 #include queue 10 #include cstring //18:5811 using namespace std;12 #define ll long long13 struct gun14 {15 double power; //g[i]的最高伤害16 int vt; //配件个数17 int v[1001];18 }g[1001];19 struct Sub{20 double maxx;21 } sub[1010]; //配件结构体,sub[i].maxx代表第i个型号配件可以提供的最高伤害加成22 bool cmp(gun a,gun b){23 return a.power b.power;24 }25 int main(){26 27 int n,m,t;double k;28 while(scanf(“%d%d”,&n,&m)!=EOF){29 for(int i=1;i =n;i++){30 31 scanf(“%lf%d”,&g[i].power,&g[i].vt);32 for(int j=1;j =g[i].vt;j++){33 scanf(“%d”,&g[i].v[j]); //有的配件数组34 }35 }36 for(int i=1;i =1000;i++){37 sub[i].maxx=0.0;38 }39 for(int i=1;i =m;i++){ //每读入一次数据进行更新最大值40 scanf(“%d%lf”,&t,&k);41 sub[t].maxx=sub[t].maxx k?sub[t].maxx:k;42 }43 44 for(int i=1;i =n;i++){ //每个枪械进行更新45 double mm=0;46 for(int j=1;j = g[i].vt;j++) //枚举每个型号的配件47 mm+=sub[g[i].v[j]].maxx;48 g[i].power=g[i].power*(1.0+mm);49 }50 51 sort(g+1,g+1+n,cmp); //逆序排序52 printf(“%.4lf\n”,g[1].power);53 }54 55 56 return 0;57 }

View Code

比赛首页 I 找数字个数 21031579

lulu喜欢小于等于1000的正整数,但是如果某个数是a或b的倍数,lulu会讨厌这个数。如果某个数里包含了a和b两个数里包含的数,lulu也会讨厌。(例如a=14,b=23,如果数字中包含1、2、3、4这四个数中的任意一个数,lulu就会讨厌这个数)。现在告诉你a,b,你能说出lulu喜欢的数有多少个么。

题目分析:水题。@疯子磊 的思路:可以主动去重,第一遍for(1-》1000)去除a的倍数和b的倍数,第二遍for(1-》1000)去除含a和b的数字的数,然后输出剩余总数——这样时间复杂度一般比我的思路要低(极端情况下一样)。自行尝试。

1 提交的代码 2 3 提交时间:2018-01-21 语言:C++ 运行时间: 6 ms 占用内存:484K 状态:答案正确 4 5 #include cstdio 6 #include iostream // 7 #include cmath 8 #include algorithm 9 #include queue 10 #include cstring //18:5811 using namespace std;12 #define ll long long13 int fact(int i,int a,int b)14 {15 int j;16 int vis1[10]={0},vis2[10]={0};17 while(i 0){18 vis1[i%10]=1;i/=10;19 }20 while(a 0){21 vis2[a%10]=1;a/=10;22 }23 while(b 0){24 vis2[b%10]=1;b/=10;25 }26 for(j=0;j =9;j++){27 if(vis1[j]==vis2[j]&&vis2[j]){28 return 1;29 }30 }31 return 0;32 }33 int main()34 {35 int T,a,b,sum;36 scanf(“%d”,&T);37 sum=0;38 while(T–){39 scanf(“%d%d”,&a,&b);40 sum=1000;41 for(int i=1;i =1000;i++){42 //一个简洁的思路,一遍for循环:每次去除a和b的倍数,然后写一个函数判断是否含有a和b的本身数字43 if(i%a==0
fact(i,a,b)){44 sum–;45 }46 }47 printf(“%d\n”,sum);48 }49 50 return 0;51 }

View Code

比赛首页 H 方块与收纳盒 21030126

现在有一个大小n*1的收纳盒,我们手里有无数个大小为1*1和2*1的小方块,我们需要用这些方块填满收纳盒,请问我们有多少种不同的方法填满这个收纳盒。

题目分析:基础一维DP;假设长度为n的时候,状态转移方程式为dp[i]=dp[i-1]+dp[i-2]; 即n块长度是有n-1块再加一块拼起的或者n-2块加两块拼起的。或者自行打表分析,分别从1打到10就可以找出规律了。

#include cstdio #include iostream //#include cmath #include algorithm #include queue #include cstring //18:58using namespace std;#define ll long longint main(){ ll dp[100]; dp[0]=1;dp[1]=1; for(int i=2;i =80;i++){ dp[i]=dp[i-1]+dp[i-2]; } int T,d; scanf(“%d”,&T); while(T–){ scanf(“%d”,&d); printf(“%lld\n”,dp[d]); } return 0;}

View Code

牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解

标签:运行时间 can ear 类型 主动 log box 装配 lap

原文:https://www.cnblogs.com/zhazhaacmer/p/8325180.html

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注