网易2018校园招聘编程题真题集合 详解

##编程题
###一、魔法币
####描述：
小易准备去魔法王国采购魔法神器,购买魔法神器需要使用魔法币,但是小易现在一枚魔法币都没有,但是小易有两台魔法机器可以通过投入 $x$($x$ 可以为 $0$)个魔法币产生更多的魔法币。
魔法机器 $1$:如果投入 $x$ 个魔法币,魔法机器会将其变为 $2x+1$ 个魔法币；
魔法机器 $2$:如果投入 $x$ 个魔法币,魔法机器会将其变为 $2x+2$ 个魔法币；
小易采购魔法神器总共需要 $n$ 个魔法币,所以小易只能通过两台魔法机器产生恰好 $n$ 个魔法币,小易需要你帮他设计一个投入方案使他最后恰好拥有 $n$ 个魔法币。
####输入描述：
输入包括一行,包括一个正整数 $n(1\le n\le 10^9)$,表示小易需要的魔法币数量。
####输出描述：
输出一个字符串,每个字符表示该次小易选取投入的魔法机器。其中只包含字符 ${}^{\prime }{1}^{\prime }$ 和 ${}^{\prime }{2}^{\prime }$。
####输入样例：
$10$
####输出样例：
$122$

####题解：
两台机器分别可以产出 $2x+1$ 与 $2x+2$ 的魔法币，所以给一个数 $n$，一定可以有一台机器恰好生存它，所以我们可以从 $n$ 开始往下拆分，如果是偶数，则使用第二台机器，否则用第一台机器，获取新的 $n$，循环这个操作，直到 $n=0$，记录这个过程所用的机器顺序，不过这个顺序我们需要反转一下再输出，因为题目是从 $0$ 为初始增长到 $n$ 的。
####代码：

#include <bits/stdc++.h>

using namespace std;   

int n;
string res = "";

void solve()
{
    while (n > 0)
	{  
        if (n % 2 == 0)
		{  
            res += '2';  
            n = n / 2 - 1;  
        }
        else
		{  
            res += '1';  
            n = n / 2;  
        }  
    }
}

int main()
{
    cin >> n;  
    
    solve();
    
    reverse(res.begin(), res.end());
	
	cout << res << '\n';
	 
    return 0;  
}  

###二、相反数
####描述：
为了得到一个数的"相反数",我们将这个数的数字顺序颠倒,然后再加上原先的数得到"相反数"。例如,为了得到 $1325$ 的"相反数",首先我们将该数的数字顺序颠倒,我们得到 $5231$,之后再加上原先的数,我们得到 $5231+1325=6556$。如果颠倒之后的数字有前缀零,前缀零将会被忽略，例如 $n=100$, 颠倒之后是 $1$。
####输入描述：
输入包括一个整数 $n,(1\le n\le 10^5)$。
####输出描述：
输出一个整数,表示 $n$ 的相反数
####输入样例：
$1325$
####输出样例：
$6556$

####题解：
没啥可说的，根据题意，直接拆分原数然后反转合并，加上原数即可。
####代码：

#include <bits/stdc++.h>

using namespace std;   

int n;

int main()
{
    cin >> n;  
    
    int ans = n;
    int tmp = 0;
    
    while (n)
    {
    	tmp *= 10;
    	tmp += n % 10;
    	n /= 10;
	}
	
	ans += tmp;
    
    cout << ans << '\n';
	 
    return 0;  
}

###三、字符串碎片
####描述：
一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,$"aaabbaaac"$ 是由下面碎片组成的:${}^{\prime }aa{a}^{\prime }{,}^{\prime }b{b}^{\prime }{,}^{\prime }{c}^{\prime }$。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。
####输入描述：
输入包括一个字符串 $s$,字符串 $s$ 的长度 $length(1\le length\le 50)$,$s$ 只含小写字母 ${(}^{\prime }{a}^{\prime }{-}^{\prime }{z}^{\prime })$。
####输出描述：
输出一个整数,表示所有碎片的平均长度,四舍五入保留两位小数。
如样例所示: $s="aaabbaaac"$
所有碎片的平均长度 $=(3+2+3+1)/4=2.25$
####输入样例：
$aaabbaaac$
####输出样例：
$2.25$

####题解：
字符串长度 $/$ 碎片个数 $=$ 平均长度。
####代码：

#include <bits/stdc++.h>

using namespace std;   

string s;

int main()
{
    cin >> s;  
    
    double len = s.length();
    
    char c = '?';
    int cnt = 0;
    for (int i = 0; i < s.length(); i++)
    {
    	if (s[i] != c)
    	{
    		cnt++;
    		c = s[i];
		}
	}
	
	printf("%.2f\n", len / cnt);
	
    return 0;  
}

###四、游历魔法王国
####描述：
魔法王国一共有 $n$ 个城市,编号为 $0\sim n-1$ 号,$n$ 个城市之间的道路连接起来恰好构成一棵树。
小易现在在 $0$ 号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动 $L$ 次。
如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多的城市,请你帮他计算一下他最多能游历过多少个城市(注意 $0$ 号城市已经游历了,游历过的城市不重复计算)。
####输入描述：
输入包括两行,第一行包括两个正整数 $n(2\le n\le 50)$ 和 $L(1\le L\le 100)$,表示城市个数和小易能行动的次数。
第二行包括 $n-1$ 个整数 $parent[i](0\le parent[i]\le i)$, 对于每个合法的 $i(0\le i\le n-2)$,在 $(i+1)$ 号城市和 $parent[i]$ 间有一条道路连接。
####输出描述：
输出一个整数,表示小易最多能游历的城市数量。
####输入样例：
$52$
$0123$
####输出样例：
$3$

####题解：
这个题并不像想象中那么复杂，是一个树上贪心的问题。

首先我们来思考一下，怎么样才能让走的点最多？
我们可以考虑从根开始走，走尽量远，期间不折返，能走多少步，也就是说树的最大深度是多少？如果树的最大深度比步数要大（默认根的深度为 $0$），那么我们就只能游历 $L+1$ 个城市；否则，我们能够将多余的步数用来访问其他城市，不过这些城市访问后需要折返，折返回这个能够到达最大深度的路径上，此时，按道理我们可以访问 $mx\_dep+(L-mx\_dep)/2+1$ 个城市，不过如果这个值大于 $N$，那么我们只能不用完所有步数，而输出一个 $N$，否则输出 $mx\_dep+(L-mx\_dep)/2+1$。

此时，就剩下一个问题了，如何求深度，最直观的解法是 $dfs$ 遍历一遍树，不过这个题有一个十分强的条件，$0\le parent[i]\le i$，$i+1$ 的父节点是 $parent[i]$，那么在输入过程中，我们可以直接根据父节点的深度加一来获取该节点深度，因为此时父节点的深度我们一定知道。
####代码：

#include <bits/stdc++.h>

using namespace std;   

const int MAXN = 55;

int N, L;
int dep[MAXN];

int main()
{
    cin >> N >> L;
    
    int par, mx_dep = 1;
    for (int i = 1; i < N; i++)
    {
    	cin >> par;
    	dep[i] = dep[par] + 1;
    	if (dep[i] > mx_dep)
    	{
    		mx_dep = dep[i];
		}
	}
	
	if (mx_dep < L)
	{
		int tmp = mx_dep + (L - mx_dep) / 2 + 1;
		if (tmp > N)
		{
			cout << N << '\n';
		}
		else
		{
			cout << tmp << '\n';
		}
	}
	else
	{
		cout << L + 1 << '\n';
	}
	
    return 0;  
}

###五、重排数列
####描述：
小易有一个长度为 $N$ 的正整数数列 $A=A[1],A[2],A[3]...,A[N]$。
牛博士给小易出了一个难题:
对数列 $A$ 进行重新排列,使数列A满足所有的 $A[i]\ast A[i+1](1\le i\le N-1)$ 都是 $4$ 的倍数。
小易现在需要判断一个数列是否可以重排之后满足牛博士的要求。
####输入描述：
输入的第一行为数列的个数 $t(1\le t\le 10)$,
接下来每两行描述一个数列 $A$,第一行为数列长度 $n(1\le n\le 10^5)$
第二行为 $n$ 个正整数 $A[i](1\le A[i]\le 10^9)$
####输出描述：
对于每个数列输出一行表示是否可以满足牛博士要求,如果可以输出 $Yes$,否则输出 $No$。
####输入样例：
2
3
1 10 100
4
1 2 3 4
####输出样例：
Yes
No

####题解：
分别计数，奇数个数 $a$、四倍数个数 $b$、非四倍数的二倍数个数 $c$。

如果说 $c>0$，需要将偶数从一端挨个排列，然后另一端四倍数与奇数交替排列，所以 $a$ 不多于 $b$ 时，$Yes$，反之，$No$；
如果说 $c==0$，则需要将奇数与四倍数交替排列，所以 $a$ 不多于 $b+1$ 时，$Yes$，反之，$No$。
####代码：

#include <bits/stdc++.h>

using namespace std;   

int T, N;

int main()
{
	cin >> T;
	
	while (T--)
	{
		cin >> N;
	
		int Odd_cnt = 0;
		int Mul4_cnt = 0;
		int Mul2Not4_cnt = 0;
		int x;
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &x);
			if (x & 1)
			{
				Odd_cnt++;
			}
			else if (x % 4 == 0)
			{
				Mul4_cnt++;
			}
			else
			{
				Mul2Not4_cnt++;
			}
		}
	
		if (Mul2Not4_cnt)
		{
			if (Odd_cnt > Mul4_cnt)
			{
				cout << "No" << '\n';
			}
			else
			{
				cout << "Yes" << '\n';
			}
		}
		else
		{
			if (Odd_cnt > Mul4_cnt + 1)
			{
				cout << "No" << '\n';
			}
			else
			{
				cout << "Yes" << '\n';
			}
		}
	}
	
    return 0;  
}

###六、最长公共子括号序列
####描述：
一个合法的括号匹配序列被定义为:

1. 空串 $""$ 是合法的括号序列
2. 如果 $"X"$ 和 $"Y"$ 是合法的序列,那么 $"XY"$ 也是一个合法的括号序列
3. 如果 $"X"$ 是一个合法的序列,那么 $"(X)"$ 也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
   例如 $"","()","()()()","(()())","(((()))"$ 都是合法的。
   从一个字符串 $S$ 中移除零个或者多个字符得到的序列称为 $S$ 的子序列。
   例如 $"abcde"$ 的子序列有 $"abe","","abcde"$ 等。
   定义 $LCS(S,T)$ 为字符串 $S$ 和字符串 $T$ 最长公共子序列的长度,即一个最长的序列 $W$ 既是 $S$ 的子序列也是 $T$ 的子序列的长度。
   小易给出一个合法的括号匹配序列 $s$,小易希望你能找出具有以下特征的括号序列 $t$:
   1、$t$ 跟 $s$ 不同,但是长度相同
   2、$t$ 也是一个合法的括号匹配序列
   3、$LCS(s,t)$ 是满足上述两个条件的t中最大的
   因为这样的 $t$ 可能存在多个,小易需要你计算出满足条件的 $t$ 有多少个。

如样例所示: $s="(())()"$,跟字符串 $s$ 长度相同的合法括号匹配序列有:
$"()(())","((()))","()()()","(()())"$,其中 $LCS("(())()","()(())")$ 为 $4$,其他三个都为 $5$,所以输出 $3$.
####输入描述：
输入包括字符串 $s(4\le |s|\le 50,|s|$ 表示字符串长度),保证 $s$ 是一个合法的括号匹配序列。
####输出描述：
输出一个正整数,满足条件的 $t$ 的个数。
####输入样例：
$(())()$
####输出样例：
$3$

####题解：
假如说，初始合法括号匹配序列长度为 $len$，那么最大 $LCS$ 一定是 $len-1$，那么我们如何凑 $LCS$ 结果为 $len-1$ 的序列呢？

其实这个并不难，我们可以抽出一个括号然后插入到别的地方，如果说抽出插入后的括号序列不同于原序列并且是合法的括号匹配序列，那么这就是我们所要找的序列之一。

这里还有一个问题便是，如果我们直接输出有多少种合法的抽出插入的方案，那么就会存在重复计算的可能，因为有的方案虽然不一样，但是最后获得的序列可能会一样，所以我们采用 $map$ 存储一下已找到的合法序列，最后输出有多少个不同的合法序列即可。
####代码：

#include <bits/stdc++.h>

using namespace std;   

int len;
string s;
map<string, int> msi;

bool charge(string str)
{
	int tag = 0;
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '(')
		{
			tag++;
		}
		else
		{
			tag--;
		}
		
		if (tag < 0)
		{
			return false;
		}
	}
	
	return true;
}

int main()
{
	cin >> s;
	len = s.size();
	
	for (int i = 0; i < len; i++)
	{
		//	抽出第 i 个括号 
		string tmp = s.substr(0, i) + s.substr(i + 1, len - i - 1);
		for (int j = 0; j < len; j++)
		{
			string tep = tmp.substr(0, j) + s[i] + tmp.substr(j, len - j - 1);
			if (tep != s && charge(tep))
			{
				msi[tep] = 1;
			}
		}
	}
	
	cout << msi.size() << '\n';
	
	return 0;
}

###七、合唱
####描述：
小 $Q$ 和牛博士合唱一首歌曲,这首歌曲由 $n$ 个音调组成,每个音调由一个正整数表示。
对于每个音调要么由小 $Q$ 演唱要么由牛博士演唱,对于一系列音调演唱的难度等于所有相邻音调变化幅度之和, 例如一个音调序列是 $8,8,13,12$, 那么它的难度等于 $|8-8|+|13-8|+|12-13|=6$ (其中 $||$ 表示绝对值)。
现在要对把这 $n$ 个音调分配给小 $Q$ 或牛博士,让他们演唱的难度之和最小,请你算算最小的难度和是多少。

如样例所示: 小 $Q$ 选择演唱 $5,6$ 难度为 $1$, 牛博士选择演唱 $1,2,1$ 难度为 $2$,难度之和为 $3$,这一个是最小难度和的方案了。
####输入描述：
输入包括两行,第一行一个正整数 $n(1\le n\le 2000)$ 第二行 $n$ 个整数 $v[i](1\le v[i]\le 10^6)$, 表示每个音调。
####输出描述：
输出一个整数,表示小 $Q$ 和牛博士演唱最小的难度和是多少。
####输入样例：
$5$
$15621$
####输出样例：
$3$

####题解：
典型的动态规划问题。

设 $dp[i][j]$ 表示当前演唱的人唱到第 $i$ 个，另一个人演唱到第 $j$ 个，当 $j<i-1$ 时，说明唱第 $i$ 个调时没有换人，所以可以直接从 $dp[i-1][j]$ 转移过来；当 $j=i-1$ 时，说明此时切换人了，但是我们并不知道当前演唱的人上一次什么时候演唱，所以我们需要枚举他上次演唱的位置，取最小来转移。

所以状态转移方程为：
$dp[i][j]=dp[i-1][j]+abs(v[i]-v[i-1]),j<i-1$
$dp[i][i-1]=min(dp[i-1][k]+abs(v[i]-v[k])),k<i-1$

初始情况（边界情况）是若当前有 $i$ 个音调，可以让一个人只唱第一个或最后一个音调，剩下的音调都由另一个人唱：
$dp[i][0]=dp[i-1][0]+abs(v[i]-v[i-1]),i\ge 2$
$dp[i][i-1]=dp[i-1][i-2]+abs(v[i-1]-v[i-2]),i\ge 2$

####代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2222;
const int INF = 0x3f3f3f3f;

int n;
int val[MAXN];
int dif[MAXN]; 
int dp[MAXN][MAXN];

int main()
{
	scanf("%d%d", &n, val);
	for (int i = 1; i < n; i++)
	{
		scanf("%d", val + i);
		dif[i] = abs(val[i] - val[i - 1]);
	} 
	
	int res = INF;
	for (int i = 2; i < n; i++)
	{
//		dp[i][0] = dp[i - 1][0] + dif[i];
		dp[i][i - 1] = dp[i - 1][i - 2] + dif[i - 1];
	}
	for (int i = 2; i < n; i++)
	{
		for (int j = 0; j < i - 1; j++)
		{
			dp[i][j] = dp[i - 1][j] + dif[i];
			dp[i][i - 1] = min(dp[i][i - 1], dp[i - 1][j] + abs(val[i] - val[j]));
		}
	}
	
	int ans = INF;
	for (int i = 0; i < n - 1; i++)
	{
		ans = min(ans, dp[n - 1][i]);
	}
	cout << ans << '\n';
	
	return 0;
}

###八、射击游戏
####描述：
小易正在玩一款新出的射击游戏,这个射击游戏在一个二维平面进行,小易在坐标原点 $(0,0)$,平面上有 $n$ 只怪物,每个怪物有所在的坐标 $(x[i],y[i])$。小易进行一次射击会把 $x$ 轴和 $y$ 轴上(包含坐标原点)的怪物一次性消灭。
小易是这个游戏的 $VIP$ 玩家,他拥有两项特权操作:
$1$、让平面内的所有怪物同时向任意同一方向移动任意同一距离
$2$、让平面内的所有怪物同时对于小易 $(0,0)$ 旋转任意同一角度
小易要进行一次射击。小易在进行射击前,可以使用这两项特权操作任意次。
小易想知道在他射击的时候最多可以同时消灭多少只怪物,请你帮帮小易。

如样例所示:

所有点对于坐标原点 $(0,0)$ 顺时针或者逆时针旋转 $45°$,可以让所有点都在坐标轴上,所以 $5$ 个怪物都可以消灭。

####输入描述：
输入包括三行。
第一行中有一个正整数 $n(1\le n\le 50)$,表示平面内的怪物数量。
第二行包括 $n$ 个整数 $x[i](-1,000,000\le x[i]\le 1,000,000)$,表示每只怪物所在坐标的横坐标,以空格分割。
第二行包括 $n$ 个整数 $y[i](-1,000,000\le y[i]\le 1,000,000)$,表示每只怪物所在坐标的纵坐标,以空格分割。
####输出描述：
输出一个整数表示小易最多能消灭多少只怪物。
####输入样例：
$5$
$0-111-1$
$0-1-111$
####输出样例：
$5$

####题解：
首先，我们知道，小易的攻击方式十字型攻击，其次我们知道，同时操作所有点等价于操作小易，所以我们可以将两种操作看做小易可以移动到图中任意点并且可以调整任意攻击角度。

那么我们要寻找的就是一个能够攻击最多的位置及攻击角度，也就是说，我们在寻找一个能够覆盖最多点的十字型。

此时，问题已经十分清晰了，那么怎么找这个十字呢？

首先我们知道任意三个不共线的点可以确定三个十字，如果取两个点连线另一个作垂线便可以确定一个十字，那么我们只需要枚举剩下 $n-3$ 个点是否在这个十字上即可，判断是否在十字上也十分简单，运用数学中判断平行与垂直的公式。比方说，确定 $AB$ 作直线，$C$ 作 $AB$ 垂线，判断点 $D$ 是否在十字上只需要判断 $AD$ 是否平行 $AB$（如果平行则重合）、$CD$ 是否垂直 $AB$（如果垂直则与垂线重合）。

总的来说，外三层循环确定十字，内层循环判断是否被十字覆盖，一共四层循环，复杂度 $O(N^4)$。
####代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 55;

int n;

struct point 
{  
    int x, y;  
} p[MAXN];
  
int main()  
{
    cin >> n;
    for (int i = 0; i < n; ++i)  
    {  
        cin >> p[i].x;  
    }  
    for (int i = 0; i < n; ++i)  
    {  
        cin >> p[i].y;  
    }
    
    if (n <= 3)  
    {  
        cout << n << endl;  
        return 0;
    }
    
    int ans = 3;  
    for (int i = 0; i < n; ++i)  
    {  
        for (int j = 0; j < n; ++j)  
        {  
            if (j == i)  
            {
            	continue;
        	}
        	
            for (int k = 0; k < n; ++k)  
            {  
                if (k == i || k == j)  
                {
					continue;
				}
				
                int cnt = 3;  
                for (int l = 0; l < n; ++l)  
                {  
                    if (l == i || l == j || l == k)
					{
						continue;
					}  
                    
                    if ((p[l].x - p[i].x) * (p[l].y - p[j].y) == (p[l].y - p[i].y) * (p[l].x - p[j].x))  
                    {  
                        cnt++;  
                    }  
                    else if ((p[l].x - p[k].x) * (p[i].x - p[j].x) + (p[l].y - p[k].y) * (p[i].y - p[j].y) == 0)  
                    {  
                        cnt++;
                    }
                }
                
            	ans = max(ans, cnt);  
            }  
        }  
    }
    
    cout << ans << endl;
    
	return 0;
}