网易2017内推笔试编程题合集（一）

1、[编程题]合唱团

有 n个学生站成一排，每个学生有一个能力值，牛牛想从这 n个学生中按照顺序选取 k名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k个学生的能力值的乘积最大，你能返回最大的乘积吗？ 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：注意有负数的情况，因此当前最小值和最大值都应该存下来。

 

c++代码：

#include<iostream>
#include<cmath>
#include<limits.h>
using namespace std;
 
long long a[51];
long long maxval[11][51];
long long minval[11][51];
 
int main(){
   int n;  //n个学生
   while(cin>>n){
       int i,j,m;
       for(i=0;i<n;i++){
           cin>>a[i];
       }//输入n个学生的能力值
 
       int k,d;
       cin>>k>>d;
 
       for(i=0;i<=k;i++){
           for(j=0;j<=n;j++){
                maxval[i][j] = minval[i][j] =0;  //全部初始化为0
           }
       }
       long long res=LONG_LONG_MIN;
 
       //max[k][i]：表示选中k个学生，以第i个学生结尾，产生的最大乘积
       for(i=1;i<=n;i++){   //依次以这n个学生作为结尾
           maxval[1][i] = minval[1][i] = a[i-1];
           for(m=2;m<=k;m++){
                for(j=i-1;j>0 &&(i-j)<=d;j--){
                    maxval[m][i] =max(maxval[m][i], max(maxval[m-1][j] * a[i-1], minval[m-1][j] * a[i-1]));
                    minval[m][i] =min(minval[m][i], min(maxval[m-1][j] * a[i-1], minval[m-1][j] * a[i-1]));
                }
           }
           res = max(res, maxval[k][i]);
       }
       cout<<res<<endl;
 
 
   }//while
   return 0;
}

2、[编程题]地牢逃脱

给定一个 n行 m列的地牢，其中 '.'表示可以通行的位置，'X'表示不可通行的障碍，牛牛从 (x₀ , y₀ )位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：做这道题，理解题意很重要。我又没看懂题目，郁闷。在把别人的代码看懂了之后我还是觉得题目起的很烂。

这里解释一下难理解的部分：

（1）合法步数是指你可以选择这些步数里面的任意一个组合，所以才会有遍历所有步数的那段代码（这里我理解了很久）。采用广度优先遍历算法通过队列queue来实现。

（2）要求的问题是我们知道牛牛自己的起点，在终点（出口）是所有可通行格子中的一个的情况下，设哪一个格子为终点，会导致牛牛要走出去的最小步数最大？

（3）可瞬间移动，即不管中间是否有障碍物，只要目标位置不是障碍物，就可以移动到该位置。

 

c++代码：

#include<iostream>
#include<queue>
#include<limits.h>
#include<algorithm>
using namespace std;
 
char ground[55][55];   //表示n行m列地牢的结构
int n,m; //表示地牢的长和宽，n行m列
int k;  //表示合法的步长数
int direction[55][2];  //表示第i次时可选择移动的行和列步长
int dis[55][55];  //dis[i][j]表示从起点到（i,j）点的最小步数
 
struct Point{
    int x,y; //表示该点的x和y
   Point(){};
   Point(int a, int b):x(a),y(b){};  //构造函数
   Point go(int i){
       //在走第i次时
       return Point(x+direction[i][0], y+direction[i][1]);
    }
   bool isOk(){
       //表示当前节点的位置是否在地牢内
       return x>=0&&y>=0&&x<n&&y<m&&ground[x][y]=='.';
    }
 
};
 
int main(){
   while(cin>>n>>m){
       int i,j;
       for(i=0;i<n;i++){
           cin>>ground[i];
       }//for  输入地牢结构
 
       //输入起点
       Point start;  //起点
       cin>>start.x;
       cin>>start.y;
 
       //输入合法步长
       cin>>k;
 
       //输入每次可选择移动的行和步长
       for(i=0;i<k;i++){
           cin>>direction[i][0]>>direction[i][1];
       }
 
       //初始化到所有点的距离为无穷大
       fill(dis[0], dis[54]+55, INT_MAX);
       dis[start.x][start.y] = 0;  //起点到起点的距离为0
 
       queue<Point> q;   //用广度遍历策略
       q.push(start);  //将起点加入队列
       while(!q.empty()){
           //当队列非空时
           Point x = q.front();  //取出队列中第一个点
           q.pop();
 
           for(i=0;i<k;i++){
                //遍历所有合法的步数
                Point y = x.go(i);   //假设x在走第i步后得到的节点
                if(y.isOk()){
                    //当该节点在地牢内时
                   if(dis[y.x][y.y]>dis[x.x][x.y]+1){
                        dis[y.x][y.y] =dis[x.x][x.y]+1;
                        q.push(y);
                    }
                }
           }
       }//while
 
       int res=0;  //表示最后的结果
       for(i=0;i<n;i++){
           for(j=0;j<m;j++){
                if(ground[i][j] =='.'){
                    res = max(res, dis[i][j]);
                }
           }
       }
 
       if(res == INT_MAX){
           cout<<-1<<endl;
       }else{
           cout<<res<<endl;
       }
 
   }//while
   return 0;
}

3、[编程题]下厨房

牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：这道题不难，用set和map都容易写出来代码，但是一直在纠结怎么判断输入结束然后输出结果呢。后来发现测试的时候本来就是没办法输出。但是提交到牛客网显示AC。（摊手…）

 

c++代码（使用map）：

#include<iostream>
#include<map>
using namespace std;
int main(){
   map<string,int> a;
   string tmp;
   int count=0;
   while(cin>>tmp){
       if(a[tmp] == 0){
           a[tmp] = 1;
           count++;
       }else{
           a[tmp]++;
       }
   }//while
   cout<<count<<endl;
   return 0;
 
}
 
使用set：
#include<iostream>
#include<set>
using namespace std;
int main()
{
   string str;
   set<string> mat;
   int res=0;
   while(cin>>str)
    {
       if(mat.find(str)==mat.end())
       {
           res++;
           mat.insert(str);
       }
           
       else
           continue;
    }
   cout<<res<<endl;
   return 0;
   
}

4、[编程题]分田地

牛牛和 15个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16 份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地，作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？ 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：“最小值最大问题”，先二分试试。 
枚举横向的三刀，纵向上在二分答案后贪心地靠左切，使得每个区域刚好全部大于等于答案，根据能否切满三刀来确定答案区间。这个时间复杂度算一下是O(n3mlogx)的，其中x是最大可能答案。
对于枚举横向的三刀，现在问题是如何确定这三刀，使得16个区域最小值最大。不妨先切中间那刀，那么问题变为如何切左边那刀和右边那刀，很显然这两个问题相互独立。用f[i]表示前i列的最优切法所得到的值，g[i]表示i~m列的最优切法得到的值，那么答案=max(min(f[i],g[i+1])),1<=i<m。容易证明f[i]和g[i]的最优决策都是单调的，于是它们都可以在O(m)的时间内算出来，因此最后复杂度变为O(n3m)。

此题较难理解，请多写几遍代码，死记硬背也要记下来。o(￣ヘ￣o#)

 

c++代码：

#include<iostream>
#include<cstring>
using namespace std;
int a[76][76];  //存储每块田地的价值
int n,m; //表示田地的大小
int sum[76][76]; //sum[i][j]表示从(0,0)到(i, j)的田地总价值
 
int getArea(int x1, int y1, int x2, inty2){
   return sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1];
 
}
 
bool judge(int mid){
   //先枚举列切三刀的情况，然后横扫一遍
   int i,j,k;
   for(i=1;i<=m-3;i++){
       for(j=i+1;j<=m-2;j++){
           for(k=j+1;k<=m-1;k++){
                int pre_x=0,count=0;  //pre_x 前一个x
                for(int x=1;x<=n;x++){
                    int area1 = getArea(pre_x,0, x, i);
                    int area2 = getArea(pre_x,i, x, j);
                    int area3 = getArea(pre_x,j, x, k);
                    int area4 = getArea(pre_x,k, x, m);
 
                    if(area1>=mid &&area2>=mid && area3>=mid && area4>=mid){
                        pre_x = x;
                        count++;
                    }
                }
                if(count>=4){
                    return true;
                }
           }
       }
    }
   return false;
 
}
int main(){
   while(cin>>n>>m){
       if(n<4 || m<4){
           cout<<0<<endl;
           continue;
       }
       memset(sum, 0, sizeof(sum));
       int i,j;
       char ch;
       for(i=1;i<=n;i++){
           for(j=1;j<=m;j++){
                cin>>ch;
                a[i][j] = ch-'0';
                sum[i][j] = sum[i-1][j] +sum[i][j-1] - sum[i-1][j-1] + a[i][j];
           }//for
       }//for
 
       int ans=0;
       //二分
 
       int left=0, right=sum[n][m];
       while(left<=right){
           int mid=(left+right)>>1;  //除以2
           if(judge(mid)){
                left = mid+1;
               ans = mid;
           }else{
                right = mid-1;
           }
       }//while
       cout<<ans<<endl;
 
    }
   return 0;
 
}

5、[编程题]分苹果

n 只奶牛坐在一排，每个奶牛拥有 a_i 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

思路：

（1）随着每头奶牛苹果的输入，算出总的苹果数，如果除以奶牛头数n可以除断，那么可以得到每头奶牛的苹果数。如果除不断，那么返回-1即可。

（2）得到了每头奶牛的苹果数each，遍历一遍所有奶牛的苹果，以苹果数大于each的奶牛为准。算出相差的苹果数tmp，如果tmp除不断2，直接返回-1。否则count += (tmp-each)/2。最后输出count。

 

c++代码：

#include<iostream>
using namespace std;
 
int main(){
   int n; //n只奶牛
   int a[101];  //a[i]表示第i只奶牛拥有的苹果数
   while(cin>>n){
       int i;
       int total=0;
       for(i=0;i<n;i++){
           cin>>a[i];
           total+=a[i];
       }//for 输入
       if(total%n != 0){  //说明不可能存在n头奶牛拥有苹果数相同的时候
           cout<<-1<<endl;
           continue;
       }
 
       //否则每头奶牛拥有的苹果数是 total/n 个
       int each = total/n;
       int count=0;
       for(i=0;i<n;i++){
           if(a[i] == each){
                continue;
           }else if(a[i]>each){
                if((a[i]-each)%2 != 0){
                    cout<<-1<<endl;
                    break;
                }else{
                    count += (a[i]-each)/2;
                }
           }else{
                // a[i]<each的情况
                if((each-a[i])%2 != 0){
                    cout<<-1<<endl;
                    break;
                }
           }
       }
       if(i==n)
           cout<<count<<endl;
 
   }//while
   return 0;
}

 

6、[编程题]星际穿越

航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x² 程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其1可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？ 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

总结：

对于数字输入的时候能用long就别用int，这里经常会出现溢出。

 

c++代码：

#include<iostream>
using namespace std;
 
int main(){
   long h;  //一个飞行器的耐久度
   while(cin>>h){
       long i=0;
       while((i+i*i)<=h){
           i++;
       }
       cout<<i-1<<endl;
   }//while
   return 0;
}

7、[编程题]藏宝图

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有{空串, a, b, c, ab, ac, bc, abc} 8 种。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

c++代码：

#include<iostream>
#include<cstring>
usingnamespace std;
intmain(){
    string s,t; //t是否是s的子序列
    while(cin>>s>>t){
        int len1 = s.length();  //总序列
        int len2 = t.length();  //子序列
        int i=0,j=0;
        while(i<len1 && j<len2){
            if(s[i] == t[j]){
                i++;
                j++;
            }else{
                i++;
            }
        }
 
        if(j == len2){
           cout<<"Yes"<<endl;
        }else{
           cout<<"No"<<endl;
        }
    }//while
 
 
    return 0;
}
 

8、[编程题]数列还原

牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j]的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。 

输入描述:

 

输出描述:

 

输入例子:

 

输出例子:

 

思路：先算出哪些元素是被模糊的了，用num_2存储起来，然后对于num_2进行全排列加入原数组中计算其顺序对是否等于k，若等于k，计数count加1。最后输出count。

 

c++代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int cal(vector<int> a){
   //计算a中顺序对的个数
   int len=a.size();
   int i,j;
   int count=0;
   for(i=0;i<len;i++){
       for(j=i+1;j<len;j++){
           if(a[j]>a[i]){
                count++;
           }
       }
   }//for
   return count;
}
 
int main(){
   int n,k;  //长度为n，牛牛记得的顺序对对数为k对
   while(cin>>n>>k){
       int count=0;
       vector<int> a;  //存原始的元素
       vector<int> flag_1;  //存不为0的元素下标
       vector<int> flag_2;  //存为0的元素下标
       vector<int> num_1;  //存不为0的元素值
       vector<int> num_2;  //存为0的元素值实际是哪些
       int i,j;
       int tmp;
       for(i=0;i<n;i++){
           cin>>tmp;
           a.push_back(tmp);
           if(tmp == 0){
                flag_2.push_back(i);
           }else{
                flag_1.push_back(i);
                num_1.push_back(tmp);
           }
       }
 
       for(i=1;i<=n;i++){
           if(find(num_1.begin(), num_1.end(), i) == num_1.end()){
                num_2.push_back(i);
           }
       }
 
       //对所有num_2中元素进行全排列
       do{
           vector<int> b = a;
           //讲num_2的元素按顺序放入b中
           //flag_2的元素个数和num_2的元素个数相等
           int len= (int) flag_2.size();
           for(i=0;i<len;i++){
                b[flag_2[i]] = num_2[i];
           }
 
           //计算b的顺序对个数
           if(cal(b) == k){
                count++;
           }
 
       }while(next_permutation(num_2.begin(), num_2.end()));
 
       cout<<count<<endl;
 
   }//while
   return 0;
 
}