网易2018秋招内推笔试

题目一

问题描述

小易有一个长度为n的整数序列,a_1,…,a_n。然后考虑在一个空序列b上进行n次以下操作:

1、将a_i放入b序列的末尾

2、逆置b序列

小易需要你计算输出操作n次之后的b序列。

输入描述：

输入包括两行,第一行包括一个整数n(2 ≤ n ≤ 2*10^5),即序列的长度。

第二行包括n个整数a_i(1 ≤ a_i ≤ 10^9),即序列a中的每个整数,以空格分割。

输出描述：

在一行中输出操作n次之后的b序列,以空格分割,行末无空格。

分析问题

例子有两种，

个数为奇数：3 (1，2，3)

1，翻转 1，

1，2翻转 2，1

2，1，3翻转 3，1，2

最后的结果是 3，1，2

个数为偶数时，4(1，2，3，4)

3，1，2，4翻转后 4，2，1，3

观察上面的结果

奇数的时候，先写1，然后把2放在1的后面，然后把3放在1的前面(先后面，再前面)

偶数的时候，先写1，然后把2放在1的前面，3放在后面，4放在前面，(先前面，再后面)。

思路：

个数是奇数的时候：奇数放在左边，偶数放在右边

个数是偶数的时候：偶数放在左边，奇数放在右边

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5; //边界问题
int a[maxn];
int n;
int main()
{
   scanf("%d", &n);
   //注意：：从1开始，存储的
   for(int i = 1; i <= n; i++)
       scanf("%d", &a[i]);
   if(n % 2) // 4,2,1,3
   {   //先输出 4 2
       for(int i = n; i >= 1; i -= 2)
           printf("%d ", a[i]);
       //控制输出空格，最后一个没有输出空格
       for(int i = 2; i <= n; i += 2)
           i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
   }
   else //3,1,2
   {
       for(int i = n; i >= 1; i -= 2)
           printf("%d ", a[i]);
       for(int i = 1; i <= n; i += 2)
           i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
   }
   printf("\n");
   return 0;
}

问题二

问题描述

小易现在手里有f个水果和d元，一天要消耗x元房租和1个水果，商店售卖一个水果p元，请问小易能坚持几天。

问题分析

计算1天花多少钱:x+p

先计算能不能活f天，(看d元够不够f天的房租)

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
   int x, f, d, p;//房租，水果个数，钱，水果价钱
   while (cin >> x >> f >> d >> p)
   {
       if (x < 1)
           return -1;
       int onespend = x + p; //一天花费
       //先判断能不能活f天
       int day = d / x;
       if (day <= f)
       {
           cout << day;
           return 0;
       }
       d -= f*x;
       day = f + d / onespend;
       cout << day;
   }
   return 0;
}

问题三

问题描述

疯狂队列，就是给一个数字，要求他们得两两的差值和最大，求这个疯狂值，即：差值。

输入描述：

输入包括两行,第一行一个整数n(1 ≤ n ≤ 50),表示学生的人数

第二行为n个整数h[i](1 ≤ h[i] ≤ 1000),表示每个学生的身高

输出描述：

如样例所示: 5 10 25 40 25

当队列排列顺序是: 25-10-40-5-25, 身高差绝对值的总和为15+30+35+20=100。

这是最大的疯狂值了

分析问题

要想差值最大，先把最大值放上，然后把两个最小值，放在左右两边，

再将两个次大值，放在两个最小值的两边。

根据样例提示,猜想了一个结论:

我们要把这个队列安排为交错的形式(证明略)。

交错有两种形式,看第一个人是比他相邻的人高还是矮。

以矮的为例:

总共的疯狂值为(h2 - h1) + (h2 - h3) + (h4 - h3) + … = -h1 + 2h2 - 2h3 + 2h4 - …,

如果总共是偶数个人,疯狂值为-h1 + 2h2 - 2h3 + 2h4 - … - 2h{n-1} + h{n},所以我们需要从最大的开始依次安排h2,…h{n-2},然后安排h{n},然后继续安排剩下的。

如果总共是奇数个人,疯狂值为-h1 + 2h2 - 2h3 + 2h4 - … + 2h{n-1} - h{n},所以我们需要从最大的开始依次安排h2,…h{n-1},然后安排h1和h{n},然后继续安排剩下的。

然后另外一种形式类似,维护最大的疯狂值即可

代码

#include <bits/stdc++.h>
using namespace std
int h[55];
int n;
int main()
{
   cin >> n;
   for(int i = 0; i < n; i++)
       cin >> h[i];
   sort(h, h + n);
   int tmp, ans = 0, ans1 = 0, ans2 = 0;
   if(n % 2 == 0)
   {
       tmp = n / 2;
       for(int i = 0; i < tmp; i++)
       {
           ans += 2 * (h[tmp + i] - h[i]);
       }
       ans += h[tmp - 1] - h[tmp];
       cout << ans << endl;
       return 0;
   }
   else
   {
       tmp = n / 2;
       for(int i = 0; i < tmp; i++)
       {
           ans1 += 2 * (h[tmp + 1 + i] - h[i]);
           ans2 += 2 * (h[tmp + 1 + i] - h[i]);
       }
       ans1 += -h[tmp] + h[tmp - 1];
       ans2 += h[n] - h[n + 1];
       cout << max(ans1, ans2) << endl;
       return 0;
   }
   return 0;
}

问题四

问题描述

判断数列能否是等差数列，

分析：先排序，然后再比较差值。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[55];
string solve(){
   sort(arr,arr+n);
   if(n < 2)
       return "Possible";
   else{
       int d = arr[1] - arr[0];      
       for(int i = 2; i < n; ++i){
           if(arr[i] - arr[i-1] != d)
               return "Impossible";
       }
   }
   return "Possible";
}
int main(){
   cin >> n;
   for(int i = 0; i < n; i++)
       cin >> arr[i];
   cout << solve() << endl;
}

问题五

s = “ABAB”,那么小易有六种排列的结果:

“AABB”,”ABAB”,”ABBA”,”BAAB”,”BABA”,”BBAA”

其中只有”AABB”和”BBAA”满足最多只有一对不同颜色的相邻砖块。

分析

思路就是看字符串里有几种字符，超过两种就不可能只有一对相邻的不同字符，有两种字符就是两种正确的排列，有一种字符自然就是一种正确的排列。

就是先排序，然后过滤掉重复的，或者直接把字符放在set中，set默认不能插入相同的值。

代码

int main()
{
   string str;
   cin >> str;
   sort(str.begin(), str.end());
   str.erase(unique(str.begin(), str.end()), str.end());
   size_t ans = str.size();
   if (ans > 2)
       ans = 0;
   cout << ans << endl;
   return 0;
}

问题六

问题描述

如果一个01串任意两个相邻位置的字符都是不一样的,我们就叫这个01串为交错01串。例如: “1”,”10101”,”0101010”都是交错01串。

输入包括字符串s,s的长度length(1 ≤ length ≤ 50),字符串中只包含’0’和’1’，求出最大字串是01串的长度。

思路：

就是按个比较字符串，维护最大值。

代码

int main()
{
   string str;
   cin >> str;
   int len = 1, ans = 1;
   for (int i = 1; i < str.size(); ++i)
   {
       if (str[i] != str[i - 1])
           len++;
       else
           len = 1;
   }
   ans = max(ans, len);
   cout << ans << endl;
   return 0;
}

问题七

问题描述

小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.

输入描述：

输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数

第二行为n个棋子的横坐标x[i](1 ≤ x[i] ≤ 10^9)

第三行为n个棋子的纵坐标y[i](1 ≤ y[i] ≤ 10^9)

4

1 2 4 9

1 1 1 1

输出描述：

输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格

0 1 3 10

如样例所示:

对于1个棋子: 不需要操作

对于2个棋子: 将前两个棋子放在(1, 1)中

对于3个棋子: 将前三个棋子放在(2, 1)中

对于4个棋子: 将所有棋子都放在(3, 1)中

暴力枚举，尝试每个节点

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INTMAX = 2147483647;
struct Point
{
   int x = 0;
   int y = 0;
}p[55];
int dis(int x,int y, const Point &b)
{
   return abs(x - b.x) + abs(y - b.y);
}
int main()
{
   int n, i, j;
   cin >> n;
   for (i = 1; i <= n; ++i)
   {
       cin >> p[i].x;
   }
   for (i = 1; i <= n; ++i)
   {
       cin >> p[i].y;
   }
   vector<vector<int>> min_step;
   for (int x = 1; x <= n; ++x)
   {
       for (int y = 1; y <= n; ++y)
       {
           vector<int> tmp;
           for (int k = 1; k <= n; ++k)
           {
               tmp.push_back(dis(p[x].x, p[y].y, p[k]));
           }
           sort(tmp.begin(), tmp.end());
           min_step.push_back(tmp);
       }
   }
   for (i = 1; i <= n; ++i)
   {
       int ans = INTMAX;
       for (j = 0; j < min_step.size(); ++j)
       {
           int temp = 0;
           for (int k = 0; k < i; ++k)
           {
               temp += min_step[j][k];
           }
           ans = min(ans, temp);
       }
       cout << ans;
       if (i != n) cout << " ";
       else cout << endl;
   }
   return 0;
}

问题八

小易非常喜欢拥有以下性质的数列:

1、数列的长度为n

2、数列中的每个数都在1到k之间(包括1和k)

3、对于位置相邻的两个数A和B(A在B前),都满足(A <= B)或(A mod B != 0)(满足其一即可)

例如,当n = 4, k = 7

那么{1,7,7,2},它的长度是4,所有数字也在1到7范围内,并且满足第三条性质,所以小易是喜欢这个数列的

但是小易不喜欢{4,4,4,2}这个数列。小易给出n和k,希望你能帮他求出有多少个是他会喜欢的数列。

分析问题

可以发现长度为4时的数列是当n为3时数列减去不合法的序列。

定义一个全局的数组，记录每个长度的合法数列的和。

dp[ j ][ i ] 表示长度为i，最后一个数是j的小易喜欢的数列的数量,

dp[j][i] += dp[m][i-1] (1<=m<=k),

判断非法的情况，直接判断是约数的情况下，就非法。

代码

const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int dp[maxn][15];
int n, k;
int main()
{
   cin >> n >> k;//n长度
   dp[1][0] = 1;
   for (int i = 1; i <= n; i++)
   {
       int sum = 0;
       for (int j = 1; j <= k; j++)
       {
           sum += dp[j][i - 1];
           sum %= mod;
       }
       for (int j = 1; j <= k; j++)
       {
           int sum2 = 0;//非法的，约数的时候是非法的
           for (int z = j + j; z <= k; z += j)
           {
               sum2 += dp[z][i - 1];
               sum2 %= mod;
           }
           dp[j][i] = (sum - sum2 + mod) % mod;
       }
   }
   int ans = 0;
   for (int j = 1; j <= k; j++)
   {
       ans += dp[j][n];
       ans %= mod;
   }
   cout << ans << endl;
   return 0;
}