网易2017春招笔试真题编程题集合题解

前言

想想已经有一年多没有接触算法题了，忙活了一年多没什么用的东西，才陡然发现自己竟然就要毕业了，然而审视了下自己的水平估计还达不到大一的程度，甚是惊恐。于是下定决心开始刷一点题，打好基本功。正好有同学在做网易笔试题的时候来向我问问题，我看了看有12道，好像也不多，于是就顺便刷了刷。本以为会是一帆风顺的，可是事实是，我果然还是太菜了。。。

双核处理

题目

一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

输入描述

输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)
第二行为n个整数length[i](1024 ≤ length[i] ≤ 4194304)，表示每个任务的长度为length[i]kb，每个数均为1024的倍数。

输出描述
输出一个整数，表示最少需要处理的时间

输入例子
5
3072 3072 7168 3072 1024

输出例子
9216

分析

题意很清晰，就是给一个数组，要我们把他分成两份并分别求和，使得这两个和的最大值最小。
我下意识的想法是枚举出所有有可能的和，但是复杂度大概是$O(2^n)$，貌似会超时。可是仔细一看，$length[i]$的取值在$[1,4096]$之间，那么最多n个数的和的范围肯定在$[n,4096n]$之间。那么我们只要对能取到的和打个表，而且表的长度肯定不超过$4096*50=204800$，再加上总共遍历n遍，计算量大概是1e7的级别，可解。

我的答案

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int n;
int a[51];
set<int>s;
int sum=0;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        a[i]=tmp/1024;
        sum+=a[i];
    }
    s.insert(0);
    for(int i=0;i<n;i++){
        set<int>added;
        for(set<int>::iterator it=s.begin();it!=s.end();it++){
            added.insert(*it+a[i]);
        }
        s.insert(added.begin(),added.end());
    }
    int ans=sum;
    for(set<int>::iterator it=s.begin();it!=s.end();it++){
        ans=min(ans,max(*it,sum-*it));
    }
    cout<<ans*1024<<endl;
}

赶去公司

题目

终于到周末啦！小易走在市区的街道上准备找朋友聚会，突然服务器发来警报,小易需要立即回公司修复这个紧急bug。假设市区是一个无限大的区域，每条街道假设坐标是(X，Y)，小易当前在(0，0)街道，办公室在(gx,gy)街道上。小易周围有多个出租车打车点，小易赶去办公室有两种选择，一种就是走路去公司，另外一种就是走到一个出租车打车点，然后从打车点的位置坐出租车去公司。每次移动到相邻的街道(横向或者纵向)走路将会花费walkTime时间，打车将花费taxiTime时间。小易需要尽快赶到公司去，现在小易想知道他最快需要花费多少时间去公司。
输入描述:
输入数据包括五行:

第一行为周围出租车打车点的个数n(1 ≤ n ≤ 50)

第二行为每个出租车打车点的横坐标tX[i] (-10000 ≤ tX[i] ≤ 10000)

第三行为每个出租车打车点的纵坐标tY[i] (-10000 ≤ tY[i] ≤ 10000)

第四行为办公室坐标gx,gy(-10000 ≤ gx,gy ≤ 10000),以空格分隔

第五行为走路时间walkTime(1 ≤ walkTime ≤ 1000)和taxiTime(1 ≤ taxiTime ≤ 1000),以空格分隔

输出描述:
输出一个整数表示，小易最快能赶到办公室的时间

输入例子:
2
-2 -2
0 -2
-4 -2
15 3

输出例子:
42

分析

基础题，先算步行的时间，再枚举每个打车点算出打的时间，找到时间最短的即可。

我的答案

#include<iostream>
#include<algorithm>
#define MAX 100000000
using namespace std;
int n;
int tx[51],ty[51];
int gx,gy;
int wt,dt;
int main(){
    cin>>n;
    int walkTime=MAX,driveTime=MAX;
    for(int i=0;i<n;i++){
        cin>>tx[i];
    }
    for(int i=0;i<n;i++){
        cin>>ty[i];
    }
    cin>>gx>>gy>>wt>>dt;
    walkTime=(abs(gx)+abs(gy))*wt;
    for(int i=0;i<n;i++){
        driveTime=min(driveTime,(abs(ty[i])+abs(tx[i]))*wt+(abs(ty[i]-gy)+abs(tx[i]-gx))*dt);
    }
    cout<<min(driveTime,walkTime)<<endl;
}

调整队形

题目

在幼儿园有n个小朋友排列为一个队伍，从左到右一个挨着一个编号为(0~n-1)。其中有一些是男生，有一些是女生，男生用’B’表示，女生用’G’表示。小朋友们都很顽皮，当一个男生挨着的是女生的时候就会发生矛盾。作为幼儿园的老师，你需要让男生挨着女生或者女生挨着男生的情况最少。你只能在原队形上进行调整，每次调整只能让相邻的两个小朋友交换位置，现在需要尽快完成队伍调整，你需要计算出最少需要调整多少次可以让上述情况最少。例如：
GGBBG -> GGBGB -> GGGBB
这样就使之前的两处男女相邻变为一处相邻，需要调整队形2次
输入描述:
输入数据包括一个长度为n且只包含G和B的字符串.n不超过50.

输出描述:
输出一个整数，表示最少需要的调整队伍的次数

输入例子:
GGBBG

输出例子:
2

分析

事实上，最终的结果只有两种可能，要么是GGG…BBB，要么是BBB…GGG。我们不妨考虑B，我们可以事先求出B全部在左边和全部在右边两种情况下的和。然后对当前每个B的下标求和，显然我们每进行一次有用的调整必然使当前的和+1或者-1。那么，我们只要计算出当前的和与最终结果的和的差就行了，由于最终结果有两种情况，我们取最小值即可。

我的答案

#include<iostream>
#include<string>
using namespace std;
int main(){
    string s;
    cin>>s;
    int cntB=0;
    int valB=0;
    for(int i=0;i<s.length();i++){
        cntB+=s[i]=='B';
        valB+=s[i]=='B'?i:0;
    }
    int leftB=valB-cntB*(cntB-1)/2;
    int rightB=(2*s.length()-cntB-1)*cntB/2-valB;
    cout<<min(leftB,rightB)<<endl;
}

消除重复元素

题目

小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。
输入描述:
输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequence[i](1 ≤ sequence[i] ≤ 1000)，以空格分隔

输出描述:
输出消除重复元素之后的序列，以空格分隔，行末无空格

输入例子:
9
100 100 100 99 99 99 100 100 100

输出例子:
99 100

分析

从后向前先判重后加入即可。

我的答案

#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
int main(){
    int n;
    int a[1002]={0};
    vector<int>v;
    set<int>s;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=n-1;i>=0;i--){
        if(s.find(a[i])==s.end()){
            s.insert(a[i]);
            v.push_back(a[i]);
        }
    }
    cout<<v[v.size()-1];
    for(int i=v.size()-2;i>=0;i--){
        cout<<" "<<v[i];
    }
    cout<<endl;

魔力手环

题目

小易拥有一个拥有魔力的手环上面有n个数字(构成一个环),当这个魔力手环每次使用魔力的时候就会发生一种奇特的变化：每个数字会变成自己跟后面一个数字的和(最后一个数字的后面一个数字是第一个),一旦某个位置的数字大于等于100就马上对100取模(比如某个位置变为103,就会自动变为3).现在给出这个魔力手环的构成，请你计算出使用k次魔力之后魔力手环的状态。
输入描述:
输入数据包括两行：
第一行为两个整数n(2 ≤ n ≤ 50)和k(1 ≤ k ≤ 2000000000),以空格分隔
第二行为魔力手环初始的n个数，以空格分隔。范围都在0至99.

输出描述:
输出魔力手环使用k次之后的状态，以空格分隔，行末无空格。

输入例子:
3 2
1 2 3

输出例子:
8 9 7

分析

矩阵快速幂模板题。。。

我的答案

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 52
#define MOD 100
struct Matrix{
    int n,m;
    int a[MAX][MAX];
    void clear(){
        n=m=0;
        memset(a,0,sizeof a);
    }
    Matrix operator +(const Matrix &b)const{
        Matrix tmp;
        tmp.n=n;
        tmp.m=m;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp.a[i][j]=(a[i][j]+b.a[i][j])%MOD;
        return tmp;
    }
    Matrix operator *(const Matrix &b)const{
        Matrix tmp;
        tmp.clear();
        tmp.n=n;
        tmp.m=b.m;
        for(int i=0;i<n;i++)
            for(int j=0;j<b.m;j++)
                for(int k=0;k<m;k++)
                    tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*b.a[k][j])%MOD;
        return tmp;
    }
    void print()const{
        for(int i=0;i<n;i++){
            for(int j=0;j<m-1;j++)
                cout<<a[i][j]<<" ";
            cout<<a[i][m-1]<<endl;
        }
    }
    Matrix operator ^(int k)const{
        Matrix tmp,mul;
        tmp.clear();
        mul.clear();
        mul.n=mul.m=tmp.m=tmp.n=n;
        mul=mul+(*this);
        for(int i=0;i<n;i++)
            tmp.a[i][i]=1;
        while(k>0){
            if(k&1){
                tmp=tmp*mul;
            }
            k>>=1;
            mul=mul*mul;
        }
        return tmp;
    }
    Matrix transpose(){
        Matrix tmp;
        tmp.n=m;
        tmp.m=n;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                tmp.a[j][i]=a[i][j];
        return tmp;
    }
};
int n,k;
int main(){
    Matrix arr;
    cin>>n>>k;
    arr.m=1;
    arr.n=n;
    for(int i=0;i<n;i++)
        cin>>arr.a[i][0];
    Matrix mul;
    mul.clear();
    mul.n=mul.m=n;
    for(int i=0;i<n;i++){
        mul.a[i][i]=1;
        mul.a[i][(i+1)%n]=1;
    }
    arr=(mul^k)*arr;
    arr.transpose().print();
}

工作安排

题目

现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。
输入描述:
输入数据有n+1行：
第一行为工程师人数n(1 ≤ n ≤ 6)
接下来的n行，每行一个字符串表示第i(1 ≤ i ≤ n)个人能够胜任的工作(字符串不一定等长的)

输出描述:
输出一个整数，表示有多少种不同的工作安排方案

输入例子:
6
012345
012345
012345
012345
012345
012345

输出例子:
720

分析

空间不大，直接dfs就行了。

我的答案

#include<iostream>
#include<cstring>
using namespace std;
bool can[6][6];
bool vis[6];
int n;
int dfs(int now){
    int ans=0;
    for(int i=0;i<6;i++){
        if(can[now][i]&&!vis[i]){
            vis[i]=true;
            if(now==0)
                ans++;
            else
                ans+=dfs(now-1);
            vis[i]=false;
        }
    }
    return ans;
}
int main(){
    cin>>n;
    memset(can,0,sizeof can);
    memset(vis,0,sizeof vis);
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        for(int j=0;j<s.length();j++)
            can[i][s[j]-'0']=true;
    }
    cout<<dfs(n-1)<<endl;
}

集合

题目

小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。
输入描述:
输入包括一行：
一共4个整数分别是w(1 ≤ w ≤ x)，x(1 ≤ x ≤ 100)，y(1 ≤ y ≤ z)，z(1 ≤ z ≤ 100).以空格分隔

输出描述:
输出集合中元素的个数

输入例子:
1 10 1 1

输出例子:
10

分析

题意就是给分数判重，显然我们不能直接算，因为浮点数是不精确的，建个结构体保存最简分数，然后丢进set里就好了。

我的答案

#include<iostream>
#include<cstring>
#include<set>
using namespace std;
struct Frac{
    int p,q;
    bool operator<(const Frac &frac)const{
        if(p!=frac.p)
            return p<frac.p;
        if(q!=frac.q)
            return q<frac.q;
        return false;
    }
};
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int w,x,y,z;
    set<Frac>s;
    cin>>w>>x>>y>>z;
    Frac f;
    for(int i=w;i<=x;i++){
        for(int j=y;j<=z;j++){
            int div=gcd(i,j);
            f.p=i/div;
            f.q=j/div;
            s.insert(f);
        }
    }
    cout<<s.size()<<endl;
}

奇怪的表达式求值

题目

常规的表达式求值，我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+, - 和 *)。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少
输入描述:
输入为一行字符串，即一个表达式。其中运算符只有-,+,*。参与计算的数字只有0~9.
保证表达式都是合法的，排列规则如样例所示。

输出描述:
输出一个数，即表达式的值

输入例子:
3+5*7

输出例子:
56

分析

小模拟。。。

我的答案

#include<iostream>
#include<string>
using namespace std;
bool isNumber(char c){
    return c>='0'&&c<='9';
}
int main(){
    string s;
    cin>>s;
    int num=0,ans=0;
    char op='+';
    for(int i=0;i<s.length();i++){
        if(isNumber(s[i])){
            num=num*10+s[i]-'0';  
        }else{
            if(op=='+'){
                ans=ans+num;
            }else if(op=='*'){
                ans=ans*num;
            }else{//op=='-'
                ans=ans-num;
            }
            op=s[i];
            num=0;
        }
    }
    if(op=='+'){
        ans=ans+num;
    }else if(op=='*'){
        ans=ans*num;
    }else{//op=='-'
        ans=ans-num;
    }
    cout<<ans<<endl;
}

涂棋盘

题目

小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。
输入描述:
输入数据包括n+1行：

第一行为一个整数n(1 ≤ n ≤ 50),即棋盘的大小

接下来的n行每行一个字符串表示第i行棋盘的颜色，’W’表示白色，’B’表示黑色

输出描述:
输出小易会涂画的区域大小

输入例子:
3
BWW
BBB
BWB

输出例子:
3

分析

小模拟，注意只能涂相邻连续的。。。

我的答案

#include<iostream>
#include<string>
using namespace std;
string s[52];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>s[i];
    int maxCnt=0;
    for(int j=0;j<n;j++){
        int cnt=1;
        for(int i=1;i<n;i++){
            if(s[i][j]==s[i-1][j]){
                cnt++;
            }else{
                maxCnt=max(maxCnt,cnt);
                cnt=1;
            }
        }
        maxCnt=max(maxCnt,cnt);
    }
    cout<<maxCnt<<endl;
}

小易记单词

题目

小易参与了一个记单词的小游戏。游戏开始系统提供了m个不同的单词，小易记忆一段时间之后需要在纸上写出他记住的单词。小易一共写出了n个他能记住的单词，如果小易写出的单词是在系统提供的，将获得这个单词长度的平方的分数。注意小易写出的单词可能重复，但是对于每个正确的单词只能计分一次。
输入描述:
输入数据包括三行：

第一行为两个整数n(1 ≤ n ≤ 50)和m(1 ≤ m ≤ 50)。以空格分隔

第二行为n个字符串，表示小易能记住的单词，以空格分隔，每个单词的长度小于等于50。

第三行为m个字符串，系统提供的单词，以空格分隔，每个单词的长度小于等于50。

输出描述:
输出一个整数表示小易能获得的分数

输入例子:
3 4
apple orange strawberry
strawberry orange grapefruit watermelon

输出例子:
136

分析

把能记住的单词丢进set里，然后判断每一个是不是在系统提供的集合里即可。

我的答案

#include<iostream>
#include<set>
using namespace std;
int main(){
    int n,m;
    set<string>s1,s2;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        s1.insert(s);
    }
    for(int i=0;i<m;i++){
        string s;
        cin>>s;
        s2.insert(s);
    }
    int ans=0;
    for(set<string>::iterator it=s1.begin();it!=s1.end();it++){
        if(s2.find(*it)!=s2.end()){
            ans+=it->length() * it->length();
        }
    }
    cout<<ans<<endl;
}

堆砖块

题目

小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。
输入描述:
输入包括两行：
第一行为整数n(1 ≤ n ≤ 50)，即一共有n块砖块
第二行为n个整数，表示每一块砖块的高度height[i] (1 ≤ height[i] ≤ 500000)

输出描述:
如果小易能堆砌出两座高度相同的塔，输出最高能拼凑的高度，如果不能则输出-1.
保证答案不大于500000。

输入例子:
3
2 3 5

输出例子:
5

分析

不知道怎么搞，看到题目保证答案不大于500000，想想这不是在提示我们“暴力搞没问题，我数据不大”么。于是我就就暴力搜索，枚举两堆塔的高度，但是需要一些剪枝：

当其中一堆高度大于500000,可以剪掉;
当较低的堆+剩下的砖块<较高的堆时，可以剪掉;
当当前可能达到的最大高度小于已经发现最大高度时，可以剪掉;

我的答案

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 500000
int height[52];
int sum[52];
int n;
int ans=0;
void dfs(int n,int sum1,int sum2){
    if(sum1==sum2)
        ans=max(ans,sum1);
    if(n==0)
        return;
    if(sum1>MAX)
        return;
    if(sum1+sum[n]<sum2)
        return;
    if((sum1+sum2+sum[n])<=ans*2)
        return;
    dfs(n-1,min(sum1+height[n],sum2),max(sum1+height[n],sum2));
    dfs(n-1,min(sum2+height[n],sum1),max(sum2+height[n],sum1));
    dfs(n-1,sum1,sum2);
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>height[i];
    sort(height+1,height+n+1);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+height[i];
    dfs(n,0,0);
    cout<<(ans?ans:-1)<<endl;
}

分饼干

题目

易老师购买了一盒饼干，盒子中一共有k块饼干，但是数字k有些数位变得模糊了，看不清楚数字具体是多少了。易老师需要你帮忙把这k块饼干平分给n个小朋友，易老师保证这盒饼干能平分给n个小朋友。现在你需要计算出k有多少种可能的数值
输入描述:
输入包括两行：

第一行为盒子上的数值k，模糊的数位用X表示，长度小于18(可能有多个模糊的数位)

第二行为小朋友的人数n

输出描述:
输出k可能的数值种数，保证至少为1

输入例子:
9999999999999X
3

输出例子:
4

分析

显然数字太大我们不能直接计算模(超过long long)，而且也不能枚举X(否则空间可能有$10^{18}$)。不过我们考虑到模n应该不大（喂喂，怎么题目没有给n的范围啊～），因此可以考虑用动态规划的思想从这里入手。
用$mod[k]$表示当前所有情况下模n余k的数量。如果我们把前i位当成一个整体$s[0:i]$，而且知道了$mod[0:n]$的值，那么对于前i+1位而言，$mod[k]$的值会贡献到$mod[(k*10+s[i+1])mod\%n]$上。如果$s[i+1]$的值是X，那么我们只要将$s[i+1]$遍历10次。
总体上说，就是从前往后遍历，依次更新mod数组，最后的结果当然就是$mod[0]$了。
注意long long 。

我的答案

#include<iostream>
#include<cstring>
using namespace std;
#define MAXN 100000
void transform1(long long mod[],int n){
    long long tmpMod[MAXN]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            tmpMod[(i*10+j)%n]+=mod[i];
        }
    }
    memcpy(mod,tmpMod,sizeof tmpMod);
}
void transform2(long long mod[],int k,int n){
    long long tmpMod[MAXN]={0};
    for(int i=0;i<n;i++){
        tmpMod[(i*10+k)%n]+=mod[i];
    }
    memcpy(mod,tmpMod,sizeof tmpMod);
}
int main(){
    long long mod[MAXN]={0};
    string s;
    int n;
    cin>>s>>n;
    mod[0]=1;
    for(int i=0;i<s.length();i++){
        if(s[i]=='X'){
            transform1(mod,n);
        }else{
            transform2(mod,s[i]-'0',n);
        }
    }
    cout<<mod[0]<<endl;
}