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

时间:2021-07-09 00:19:06

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

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

在绝地求生(吃鸡)游戏里,不同的枪支有不同的威力,更是可以搭配不同的配件,以提升枪支的性能。
牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解

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

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

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

牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解
 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:58
11 using namespace std;
12 #define ll long long
13 struct gun
14 {
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的数字的数,然后输出剩余总数——这样时间复杂度一般比我的思路要低(极端情况下一样)。自行尝试。

牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解
 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:58
11 using namespace std;
12 #define ll long long
13 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||i%b==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(n>=2)的时候,状态转移方程式为dp[n]=dp[n-1]+dp[n-2];  即n块长度是有n-1块再加一块拼起的或者n-2块加两块拼起的。或者自行打表分析,分别从1打到10就可以找出规律了。

  

牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解牛客网_2018年全国多校算法寒假训练营练习比赛(第一场)_部分题解
#include<cstdio>
#include<iostream>    //
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>    //18:58
using namespace std;
#define ll long long
int 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