网易笔试题（一）

admin 管理员组

文章数量: 1086866

网易笔试题（一）

合唱团

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

输入描述:

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n
个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <=
10, 1 <= d <= 50)

输出描述：

输出一行表示最大的乘积。

分析：
乘积最大，而且数据存在负数，那么就需要存储最大值以及最小值。动态数组dp[i][j]设为以第i个学生结尾的选取j个人的情况。
注意：
1只声明不初始化的时候：
如果申明的是全局/静态数组，系统会把数组的内容自动初始化为0。如果申明的是局部数组，数组的内容会是随机的，不一定0。
2注意声明vector时候，要声明大小N；

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
long long Max1[51][11];
long long Min1[51][11];int main(){int N, K, D;cin>>N;vector <int> a(N);//一定要注意初始化for(int i = 0;i < N;++i) cin>>a[i];cin>>K>>D;for(int i = 0;i < N;++i) Max1[i][0] = Min1[i][0] = a[i];for(int i = 0;i < N;++i){for(int j = 1;j < K;++j){for(int m = i-1;m >= max(0,i-D);--m)  {Max1[i][j] = max(Max1[i][j], max(Max1[m][j-1]*a[i], Min1[m][j-1]*a[i]));Min1[i][j] = min(Min1[i][j], min(Max1[m][j-1]*a[i], Min1[m][j-1]*a[i]));}}}long long  ans = Max1[0][K-1];for(int i=0;i<N;++i) ans = max(ans,Max1[i][K-1]);cout<<ans<<endl;return 0;
}

分田地

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

输入描述：

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 75），表示田地的大小，接下来的 n
行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。

输出描述：

输出一行表示牛牛所能取得的最大的价值。

思路分析：
这题是求最小值的最大值，暴力破解过不了。参考网友们的思路是：用二分法去逼近最终值，假定二分值为mid（假设的最小值），暴力枚举竖切的位置，然后看横切能切多少刀。枚举横切时，当这部分的4个矩形的价值都大于等于mid，说明这一刀切得合理，从这个位置开始继续往下枚举横切。如果最终横切的刀数大于等于4，那么说明这个值mid偏小，否则说明mid偏大。通过这样的不断压缩区间，最终得到最小值得最大值。
注意：
输入数组的时候是连续字符串输入，不带空格，所以先用字符串保留下来。

#include <bits/stdc++.h>
using namespace std;
int a[76][76];
int sum[76][76];
int n,m;
char str[100];int calc(int x, int y, int i, int j){return sum[x][y] - sum[x][j] - sum[i][y] + sum[i][j];
}
bool judge(int x){for(int i = 1; i <= m - 3; i++){for(int j = i + 1; j <= m - 2; j++){for(int k = j + 1; k <= m - 1; k++){int last = 0, cnt = 0;for(int r = 1; r <= n; r++){int s1 = calc(r, i, last, 0);int s2 = calc(r, j, last, i);int s3 = calc(r, k, last, j);int s4 = calc(r, m, last, k);if(s1 >= x && s2 >= x && s3 >= x && s4 >= x){last = r; cnt++;}}if(cnt >= 4)return true;}}}return false;
}
int main(){cin>>n>>m;for(int i = 1; i <= n; i++){scanf("%s", str + 1);//注意输入连续的数字到数组，先输入到字符串for(int j = 1; j <= m; j++){a[i][j] = str[j] - '0';}}for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];}}int l = 0, r = sum[n][m], res = 0;while(l <= r){int m = (l + r) >> 1;if(judge(m)){l = m + 1;res = m;}else r = m - 1;}cout<<res<<endl;return 0;
}

分苹果

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

输入描述:

每个输入包含一个测试用例。每个测试用例的第一行包含一个整数 n（1 <= n <= 100），接下来的一行包含 n 个整数 ai（1 <=
ai <= 100）。

输出描述:

输出一行表示最少需要移动多少次可以平分苹果，如果方案不存在则输出 -1。

分析：不存在的情况有三种：
1）当总和不能均分时；
2）当数据中同时出现了偶数以及奇数时；
3）当所有数为偶数并且总和均分为奇数 or 所有数为奇数并且总和均分为偶数时；
其他情况：循环找比均分值大的数，然后相减除2，累计即可。
问题：写的时候代码一直通过60%，因为以为输出即可检测，而忘了写else。。。

#include <bits/stdc++.h>
using namespace std;
int main() {int num;bool odd = false;bool even = false;cin>>num;vector<int> a(num);int sum = 0;for(int i = 0;i<num;++i) {cin>>a[i];sum += a[i];if(a[i]%2) odd = true;else even = true;}int ave = sum/num;int times = 0;**/*错误写法：if(sum%num) cout<<-1<<endl;if(odd&&even) cout<<-1<<endl;if((odd&&ave%2==0)||(even&&ave%2!=0))      cout<<-1<<endl;int times = 0；for(int i = 0;i<num;++i) {if(a[i]>ave) times += (a[i]-ave)/2;}cout<<times<<endl;*/**if(sum%num) cout<<-1<<endl;else if(odd&&even) cout<<-1<<endl;else if((odd&&ave%2==0)||(even&&ave%2!=0)) cout<<-1<<endl;else{for(int i = 0;i<num;++i) {if(a[i]>ave) times += (a[i]-ave)/2;}cout<<times<<endl;}return 0;
}

藏宝图

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

输入描述:

每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。

输出描述：

输出一行 “Yes” 或者 “No” 表示结果。

思路：用两个指针指向两个字符串，循环判断。
问题：

关于strlen(),sizeof(),size(),length()的区别：
string类型可以用size或者length求字符串长度（不包括’\0’）
string类型不能用strlen()求长度的,strlen只适全char *类型的。
如果一定要用，就用一个c_str()接口来求strlen（str1.c_str()）
sizeof来返回类型以及静态分配的对象、结构或数组所占的空间，返回值跟对象、结构、数组所存储的内容没有关系。

举例如下：

char* ss = "0123456789"; 
sizeof(ss)//结果为4，因为ss是指向字符串常量的字符指针，sizeof 获得的是一个指针的之所占的空间,应该是长整型的，所以是4 
sizeof(*ss) 
//结果为1,*ss是第一个字符 其实就是获得了字符串的第一位'0' 所占的内存空间，是char类型的，占了1位 
strlen(ss)= 10 
// 如果要获得这个字符串的长度,不包括'\0'

#include <bits/stdc++.h>  
#include <string>
#include <algorithm>  
using namespace std;  int main() { string s1,s2;cin>>s1;cin>>s2;int len1 = s1.size();int len2 = s2.size();if(len1<len2) cout<<"No"<<endl;int i = 0, j = 0;while(i < len1&&j < len2){if(s1[i] == s2[j]) {i += 1; j += 1;}else {i+=1;}  }if(j == len2) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

数列还原

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

输入描述:

每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <=1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。

输出描述:

输出一行表示合法的排列数目。

分析：
这道题比较简单，直接暴力计算全排列就可以得到通过。写代码的时候注意局部变量的初始化。用next_permutation和prev_permutation求排列组合，但是要记得包含头文件#include algorithm。next_permutation()会取得（first,last）所标示之序列的下一个排列组合，如果没有下一个排列组合，便返回false;否则返回true。

#include <iostream>
#include <vector>
#include <limits.h>
#include<algorithm>
using namespace std;int cal(vector<int> vec){int res = 0;int len = vec.size();for(int i=0;i<len;++i) {for(int j=i+1;j<len;++j) {if(vec[i]<vec[j]) ++res;}}return res;
}
int main(){int n, k, res = 0;cin>>n>>k;vector<int> a(n);//输入数组vector<int> c1;//不为0元素的值vector<int> c2;//为0元素的值vector<int> i2;//为0元素的位置for(int i=0;i<n;++i){cin>>a[i];if(a[i]!=0) c1.push_back(a[i]);else i2.push_back(i);}for(int i=1;i<=n;++i){if(find(c1.begin(), c1.end(),i) == c1.end()){c2.push_back(i);}}do{vector<int> b = a;for(int i=0;i<c2.size();i++) b[i2[i]] = c2[i];if(cal(b) == k) ++res;}while(next_permutation(c2.begin(),c2.end()));cout<<res<<endl;return 0;
}

本文标签： 网易笔试题（一）