网易2017春招笔试详解

网易2017春招笔试详解

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

     思路：要使得工作时间最短，那么最后两个CPU的工作时间的差一定最小，两个CPU的工作时间应该尽量接近所有任务时间和的一半即sum/2，就转换为01背包--容积为sum/2，物品为n个，质量和体积都是t[i]。

AC代码：

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 4194304 / 1024 * 55 + 5;
int dp[maxn], a[55];int main() {int n;while(scanf("%d", &n) == 1) {int sum = 0;for(int i = 1; i <= n; ++i) {scanf("%d", &a[i]);a[i] /= 1024;sum += a[i]; }memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; ++i) {for(int j = sum/2; j >= a[i]; --j) {dp[j] = max(dp[j], dp[j - a[i]] + a[i]);}}printf("%dn", max(dp[sum/2], sum-dp[sum/2])*1024);}return 0;
} 

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

     思路：小易走到公司最快可以是直接走路，也可以走路 + 出租车。他有n个打车的选择，一旦上车之后，他没必要下车再走路，因为走路会比坐车慢，如果坐车比走路还慢，那么没必要打车，直接走到公司。还有一种情况就是，如果打车点太远，在走到打车点+打车到公司的时间大于直接走到公司的时间，肯定选择直接走到公司。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 50 + 5;
struct node{int x, y;
}pos[maxn];
int main() {int n;int gx, gy;int walk, taxi;scanf("%d", &n);for(int i = 0; i < n; ++i) scanf("%d", &pos[i].x);for(int i = 0; i < n; ++i) scanf("%d", &pos[i].y);scanf("%d%d", &gx, &gy);scanf("%d%d", &walk, &taxi);int ans = abs(gx)*walk + abs(gy)*walk;for(int i = 0; i < n; ++i) {int tol = abs(pos[i].x)*walk + abs(pos[i].y)*walk + abs(pos[i].x-gx)*taxi + abs(pos[i].y-gy)*taxi;ans = min(ans, tol);}printf("%dn", ans);return 0;
} 

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

   思路：很容易知道，男孩要么往左走要么往右走，枚举两种情况模拟即可。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 50 + 5;
char a[maxn], b[maxn];
int main() {scanf("%s", a);memcpy(b, a, sizeof(a));int sta = 0, ans = inf, tol = 0;for(int i = 0; i < strlen(a); ++i) {if(a[i] == 'G') {tol += i - sta;sta++;}}ans = min(ans, tol);sta = tol = 0;for(int i = 0; i < strlen(a); ++i) {if(a[i] == 'B') {tol += i - sta;sta++;}}ans = min(ans, tol);printf("%dn", ans);return 0;
}

     第四题：小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。

    思路：dp[i]表示数字i最后出现的位置，最后根据位置给所有出现的数字排序即可。注意：是按照位置顺序输出的。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 1000 + 5;
int cnt[maxn];
bool cmp(const int a, const int b) {return cnt[a] < cnt[b];
}
int main() {int n;scanf("%d", &n);int x;for(int i = 0; i < n; ++i) {scanf("%d", &x);cnt[x] = i+1;}vector<int>ans;for(int i = 1; i <= 1000; ++i) {if(cnt[i]) ans.push_back(i);}sort(ans.begin(), d(), cmp);for(int i = 0; i < ans.size(); ++i) {if(i == ans.size()-1) printf("%dn", ans[i]);else printf("%d ", ans[i]);}return 0;
}

    第五题：之前写过题解， 魔力手环题解

    第六题：现在有n位工程师和6项工作(编号为0至5)，现在给出每个人能够胜任的工作序号表(用一个字符串表示，比如：045，表示某位工程师能够胜任0号，4号，5号工作)。现在需要进行工作安排，每位工程师只能被安排到自己能够胜任的工作当中去，两位工程师不能安排到同一项工作当中去。如果两种工作安排中有一个人被安排在的工作序号不一样就被视为不同的工作安排，现在需要计算出有多少种不同工作安排计划。

   思路：题意不清，是要求每个工程师都必须要工作得总方案数，数据量很小暴力搜索即可。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 6 + 5;
vector<int>a[maxn];
char s[maxn];
int ans, n;
int vis[maxn];
void dfs(int cnt) { //安排第cnt位工程师 if(cnt == n) {++ans;return;}for(int i = 0; i < a[cnt].size(); ++i) {int work = a[cnt][i];if(!vis[work]) {vis[work] = 1;dfs(cnt+1);vis[work] = 0;}}
}
int main() {ans = 0;scanf("%d", &n);for(int i = 0; i < n; ++i) {scanf("%s", s);for(int j = 0; j < strlen(s); ++j) a[i].push_back(s[j]-'0');}memset(vis, 0, sizeof(vis));dfs(0);printf("%dn", ans);return 0;
} 

     第七题：小易最近在数学课上学习到了集合的概念,集合有三个特征：1.确定性 2.互异性 3.无序性.
小易的老师给了小易这样一个集合：
S = { p/q | w ≤ p ≤ x, y ≤ q ≤ z }
需要根据给定的w，x，y，z,求出集合中一共有多少个元素。小易才学习了集合还解决不了这个复杂的问题,需要你来帮助他。

   思路：用gcd约分+set判重。注意：不要直接相除，可能会因为精度原因得到相同的小数。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 1e4 + 5;
set<PI>s;
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);
}int main() {int w, x, y, z;scanf("%d%d%d%d", &w, &x, &y, &z);for(int i = w; i <= x; ++i)for(int j = y; j <= z; ++j) {int g = gcd(i, j);s.insert(make_pair(i/g, j/g));}printf("%dn", s.size());return 0;
} 

      第八题：常规的表达式求值，我们都会根据计算的优先级来计算。比如*/的优先级就高于+-。但是小易所生活的世界的表达式规则很简单，从左往右依次计算即可，而且小易所在的世界没有除法，意味着表达式中没有/，只有(+,- 和 *)。现在给出一个表达式，需要你帮忙计算出小易所在的世界这个表达式的值为多少。

    思路：仔细读题，直接模拟即可。

AC代码：

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 1e4 + 5;
char s[maxn];
int main() {scanf("%s", s);int ans = s[0]-'0';for(int i = 1; i < strlen(s); i+=2) {if(s[i] == '+') ans += s[i+1]-'0';else if(s[i] == '-') ans -= s[i+1]-'0';else ans *= s[i+1]-'0';}printf("%dn", ans);return 0;
}

     第九题：小易有一块n*n的棋盘，棋盘的每一个格子都为黑色或者白色，小易现在要用他喜欢的红色去涂画棋盘。小易会找出棋盘中某一列中拥有相同颜色的最大的区域去涂画，帮助小易算算他会涂画多少个棋格。

  思路：直接枚举求单列最大连通块。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 50 + 5;
char s[maxn][maxn];
int main() {int n;scanf("%d", &n);for(int i = 0; i < n; ++i) scanf("%s", s[i]);int ans = 0;for(int col = 0; col < n; ++col) {for(int i = 0; i < n; ++i) {int cnt = 1;for(int j = i+1; j < n && s[j][col] == s[i][col]; ++j) {++cnt;}ans = max(cnt, ans);}}printf("%dn", ans);return 0;
}

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

  思路：用set。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 50 + 5;
set<string>s;
int main() {int n, m;cin >> n >> m;string word;for(int i = 0; i < n; ++i) {cin >> word;s.insert(word);}	int score = 0;for(int i = 0; i < m; ++i) {cin >> word;unt(word)) score += word.size()*word.size();}printf("%dn", score);return 0;
}

   第十一题：小易有n块砖块，每一块砖块有一个高度。小易希望利用这些砖块堆砌两座相同高度的塔。为了让问题简单，砖块堆砌就是简单的高度相加，某一块砖只能使用在一座塔中一次。小易现在让能够堆砌出来的两座塔的高度尽量高，小易能否完成呢。

   思路：动态规划好题。dp(i, j)表示考虑前i个砖块，两堆砖块的高度差为j的最大高度。用滚动数组优化下内存，注意下边界。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 5e5 + 5;
int dp[2][maxn]; //滚动数组
int h[55];
int main() {int n;scanf("%d", &n);int sum = 0;for(int i = 1; i <= n; ++i) {scanf("%d", &h[i]);sum += h[i];}memset(dp, -1, sizeof(dp));dp[0][0] = 0; int f = 1;int lim = min(maxn, sum/2);for(int i = 1; i <= n; ++i) {for(int j = 0; j <= lim; ++j) {dp[f][j] = dp[1-f][j];if(j-h[i] <= 0 && dp[1-f][h[i]-j] >= 0) dp[f][j] = max(dp[f][j], dp[1-f][h[i]-j] + j);if(j-h[i] > 0 && dp[1-f][j-h[i]] >= 0) dp[f][j] = max(dp[f][j], dp[1-f][j-h[i]] + h[i]);if(j+h[i] <= lim && dp[1-f][j+h[i]]) dp[f][j] = max(dp[f][j], dp[1-f][j+h[i]]);}f = 1 - f;}if(dp[1-f][0]) printf("%dn", dp[1-f][0]);else printf("-1n");return 0;
}

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

    思路：数位DP。dp[i][j]表示后i个数位对n求余的余数为j的个数，因为189 % n = (100%n + 80%n + 9%n)%n，逐渐往高位求即可，边界d[0][0] = 1.

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int> 
typedef long long LL;
const int maxn = 10000 + 5;
char s[20];
LL dp[2][maxn]; 
int main() {int n;scanf("%s%d", s, &n);int len = strlen(s);memset(dp, 0, sizeof(dp));int f = 1;dp[0][0] = 1;LL sum = 1;for(int i = len-1; i >= 0; --i) {memset(dp[f], 0, sizeof(dp[f]));if(s[i] == 'X') {int st = i == 0 ? 1 : 0;for(int i = st; i <= 9; ++i) {int m = (int)(sum*i%n); //余数 for(int j = 0; j < n; ++j) {dp[f][(j+m)%n] += dp[1-f][j];}}}else {int m = (int)(sum*(s[i]-'0')%n);for(int j = 0; j < n; ++j) {dp[f][(j+m)%n] += dp[1-f][j];}}f = 1 - f;sum *= 10;}printf("%lldn", dp[1-f][0]);return 0;
}

如有不当之处欢迎指出！