8月2日网易笔试8道编程题代码
第一题：有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？
//mx[i][j]表示前i个人选了j个人并且以第i个人为结尾满足相邻位置差不大于d的最大值
//mn[i][j]表示前i个人选了j个人并且以第i个人为结尾满足相邻位置差不大于d的最小值
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110;
const long long inf = 1e16;
long long a[N], mx[N][15], mn[N][15];
int main(){
int n;
while(scanf("%d", &n) > 0){
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
}
int d, m;
scanf("%d%d", &m, &d);
for(int i = 1; i <= n; i++){
mx[i][0] = 1;
mn[i][0] = 1;
for(int j = 1; j <= m; j++){
mx[i][j] = -inf;
mn[i][j] = inf;
}
}
long long mmx = -100, mmn = 100;
long long ans = -inf;
for(int i = 1; i <= n; i++){
mmx = max(mmx, a[i]);
mx[i][1] = a[i];
mn[i][1] = a[i];
if(m == 1)ans = max(ans, mmx);
}
for(int i = 1; i <= n; i++){
for(int j = 2; j <= m && j <= i; j++){
for(int k = i - 1; k >= max(1, i - d) && k >= j - 1; k--){
mx[i][j] = max(mx[i][j], mx[k][j - 1] * a[i]);
mx[i][j] = max(mx[i][j], mn[k][j - 1] * a[i]);
mn[i][j] = min(mn[i][j], mn[k][j - 1] * a[i]);
mn[i][j] = min(mn[i][j], mx[k][j - 1] * a[i]);
if(j == m)ans = max(ans, mx[i][j]);
}
}
}
printf("%lld\n", ans);
}
}
第二题：给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。
//直接从起点开始bfs一遍，到达所有点的最大值即答案
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
int n, m, k, x, y;
char s[N][N];
int dx[N], dy[N], vis[N][N];
struct node{
int x, y, step;
node(){}
node(int x, int y, int step):x(x), y(y), step(step){}
};
bool inside(int i, int j){
return i >= 0 && i < n && j >= 0 && j < m;
}
void bfs(){
memset(vis, 0, sizeof vis);
queue<node>que;
que.push(node(x, y, 0));
vis[x][y] = 1;
int ans = -1;
while(!que.empty()){
node now = que.front();
que.pop();
for(int i = 0; i < k; i++){
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if(!inside(nx, ny))continue;
if(s[nx][ny] == 'X' || vis[nx][ny])continue;
//printf("%d %d\n", nx, ny);
vis[nx][ny] = 1;
que.push(node(nx, ny, now.step + 1));
ans = max(ans, now.step + 1);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!vis[i][j] && s[i][j] == '.')ans = -1;
}
}
printf("%d\n", ans);
}
int main(){
while(scanf("%d%d", &n, &m) > 0){
for(int i = 0; i < n; i++){
scanf("%s", s[i]);
}
scanf("%d%d", &x, &y);
scanf("%d", &k);
for(int i = 0; i < k; i++){
scanf("%d%d", &dx[i], &dy[i]);
}
bfs();
}
}
第三题：牛牛想尝试一些新的料理，每个料理需要一些不同的材料，问完成所有的料理需要准备多少种不同的材料。
#include <cstdio>
#include <iostream>
#include <set>
#include <string>
using namespace std;
set<string>st;
int main(){
string s;
while(cin >> s){
st.insert(s);
}
printf("%d\n", st.size());
}
第四题：牛牛和 15 个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16 份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地， 作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？
//二分答案，判断可行性时暴力枚举三列的情况，然后横着贪心地扫一遍，每当四个都满足时就砍一刀，满足四次即可，复杂度O(N^4logN)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 10010;
char str[100];
int a[110][110];
int sum[110][110], n, m;
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++;
}
// printf("i = %d j = %d k = %d last = %d\n",i, j, k, last);
}
if(cnt >= 4)return true;
}
}
}
return false;
}
int main(){
while(scanf("%d%d", &n, &m) > 0){
for(int i = 1; i <= n; i++){
scanf("%s", str + 1);
for(int j = 1; j <= m; j++){
a[i][j] = str[j] - '0';
}
}
memset(sum, 0, sizeof sum);
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], ans = 0;
while(l <= r){
int m = (l + r) >> 1;
if(judge(m)){
l = m + 1;
ans = m;
}
else r = m - 1;
}
printf("%d\n", ans);
}
}
第五题：n 只奶牛坐在一排，每个奶牛拥有 ai 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平分苹果，如果方案不存在输出 -1。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
int main(){
int n;
while(scanf("%d", &n) > 0){
int sum = 0;
for(int i = 1; i <= n ; i++){
scanf("%d", &a[i]);
sum += a[i];
}
int flag = 0;
if(sum % n != 0)flag = 1;
int avg = sum / n, cnt = 0;
for(int i = 1; i <= n; i++){
if(abs(a[i] - avg) % 2 != 0)flag = 1;
cnt += abs(a[i] - avg) / 2;
}
if(flag)puts("-1");
else printf("%d\n", cnt / 2);
}
}
第六题：航天飞行器是一项复杂而又精密的仪器，飞行器的损耗主要集中在发射和降落的过程，科学家根据实验数据估计，如果在发射过程中，产生了 x 程度的损耗，那么在降落的过程中就会产生 x2 程度的损耗，如果飞船的总损耗超过了它的耐久度，飞行器就会爆炸坠毁。问一艘耐久度为 h 的飞行器，假设在飞行过程中不产生损耗，那么为了保证其可以安全的到达目的地，只考虑整数解，至多发射过程中可以承受多少程度的损耗？
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int a[110];
int main(){
long long n;
while(scanf("%lld", &n) > 0){
long long l = 0, r = sqrt(n * 1.0), ans = 0;
while(l <= r){
long long m = (l + r) >> 1;
if(m * m + m <= n){
l = m + 1;
ans = m;
}
else r = m - 1;
}
cout << ans << endl;
}
}
第七题：牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
char s1[20], s2[20];
while(scanf("%s%s", s1, s2) > 0){
int i = 0, j = 0;
int len1 = strlen(s1), len2 = strlen(s2);
while(i < len1 && j < len2){
if(s1[i] == s2[j]){
i++; j++;
}
else i++;
}
if(j == len2)puts("Yes");
else puts("No");
}
}
第八题：牛牛的作业薄上有一个长度为 n 的排列 A，这个排列包含了从1到n的n个数，但是因为一些原因，其中有一些位置（不超过 10 个）看不清了，但是牛牛记得这个数列顺序对的数量是 k，顺序对是指满足 i < j 且 A[i] < A[j] 的对数，请帮助牛牛计算出，符合这个要求的合法排列的数目。
//因为看不清的位置至多只有10个，直接暴力全排列所有的可能性去判断即可，计算顺序对时可用树状数组O(NlogN)优化一下，不过暴力O(N^2)也能过，都暴力好了。。。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int a[N], b[N], vis[N];
int c[15];
bool judge(int n, int k, int b[]){
int ret = 0;
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
if(b[i] < b[j])ret++;
}
}
//printf("%d %d\n", ret, k);
return ret == k;
}
int main(){
int n, k;
while(scanf("%d%d", &n, &k) > 0){
memset(vis, 0, sizeof vis);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
vis[a[i]] = 1;
}
int tot = 0;
for(int i = 1; i <= n; i++){
if(!vis[i])c[tot++] = i;
}
int index[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int ans = 0;
do{
int idx = 0;
for(int i = 1; i <= n; i++){
if(a[i] == 0)b[i] = c[index[idx++]];
else b[i] = a[i];
// printf("%d ", b[i]);
}
// puts("");
if(judge(n, k, b))ans++;
}while(next_permutation(index, index + tot));
printf("%d\n", ans);
}
}
查看10道真题和解析