网易2018校招内推笔试编程题参考代码及思路

练习链接: https://www.nowcoder.com/test/6291726/summary

等差数列

分析

对序列排序,然后比对一下是否等差即可。

参考code

#include <bits/stdc++.h>

using namespace std;

int n;
int x[55];
string solve() {
    sort(x, x + n);
    if(n <= 2) return "Possible";
    else {
        int d = x[1] - x[0];
        bool ok = 1;
        for(int i = 1; ok && i < n; i++) {
            if(d != x[i] - x[i - 1]) return "Impossible";
        }
        return "Possible";
    }
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i];
    cout << solve() << endl;
    return 0;
}

彩色砖块

分析

题目有点唬人。。
设颜色种数为s,那么
if s > 2 ans = 0
else ans = s

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
set<char> S;
int main() {
    cin >> s;
    for(int i = 0; i < s.size(); i++) S.insert(s[i]);
    int ans = S.size();
    if(ans > 2) ans = 0;
    cout << ans << endl;
    return 0;
}

交错01串

分析

就挨着比较,记录当前是交错01串的长度,维护最大值即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

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

独立的小易

分析

首先计算能保证的房屋能租多少天,如果有剩余再考虑购买水果。

参考代码

#include <bits/stdc++.h>

using namespace std;

int x, f, d, p;
int solve(int x, int f, int d, int p) {
    int tmp1 = d / x;
    if(tmp1 <= f) return tmp1;
    d -= f * x;
    return f + d / (x + p);
}
int main() {
    cin >> x >> f >> d >> p;
    cout << solve(x, f, d, p) << endl;
    return 0;
}

堆棋子

分析

对于一个k,我们找一个坐标(x, y)让k个棋子距离这个坐标的曼哈顿距离之和最小。注意到x和y其实是独立的,考虑枚举棋盘上所有可能得坐标(x[i], y[j]),计算这个坐标到所有棋子的距离分别是多少,然后维护k个棋子对于这个坐标最小曼哈顿距离和即可。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int n, x[55], y[55];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i];
    for(int i = 0; i < n; i++) cin >> y[i];
    vector<int> res(n, inf);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                vector<int> res2(n);
                for(int l = 0; l < n; l++) {
                    res2[l] = abs(x[l] - x[j]) + abs(y[l] - y[k]);
                }
                sort(res2.begin(), res2.end());
                int res3 = 0;
                for(int l = 0; l < i + 1; l++) res3 += res2[l];
                res[i] = min(res[i], res3);
            }
        }
    }
    for(int i = 0; i < n; i++) {
        i == 0 ? cout << res[i] : cout << " " << res[i];
    }
    return 0;
}

操作序列

分析

观察每一次操作之后的序列跟之前的关系,可以根据这个直接得到最终的数列。

参考代码

#include <bits/stdc++.h>

using namespace std;


const int maxn = 2e5 + 5;

int a[maxn];
int n;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    if(n % 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 {
        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;
}

疯狂队列

分析

根据样例提示,猜想了一个结论:
我们要把这个队列安排为交错的形式(证明略)。
交错有两种形式,看第一个人是比他相邻的人高还是矮。
以矮的为例:
总共的疯狂值为(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;
}

小易喜欢的数列

分析

想象一下,如果我们确定这个数列的第一个数是i,那么第二个数可以是1到k中除了是i的约数的任何数。
于是我们定义dp[j][i]表示长度为i最后一个数是j的小易喜欢的数列的数量,然后挨着转移即可。。实现请参考参考代码。

参考代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int dp[maxn][15];
int n, k;
int main() {
    cin >> n >> k;
    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;
}