2018年全国多校算法寒假训练营练习比赛(第一场)

时间:2023-01-26 00:19:30

首先申明一下(部分代码参考部分同学)其中有六字冲、N阶汉诺塔、恋与程序员都是看别人代码的,其实(恋与程序员我自己也是会做的)只是一是没想通。。。。希望给大家看看我的做法吧。

A大吉大利,今晚吃鸡——枪械篇

其实这题思想就是模拟,先把配置 k 中只要最大的。而对于每一把枪都需要它最好的 配件就是把它排一下序即可。

最后加上枪原本的p 就是公式  w=p*(1+b+b+…+bk)来设定这把枪的最高威力。最后不断更新威力值。找到最大的。

链接:https://www.nowcoder.com/acm/contest/67/A
来源:牛客网

题目描述

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

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

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



输入描述:

数据有多组,处理到文件结束。
第一行两个整数n和m,代表枪支数量和配件数量。
接下来n行,描述n把枪的属性:第一个整数为p,代表枪支的威力;第二个整数为k,代表该枪支可装备的配件数量;后面k个整数,代表可装备配件的种类。
接下来m行,描述m个配件的属性:第一个整数为q,代表配件的种类,第二个浮点数为b,代表配件可以为枪支提供的威力加成。

输出描述:

每组数据输出为一行,输出一个浮点数,代表合理装备配件后的枪支最大威力。精确到小数点后4位。
 
 
 
 
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
typedef struct point{
    int p,k,pj[1000];
}point;
int cmp(double a,double b)
{
    return a>b;
}
int main()
{
    int n,m;

    while(~scanf("%d%d",&n,&m))
    {
        point a[1000];
        double b[1000][100],y,ans=0.0;
        int vis[1000],cnt=0,x;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].p,&a[i].k);
            for(int j=0;j<a[i].k;j++)
            {
                scanf("%d",&a[i].pj[j]);
            }
        }
       /* for(int i=0;i<n;i++)
        {
            for(int j=0;j<a[i].k;j++)
            {
                printf("%d\n",a[i].pj[j]);
            }
        }*/
        for(int i=0;i<m;i++)
        {
            scanf("%d%lf",&x,&y);

            b[x][vis[x]]=y;
            vis[x]++;
        }

        for(int i=0;i<1000;i++)
        {
            if(vis[i]!=0)
            {
                sort(b[i],b[i]+vis[i],cmp);
            }
        }
       /* for(int i=0;i<100;i++)
        {
            if(vis[i]!=0)
            {
                printf("%.2lf****\n",b[i][0]);
            }
        }*/
        for(int i=0;i<n;i++)
        {
            double w=1;
            for(int j=0;j<a[i].k;j++)
            {
                w+=b[a[i].pj[j]][0];
            }
            w*=(a[i].p);
            //printf("%.2lf^^^^^\n",w);
            ans=max(ans,w);
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}
 B 
  最强的决斗者一切都是必然的! 
链接: https://www.nowcoder.com/acm/contest/67/B来源:牛客网

题目描述

    L一直喜欢玩游戏王这款声控印卡游戏,使用一套连锁式削血卡组便可战无不胜。每当陷入危机即将败北之际,L便会高呼“最强的决斗者一切都是必然的!”,然后发动闪光印卡技能,直接翻盘,伤害不多不少,正好足够击败对手。

    发动闪光印卡技能后,L抽取一张牌,然后微微一笑。接着L以一定顺序打出若干张牌,造成的伤害正好等于对方的生命值。每一张牌都有其发动速度以及效果。如果后发动的一张牌的发动速度不小于前一张牌,则后发动的那张牌会在前一张牌后进行连锁发动,这张牌的连锁数就是连锁发动的编号。不进行连锁发动的牌,连锁数为1。同一连锁中的牌,后发动的牌先生效。

    如下图,5张牌的速度分别为(1,2,2,2,3),因此它们进行连锁发动。连锁数分别为(1,2,3,4,5),因为连锁中的牌,后发动的先生效,所以,生效顺序为(5,4,3,2,1)。
2018年全国多校算法寒假训练营练习比赛(第一场)

    为简化问题,我们假设发动的牌的效果有如下几种:

    1. 对对方造成X点伤害

    2. 对对方造成这张牌的连锁数乘X点的伤害

    3. 同一连锁中的牌全部无效

    4. 连锁中的前一张牌无效

    现在你知道L发动牌的效果、速度和顺序,求L能对对方造成多少伤害。

输入描述:

数据有多组,处理到文件结束
第一行一个整数n,代表L发动了多少张牌。
接下来n行,前两个数是两个整数s和t,代表牌的发动速度和效果(数字对应上述4类效果)。如果是第1、2类效果,则紧接着一个整数x,代表效果中的X的数值。

输出描述:

每组数据输出一行,一个整数,代表L能对对方造成的伤害。
#include<stdio.h>
#include<algorithm>
#include<stack>
#include<string.h>
using namespace std;
typedef struct point {
    int s,t,x;
}point;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        point a[5010];
        int ans=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a[i].s,&a[i].t);
            if(a[i].t==1||a[i].t==2)
            {
                scanf("%d",&a[i].x);
            }
        }
        stack<point>st;
        st.push(a[0]);
        for(int i=1;i<n;i++)
        {
            if(st.empty()||a[i-1].s<=a[i].s)
            {
                st.push(a[i]);
            }
            else
            {
                i--;
                while(!st.empty())
                {
                    point cur=st.top();
                    st.pop();
                    if(cur.t==1)
                    {
                        ans+=cur.x;
                        continue;
                    }
                    else if(cur.t==2)
                    {
                        ans+=(cur.x*(st.size()+1));
                        continue;
                    }
                    else if(cur.t==3)
                    {
                        break;
                    }
                    else if(cur.t==4)
                    {
                        if(!st.empty())
                            st.pop();
                        else
                            break;
                    }
                }
                while(!st.empty())
                    st.pop();
            }
        }
        while(!st.empty())
        {
           // printf("*******\n");
            point cur=st.top();
            st.pop();
            if(cur.t==1)
            {
                ans+=cur.x;
            }
            else if(cur.t==2)
            {
                ans+=(cur.x*(st.size()+1));
            }
            else if(cur.t==3)
            {
                break;
            }
            else if(cur.t==4)
            {
                if(!st.empty())
                  st.pop();
                else
                    break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}



C 六子冲
链接: https://www.nowcoder.com/acm/contest/67/C
来源:牛客网

题目描述

    六子冲是流传于中国民间的一类棋类游戏。由于这个游戏对环境的要求不高,孩子们大都是在光滑的地面或石板上画上方格,以石子或木棍、草节等为棋子,并有简单的比赛,可以锻炼脑力。

    纵横各四条直线组成一个正方形棋盘,直线相交的地方为落子点。开局时放子处为上下左右边线上的落子点,且不同方的子不可交叉放置。如下图:
2018年全国多校算法寒假训练营练习比赛(第一场)

    棋子只能停留在棋盘上的落子点,棋子只能在线上移动,棋子只能移动一步(即相邻落子点),每回合只能移动1个棋子。消灭对方棋子的方法只有一条,也很简单。那就是:二子打一子。即在棋盘上攻击方的2个棋子(2子必须相连并主动移动其中的1个)与被攻方的1个棋子皆处在一条直线上并相邻时,被攻方的这个棋子就被消灭。双方轮流走子,保护自己的棋子并消灭所有对方的棋子,直到最后胜利。

    吃子例与错误吃子例如下图所示:
2018年全国多校算法寒假训练营练习比赛(第一场)2018年全国多校算法寒假训练营练习比赛(第一场)
2018年全国多校算法寒假训练营练习比赛(第一场)2018年全国多校算法寒假训练营练习比赛(第一场)

    现为双方棋子赋予编号1~12。1~6号为黑方棋子,7~12号为白方棋子。其初始位置如下:

2018年全国多校算法寒假训练营练习比赛(第一场)

    用两个整数,来代表走子方式。第一个数q代表棋子的编号,第二个数p,代表走子的方向。1<=q<=12,1<=p<=4,其中q的数字对应棋子的编号,p为1时向上走子,p为2时向下,3为向左,4为向右。给你n步走子方式,求最后棋盘的局面。



输入描述:

数据有多组,处理到文件结束。
第一行一个数n,代表走子步数。
接下来n行,每行两个整数,第一个数q代表棋子的编号,第二个数p,代表走子的方向。

输出描述:

每组数据第一行输出“#Case i:”并换行,其中i为测试用例编号,从1开始。
接着输出一个4*4的矩阵,代表棋盘局面的情况,4*4的矩阵代表棋盘上的4*4个棋位,矩阵的元素,即是棋盘上对应的棋子编号,没有棋子为0。输出的数字以3位的位宽输出。
示例1

输入

8
7 3
6 1
12 4
1 1
12 2
2 1
10 2
4 1

输出

#Case 1:
  0  0  9  8
  0 10  7  0
  2 12  4  0
  0  0  0  5

说明

注意,输出的每一个棋子编号,都应是位宽为3的。最后的输出效果,每个数字都右对齐。如果网页显示有误或者描述不够清晰,请看下面:
**0**0**9**8
**0*10**7**0
**2*12**4**0
**0**0**0**5
上面的‘*’对应输出样例中的空格。所有数据的结果,请按上面的格式输出。
在实际测试数据中,会存在让子的情况。即有可能出现一方玩家连续走子多次的情况。

备注:

对于100%的数据,
1 <= n <= 1000;
1 <= q <= 12;
1 <= p <= 4。
 
  
#include<bits/stdc++.h>
using namespace std;
int n,a[5][5],T;
int dir[4][2]={
    {-1,0},
    {1,0},
    {0,-1},
    {0,1}
};
int check(int x,int y,int z)
{
    if(!x||!y||!z)
        return 0;
    return (x-6.5)*(y-6.5)>0&&(x-6.5)*(z-6.5)<0;
}
void check(int x,int y)
{
    if(x>0&&a[0][y]==0){
        if(x!=3&&check(a[1][y],a[2][y],a[3][y]))a[3][y]=0;
        if(x!=1&&check(a[3][y],a[2][y],a[1][y]))a[1][y]=0;
    }
    if(x<3&&a[3][y]==0){
        if(x!=2&&check(a[0][y],a[1][y],a[2][y]))a[2][y]=0;
        if(x!=0&&check(a[1][y],a[2][y],a[0][y]))a[0][y]=0;
    }
    if(y>0&&a[x][0]==0)
    {
        if(y!=3&&check(a[x][1],a[x][2],a[x][3]))a[x][3]=0;
        if(y!=1&&check(a[x][3],a[x][2],a[x][1]))a[x][1]=0;
    }
    if(y<3&&a[x][3]==0)
    {
        if(y!=2&&check(a[x][0],a[x][1],a[x][2]))a[x][2]=0;
        if(y!=0&&check(a[x][1],a[x][2],a[x][0]))a[x][0]=0;
    }
}
int main()
{
        while(~scanf("%d",&n)){
            memset(a,0,sizeof(a));
            for(int i=0;i<4;i++)
                a[0][i]=11-i,a[3][i]=2+i;
            a[1][0]=12;
            a[1][3]=7;
            a[2][0]=1;
            a[2][3]=6;

            while(n--)
            {
                int q,d;
                scanf("%d%d",&q,&d);
                    d--;
                int x=-1,y;
                for(int i=0;i<4;i++){
                    for(int j=0;j<4;j++){
                        if(a[i][j]==q)
                            x=i,y=j;break;
                    }
                    if(x!=-1)
                    break;
                }
                a[x][y]=0;
                x+=dir[d][0];
                y+=dir[d][1];
                a[x][y]=q;
                check(x,y);
            }
            printf("#Case %d:\n",++T);
            for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                    printf("%3d",a[i][j]);
                }printf("\n");
            }
        }
        return 0;
}


D	N阶汉诺塔变形
链接:https://www.nowcoder.com/acm/contest/67/D
来源:牛客网

题目描述

    相信大家都知道汉诺塔问题。那么现在对汉诺塔问题做一些限制,成为一个新的玩法。

    在一个底座上,从左到右有三个分别命名为A、B和C的塔座,有n个大小不一的圆盘。这些圆盘一开始,从小到大按顺序叠加在塔座A上,形成一座上小下大的塔,塔座B和C为空。我们将n个圆盘,从小到大编号为1~n。现要求将塔座A上的n个圆盘移至塔座C上并仍按照同样的顺序叠排,圆盘移动时必须遵循以下规则:     (1)每次只能将一个圆盘从一个塔座移动到相邻的塔座上     (2)所有圆盘可以叠在A、B和C中的任一塔座上

    (3)任何时刻都不能将一个较大的圆盘压在较小的圆盘上面

    那么问题来了,对于一个n阶(阶数即是问题中圆盘的个数)的上述问题,用最少操作次数将圆盘塔从塔座A移动到塔座C的操作总是固定的。请问,n阶问题执行k步操作后,塔座A、B和C上圆盘的情况是怎样的?从大到小输出三个塔座上的圆盘的编号(如果该塔座上没有圆盘,请输出0)。

比如,塔座A上有圆盘1,3;塔座B上有圆盘2;塔座C上有圆盘4。我们将输出:

3 1

2

4

输入描述:

数据有多组,处理到文件结束。
每组数据一行输入,有两个整数n和k,n代表问题的阶数,k代表执行的步数。

输出描述:

每组数据输出占三行。
第一行描述塔座A的情况。
第二行描述塔座B的情况。
第三行描述塔座C的情况。
示例1

输入

3 5
4 10

输出

3 1
2
0
4
3 1
2

备注:

10000组数据。
对于100%的数据,
1 <= n < 40;
1 <= k < (3^n)。
 
   
#include<stdio.h>
int main()
{
    int n,ans[40];
    int p[]={0,1,2,1};
    long long k;
    while(~scanf("%d%lld",&n,&k))
    {
        for(int i=1;i<=n;i++)
        {
            ans[i]=0;
        }
        for(int i=1;i<=n&&k;i++)
        {
            long long temp=k/3;
            ans[i]=p[(k-temp)&3];
            k=temp;
        }
        for(int i=0;i<3;i++)
        {
            int cnt=0;
            for(int j=n;j>=1;j--)
            {
                    if(ans[j]==i)
                    {
                        if(++cnt>1)
                            printf(" ");
                        printf("%d",j);
                    }
            }
            if(cnt==0)
                printf("0");
            printf("\n");
        }
    }
    return 0;
}


E	恋与程序员
 
   
链接:https://www.nowcoder.com/acm/contest/67/E
来源:牛客网

题目描述

    马云:“哈哈,女生的钱最好赚了!”

    叠纸:“马云说得对!”

    腾讯:“哇!真的耶!求代理!”

    小P眼一眯,嘴角一挑,似乎发现了商机。不就是抽卡过关看CG么,我也能做啊!于是乎,一个月后,一款《恋与程序员》诞生了。

    游戏里设置了n个事件,m个关卡,k张卡片。每一个事件都有一张独一无二的CG,但是每个关卡,都需要拥有特定的卡片才能通关。从一个事件,触发另一个事件,需要通过一个特定的关卡。我们给事件编号为1~n,对应的CG编号与事件的编号一致。卡片编号为1~k。一开始,玩家会触发事件1,并拿到1号CG,但是从此之后,玩家如果想触发别的事件,便要通过闯关来达到。

    现在,小Q想要c号CG(触发c号事件获得),但是小Q却又不想花太多的钱。于是小Q查了攻略,以事件为点,关卡为边,作了一张图,并且小Q知道每个关卡都需要什么卡片以及卡片的售价。请你计算一下,小Q拿到c号CG,至少要花多少钱。

    注意,过关并不需要消耗卡片,同一张卡片可以通关多次。

输入描述:

数据有多组,处理到文件结束。
每组数据第一行有四个整数n,m,k,c,代表事件数量、关卡数量、卡片数量以及小Q想要的CG的编号。
接下来m行,每行三个整数u,v,e,代表从u号事件可以通过闯关触发v号事件,并且需要e号卡片。
接下来k行,每行两个整数a,b,代表a号卡片的售价是b。

输出描述:

每组数据输出一行,一个整数,代表小Q拿到c号CG的最小花费。
示例1

输入

6 7 5 6
2 3 2
4 3 3
1 2 1
1 5 4
4 6 5
1 4 2
5 6 3
1 100
3 422
2 210
5 107
4 38

输出

317

备注:

对于100%的数据,
1 <= n,m,k <= 100;
1 <= u,v <= n;
1 <= a,c,e <= k;
1 <= b <= 1000。
 
    
 
    
#include<stdio.h>
#include<string.h>
int G[101][101],vis[101],card[101];
int n,m,k,c,sum;
void dfs(int cg,int add)
{
    if(cg==c)
    {
        if(add<sum)
            sum=add;
        return ;
    }
    for(int i=0;i<101;i++)
    {
        if(G[cg][i]!=0)
        {
            if(vis[G[cg][i]]==0)
            {
                vis[G[cg][i]]=1;
                dfs(i,add+card[G[cg][i]]);
                vis[G[cg][i]]=0;
            }
            else
            {
                dfs(i,add);
            }
        }
    }
}
int main()
{
        while(~scanf("%d%d%d%d",&n,&m,&k,&c))
        {
                memset(G,0,sizeof(G));
                memset(vis,0,sizeof(vis));
                memset(card,0,sizeof(card));
                for(int i=0;i<m;i++)
                {
                    int u,v,cd;
                    scanf("%d%d%d",&u,&v,&cd);
                    G[u][v]=cd;
                }
                for(int i=0;i<k;i++)
                {
                    int x,y;
                    scanf("%d%d",&x,&y);
                    card[x]=y;
                }
                sum=0x3f3f3f3f;
                dfs(1,0);
                printf("%d\n",sum);
        }
}


 
    
F	大吉大利,今晚吃鸡——跑毒篇
链接:https://www.nowcoder.com/acm/contest/67/F
来源:牛客网

题目描述

    现在有一款很火的游戏playerunknown's battlegrounds,人称“吃鸡”,在里面经常面临跑毒(从安全区外跑进安全区内)的问题,在安全区外,人们会处于中毒状态,每秒会掉a%血,人们可以通过使用道具急救包把血量升回到80%,使用急救包需要原地站着6秒。现在知道在安全区外扣血速度为a%/s,角色和安全区的距离为b米,角色跑步速度为1m/s,角色有c个急救包,请问角色是否能安全跑进安全区内。(PS:角色开始的血量为100%。如果血量降到0%,立刻判定为死亡。使用急救包时,如果刚使用完毕瞬间或者正在使用急救包的时候,血量降到0%,角色立即判定为死亡。顺带一提,这里判断时间不存在0.xxxx秒,最小时间单位为1s)

输入描述:

第一行是样例数T(T<9)
第2到2+T-1行每行有三个整数a b c,其中a为安全区外的扣血速度a%/s,b为角色和安全区的距离,c为急救包的数量。

输出描述:

如果角色能进入安全区输出“YES”。
若角色在安全区外死亡输出“NO”。
示例1

输入

3
1 100 2
6 31 2
7 31 2

输出

YES
YES
NO

说明

当a=6,b=31,c=2时,
0s起跑,10s的时候角色跑了10M,血量剩下40%,开始使用急救包,16s的时候,角色血量先降到4%再恢复到80%,然后角色继续跑步。23s的时候,角色跑了17M,剩余血量为38%,开始使用急救包,29s的时候,角色血量先降到2%再恢复到80%,然后角色继续跑步。42s的时候,角色跑了30m,血量剩余2%。当43s的时候,角色跑了31m进入了安全区内,不再扣血。

备注:

对于100%的数据,
1 <= T < 9;
0 < a <= 20;
0 < b <= 120;
0 <= c <= 8。
 
     
 
     
#include<stdio.h>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c,blood=100;
        scanf("%d%d%d",&a,&b,&c);
        while(1)
        {
            if(blood-a<=0&&b==1)
            {
                b--;
                break;
            }
            else if(blood-a>0)
            {
                blood-=a;
                b--;
                if(b<=0)
                    break;
            }
            else
            {
              //  printf("%d\n",blood);
                c--;
                if(c==-1)
                   break;
                blood=80;
                b+=6;
            }
        }
        if(c!=-1&&b<=0)
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
}

G 圆圈
 
    
链接:https://www.nowcoder.com/acm/contest/67/G
来源:牛客网

题目描述

    圈圈圆圆圈圈,lulu小朋友最近看喜羊羊看多了,老是受刺激就画圆圈,听到小于8的数字时,还会画出十分有规律的圆圈,现在你需要根据样例观察出规律,编写程序,根据输入的数字n(n<8),输出对应的圆圈。

输入描述:

第一行是样例数T(T<9)
第2到2+T-1行每行有一个整数n(n<8),代表lulu听到的数字

输出描述:

听到对应数字时,输出对应样子的圆圈。
示例1

输入

4
0
1
2
3

输出

O
 O
O O
 O
    O
   O O
    O
 O     O
O O   O O
 O     O
    O
   O O
    O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O
    O                 O
   O O               O O
    O                 O
 O     O           O     O
O O   O O         O O   O O
 O     O           O     O
    O                 O
   O O               O O
    O                 O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O

说明

当n=0时输出
O
当n=1时输出
*O
O*O
*O
当n=2时输出
****O
***O*O
****O
*O*****O
O*O***O*O
*O*****O
****O
***O*O
****O
上面的'O'是大写英文字母O,'*'代表空格,每一行最后一个O后面不带空格。

备注:

对于100%的数据,
0<T<9;
0<=n<8;
 
     
 
     
#include<iostream>
#include<cstring>
#include<cmath>
#define maxn 2500
using namespace std;
int p[maxn][maxn],ed[maxn];
void dfs(int n,int sx,int sy)
{
       if(n==0)
       {
            p[sx][sy]=1;
            return ;
       }
       int part=(int)pow(3,n-1);
       dfs(n-1,sx+part,sy);
       dfs(n-1,sx,sy+part);
       dfs(n-1,sx+part,sy+part*2);
       dfs(n-1,sx+2*part,sy+part);
}
int main()
{
    int n,t,alls;
        cin>>t;
    while(t--)
    {
        cin>>n;
        memset(p,0,sizeof(p));
        memset(ed,0,sizeof(ed));
        alls=pow(3,n);
        dfs(n,0,0);
        for(int i=0;i<alls;i++)
        {
            for(int j=0;j<alls;j++)
            {
                if(p[i][j])ed[i]=j;
            }
        }
        for(int i=0;i<alls;i++)
        {
            for(int j=0;j<=ed[i];j++)
            {
                if(p[i][j])
                    cout<<"O";
                else
                    cout<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}


H	方块与收纳盒
 
     
链接:https://www.nowcoder.com/acm/contest/67/H
来源:牛客网

题目描述

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

输入描述:

第一行是样例数T
第2到2+T-1行每行有一个整数n(n<=80),描述每个样例中的n。

输出描述:

对于每个样例输出对应的方法数
示例1

输入

3
1
2
4

输出

1
2
5

说明

n=4,有五种方法
1:1 1 1 1
2:2 1 1
3:1 2 1
4:1 1 2
5:2 2

备注:

对于100%的数据,
0 < T < 80;
0 < n <= 80。
 
      
 
      
#include<stdio.h>
typedef long long ll;
ll dp[90]={1,1,2};
void solve()
{
    for(int i=3;i<90;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
}
int main()
{
    int T;
    solve();
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("%lld\n",dp[n]);
    }
    return 0;
}


I	找数字个数
链接:https://www.nowcoder.com/acm/contest/67/I
来源:牛客网

题目描述

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

输入描述:

第一行是样例数T
第2到2+T-1行每行有2个整数a b。

输出描述:

输出lulu喜欢的数的个数
示例1

输入

3
2 3
14 23
1234 5678

输出

171
190
7

说明

a=1234 b=5678的时候,只考虑含有数字9,0的数,只有7个,分别是9,99,999,90,990,909,900

备注:

对于100%的数据,
0 < T <= 20;
0 <= a <= 99999;
0 <= b <= 99999。
 
       
 
       
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int cal(int a)
{
    return 1000/a*a;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a,b,ans=1000;
        scanf("%d%d",&a,&b);
        int n1=a,n2=b,num[10]={0};
        if(a==1||b==1)
        {
            printf("1\n");
            continue;
        }
        while(n1!=0)
        {
            num[n1%10]=1;
            n1/=10;

        }
        while(n2!=0)
        {
            num[n2%10]=1;
            n2/=10;
        }
        for(int i=1;i<=1000;i++)
        {
            int temp=i,flag=0;
            if(i%a==0||i%b==0)
            {
                ans--;
                continue;
            }
            while(temp)
            {
                if(num[temp%10]==0)
                {
                    temp/=10;
                }
                else
                {
                    flag=1;
                    break;
                }
            }
            if(flag==1)
            {
                ans--;
                continue;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


J	闯关的lulu
 
       
链接:https://www.nowcoder.com/acm/contest/67/J
来源:牛客网

题目描述

    勇者lulu某天进入了一个高度10,000,000层的闯关塔,在塔里每到一层楼,他都会获得对应数量的0 1(看情况获得),然后塔里有一个法则,当你身上某个数字达到一个特定的数量时,它们会合成为下一个数字,现在问题来了,当lulu从1层到达第n层的时候,他身上的数字是多少。

第1层 0

第2层 11

第3层 110

第4层 21

第5层 210

第6层 22

第7层 220

第8层 2211

第9层 22110

第10层 2221

第11层 22210

第12层 3

输入描述:

第一行是样例数T(T<100)
第2到2+T-1行每行有一个整数n(0<n<=10^7)。

输出描述:

从大到小输出lulu到达第n层时身上的数字
示例1

输入

4
1
2
3
20

输出

0
11
110
32211

备注:

对于100%的数据,
0 < T <= 100
0 < n <= 10^7
 
        
 
        
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int  a[10]={0};
        for(int i=1;i<=n;i++)
        {
            if(i&1)
            {
                a[0]++;
            }
            else
            {
                a[0]+=3;
            }
        }
        for(int i=0;i<=9;i++)
        {
            if(a[i]>=i+2)
            {
                a[i+1]=a[i]/(i+2);
                a[i]=a[i]%(i+2);
            }
        }
        for(int i=9;i>=0;i--)
        {
            if(a[i]!=0)
            {
                for(int j=0;j<a[i];j++)
                {
                    cout<<i;
                }
            }
        }
        cout<<endl;
    }
    return 0;
}