17广工校赛

最新推荐文章于 2020-03-29 15:59:11 发布

keepcoral

最新推荐文章于 2020-03-29 15:59:11 发布

阅读量259

点赞数

分类专栏：算法文章标签：基础

本文链接：https://blog.csdn.net/keepcoral/article/details/79687058

版权

算法专栏收录该内容

4 篇文章

订阅专栏

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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

小明在坐景驰科技研发的无人车到达了目的地。

景驰科技（JingChi.ai）是一家由人工智能技术驱动、以无人驾驶技术为核心的智能出行公司。它将打造面向中国市场的全无人驾驶。

从无人车下来以后，小明看到了一个长长的楼梯。

有一个n级台阶的楼梯，小明一次可以向上跳1步，两步，甚至是n步，请问小明跳到n级台阶有多少种跳法？

输入描述:

第一行输入一个整数t，代表有t组样例:（ T<=30）
接下来的t行，都用一个整数n，表示楼梯有n级台阶（ 1<=n<=30）

输出描述:

输出跳到第n级台阶有多少种跳法

示例1

输入

1
1

输出

规律题，一开始我以为是用dp来就组合数，但发现不是的，这这是排列组合问题，一个个模拟之后就变成了一个规律题，题目说的也不是很清晰，甚至n步（其实是1-n步都是可以的）

规律：

n=1 :

1=1

1种

n=2 :

1+1=2

2=2

2种

n=3 :

1+1+1=3

1+2=3(排序1，2或者2 ，1)

3=3;

4种

n=4 :

1+1+1+1=4

1+1+2=4（3种）

2+2=4

1+3=4（2种）

4=4

总共8种

因此跳法=2^(n-1)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <cmath>
#define L o*2
#define R o*2+1
using namespace std;
int dp[1000009];
int a[100];
int p(int n)
{
    if(n<1) return 0;
    if(n==1) return 1;
    else if(n==2) return 2;
    else
    {
        return p(n-1)+p(n-2);
    }
}
int main()
{
    int n,i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%.0lf\n",pow(2.0,n-1));
    }
}

牛客网是是一个专注于程序员的学习和成长的专业平台，集笔面试系统、课程教育、社群交流、招聘内推于一体，同时它也是全国最大的IT题库，刷真题，练算法，看面经，得内推，全面提升你的技术水平、推荐最好的工作给你。Tmk很喜欢在牛客网上刷题。

回想起Tmk第一次看到牛客网的时候觉得很棒，就想赶紧做一道题。

于是他打开了a+b problem，题目是这样的，输入a和b，输出a+b=？

例如输入3和4，输出3+4=7.

Tmk觉得好难，通过了与小伙伴们激烈的讨论，然后打下了下面的代码：

#include <cstdio>

using namespace std;

Int main()

{

Int a,b,c;

scanf(“%d %d”,&a,&b);

c=a+b;

printf(“%d+%d=%d”,?,b,?);

return 0;

}

Tmk懵逼了，他不知道?那里应该是填什么字母，现在他好想去ac这道题，请问这两个问号的位置应该用什么代替呢？（一个?的位置应该填一个字母）

printf（"ac"）;

链接：https://www.nowcoder.com/acm/contest/90/J
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

牛客网是IT求职神器,提供海量C++、JAVA、前端等职业笔试题库,在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的编程。作为acmer的小A，牛客网是他首选的题库。

小A是一个中度强迫症患者,每次做数组有关的题目都异常难受,他十分希望数组的每一个元素都一样大,这样子看起来才是最棒的,所以他决定通过一些操作把这个变成一个看起来不难受的数组,但他又想不要和之前的那个数组偏差那么大,所以他每次操作只给这个数组的其中n-1个元素加1,但是小A并不能很好的算出最优的解决方案,如果你能帮他解决这个问题,小A就能送你一个气球

输入描述:

第一行一个整数T(T<=100),表示组数

对于每组数据有一个n,表示序列的长度(0< n <100000)

下面一行有n个数,表示每个序列的值(0<a_i<1000)

输出描述:

输出两个数
第一个数表示最小的操作步数
第二个数经过若干步以后的数组元素是什么

示例1

输入

1
3
1 2 3

输出

3 4

这是一道经典的面试题，一开始找不到头绪，上网去找，学会了思路。

首先给n-1个元素+1，那么就等价于，给n个元素+1，再找其中一个元素-1。有了这个结论以后，题目就好做了

因为要找所有元素相等，那么就是要把所有元素的差值变为零，那么给所有元素+1，对于它们的差值是不会影响的，例如（1,2,3）全部+1 （2，3，4）差值它们之间各元素的差值是不会变化的，那么只有给一个元素减1之后，它们的差值才会发生编变化，那么现在题目变成了，一个数组只能给其中一个元素-1，那么使全部元素变为相等的操作次数最少为多少。

因为只能被减，我们只需要找最小值为参照就可以了，例如（1，2，3）我们只需要给元素（3）进行两次-1，元素（2）进行一次-1，那么数组就变成了（1，1，1）了，题目还要求最终值为多少，那么我们只需要给最小值加上它的操作次数（也就是加上操作次数个1）就是最终值了，也是说元素（1）+3次操作，就是得到最后值为4

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <cmath>
#define L o*2
#define R o*2+1
 
using namespace std;
int a[1005000];
int main()
{
    int m=100001;
    int sum=0,t,i,n;
    scanf("%d",&t);
    while(t--)
    {
        sum=0;
        m=100001;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            m=min(m,a[i]);
        }
        int d=sum-m*n;
        printf("%d %d\n",d,m+d);
    }
}

链接：https://www.nowcoder.com/acm/contest/90/G
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

景驰公司自成立伊始，公司便将“推动智能交通的发展，让人类的出行更安全，更高效，更经济，更舒适”作为公司使命，通过产业融合、建设智能汽车出行行业的方式，打造“利国、利民、利公司、利个人”的无人驾驶出行系统。公司的愿景是成为中国第一、世界一流的智能出行公司。

有一天，景驰公司的工程师在真车上做测试。

景驰公司的试验车上面有一个奇怪的图案，这是一个n*m的矩阵，这辆车可以到处开，每次可以左旋右旋，小明想知道转完之后的图案是怎么样的

具体来说：有一个n*m的字符矩阵，只包含3种字符（‘+’‘-’，‘|’）,通过一通乱旋之后变成什么样子？

输入描述:

第一行测试样例数T（0<T<=100）
每个测试样例第一行两个正整数n,m(0<n,m<=30)
接下来的n行是一个n*m的字符矩阵
字符矩阵之后是一串只包含‘L’(左旋)和‘R’（右旋）的字符串，长度不超过1000
每个样例间输出一个空行

输出描述:

第一行两个正整数n,m
接下来的n行是一个n*m的字符矩阵
每个样例后面输出一个空行

示例1

输入

2
2 3
+-+
|+|
LLRRR

3 2
-+
+|
-+
LLL

输出

3 2
-+
+|
-+

2 3
|+|
+-+

备注:

左旋即逆时针旋转，右旋即顺时针旋转
-通过一次左旋或右旋会变成|
|通过一次左旋或右旋会变成-

细节题，我们规定左旋-1，右旋+1，初始化为0，操作之后那么我们可以最终得到一个数字，如果为负那么相当于它向左旋了多少次，如果为正那么相当于它向右旋了多少次，如-3，左旋了3次，再如4，右旋了四次。而且我们也很容易可以想到一个矩形旋转4次即恢复原状，那么4就是它的周期，直接将这个值%4就是它的图案了，思路就是这样。

具体操作，先将右旋的4副图打出来（它的操作数分别是0，1，2，3，这里0代表着没有进行操作，3代表了进行了3次右旋，第四次与操作数为0相同），分别用a,b,c,d四个数组装着。那么我们可以观察左旋0，2图与右旋是相同的，左旋1，3图分别对应着右旋的3，1图，那么处理好细节如 - 变 | 就可以了

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <cmath>
#define L o*2
#define R o*2+1
 
using namespace std;
char s[50][50];
char a[50][50];
char b[50][50];
char c[50][50];
char d[50][50];
char g[2000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
    int n,i,m,j,k;
    scanf("%d%d",&n,&m);
    for(i=0; i<=n-1; i++)
    {
        scanf("%s",s[i]);
    }
    for(k=0; k<=3; k++)
    {
        if(k==0)
        {
            for(i=0; i<=n-1; i++)
            {
                for(j=0; j<=m-1; j++)
                {
                    a[i][j]=s[i][j];
                }
                a[i][j]='\0';
            }
        }
        else if(k==1)
        {
            for(i=0; i<=m-1; i++)
            {
                for(j=0; j<=n-1; j++)
                {
 
                    if(s[n-1-j][i]=='-')
                    {
                        b[i][j]='|';//s[n-1-j][i];
                    }
                    else if(s[n-1-j][i]=='|')
                    {
                        b[i][j]='-';
                    }
                    else  b[i][j]=s[n-1-j][i];
                }
                b[i][j]='\0';
            }
        }
        else if(k==2)
        {
            for(i=0; i<=n-1; i++)
            {
                for(j=0; j<=m-1; j++)
                {
                    c[i][j]=s[n-1-i][m-1-j];
                }
                c[i][j]='\0';
            }
        }
        else if(k==3)
        {
            for(i=0; i<=m-1; i++)
            {
                for(j=0; j<=n-1; j++)
                {
                    d[i][j]=b[m-1-i][n-1-j];
                }
                d[i][j]='\0';
            }
        }
    }
    int sum=0;
    scanf("%s",g);
    for(i=0; g[i]!='\0'; i++)
    {
        if(g[i]=='L') sum--;
        else sum++;
    }
    if(sum>=0)
    {
        sum=sum%4;
        if(sum==0)
        {
            printf("%d %d\n",n,m);
            for(i=0; i<=n-1; i++)
            {
                printf("%s",a[i]);
                printf("\n");
            }
        }
        else if(sum==1)
        {
            printf("%d %d\n",m,n);
            for(i=0; i<=m-1; i++)
            {
                printf("%s",b[i]);
                printf("\n");
            }
        }
        else if(sum==2)
        {
            printf("%d %d\n",n,m);
            for(i=0; i<=n-1; i++)
            {
                printf("%s",c[i]);
                printf("\n");
            }
        }
        else
        {
            printf("%d %d\n",m,n);
            for(i=0; i<=m-1; i++)
            {
                printf("%s",d[i]);
                printf("\n");
            }
        }
        printf("\n");
    }
    else
    {
        sum=-sum;
        sum=sum%4;
        if(sum==0)
        {
            printf("%d %d\n",n,m);
            for(i=0; i<=n-1; i++)
            {
                printf("%s",a[i]);
                printf("\n");
            }
        }
        else if(sum==1)
        {
            printf("%d %d\n",m,n);
            for(i=0; i<=m-1; i++)
            {
                printf("%s",d[i]);
                printf("\n");
            }
        }
        else if(sum==2)
        {
            printf("%d %d\n",n,m);
            for(i=0; i<=n-1; i++)
            {
                printf("%s",c[i]);
                printf("\n");
            }
        }
        else
        {
            printf("%d %d\n",m,n);
            for(i=0; i<=m-1; i++)
            {
                printf("%s",b[i]);
                printf("\n");
            }
        }
        printf("\n");
    }
}
}

我写的看起来有点复杂，但其实后面的都是打印，处理好n行还是m行，前面的把4副图案打印出来就基本可以了

链接：https://www.nowcoder.com/acm/contest/90/K
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

ZiZi登录各种账号的时候，总是会忘记密码，所以他把密码都记录在一个记事本上。其中第一个密码就是牛客网的密码。

牛客网专注于程序员的学习、成长及职位发展，连接C端程序员及B端招聘方，通过IT笔试面试题库、在线社区、在线课程等提高候选人的求职效率，通过在线笔试、面试及其他工具提升企业的招聘效率。

团队由来自Google、百度、阿里、网易等知名互联网巨头的热血技术青年组成，用户覆盖全国2000多所高校的100W求职程序员及全部一线互联网企业，并仍在高速增长中。

谨慎的 ZiZi当然不会直接把密码记录在上面，而是把上面的字符串经过转化后才是真正的密码。转化的规则是把字符串以n行锯齿形写出来，然后再按从左到右，从上到下读取，

即为真正的密码。如ABABCADCE以3行写出：

所以真正的密码是ACEBBACAD。但是每一次都要写出来就太麻烦了，您如果能帮他写出一个转换程序，他就送你一个气球。

输入描述:

第一行一个整数T，表示数据组数
对于每组数据，首先一个正整数n（n<=100,000),然后下一行为一个字符串，字符串长度len<=100,000。

输出描述:

对于每组数据，输出一个字符串，代表真正的密码。

示例1

输入

1
3
ABABCADCE

输出

ACEBBACAD

第一眼看上去是模拟题，但当你看到可能会有10w行的时候你一定不会这么想了

规律题，多模拟才能出规律，自己拿123456789来代替ABCDEFGHI更容易看出规律来。

第1行k=2*(n-1)，m=0 读的字符下标是 1 1+k 1+2k...

第2行k=2*n-2-2, m=2 读的字符下标是 2 2+k 2+k+m 2+k+m+k 2+k+m+k+m....

第n行k=0，m=2*(n-1) 读的数字下标是 n n+m n+2m...

那么我们可以看出规律1或者n行间隔都是2*(n-1)，其余的都是k，m交替相加

还有一个特殊的样例，当n=1是，直接输出，我本来一开始已经想到这个特殊样例了，但码着码着就忘记了，于是又wa了。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string.h>
#define L o*2
#define R o*2+1
using namespace std;
char s[100009];
int main()
{
    int n,b,i,k,m,j,t;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%s",s+1);
        b=strlen(s+1);
        if(n==1) printf("%s",s+1);
       else
        for(i=1; i<=n; i++)
        {
            if(i==1)
            {
                k=2*(n-1);
                m=0;
                for(j=i; j<=b; j+=k)
                {
                    printf("%c",s[j]);
                }
            }
            else if(i==n)
            {
                k=0;
                m=2*(n-1);
                for(j=i; j<=b; j+=m)
                {
                    printf("%c",s[j]);
                }
            }
            else
            {
                k-=2;
                m+=2;
                t=0;
                for(j=i; j<=b;)
                {
                    printf("%c",s[j]);
                    if(t%2==0) j+=k;
                    else j+=m;
                    t++;
                }
            }
        }
        printf("\n");
    }
 
}