网易2019校招笔试编程题参考代码

表达式求值

思路

考虑所有可能的表达式取最大值。

时间复杂度

O(1)

参考代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = a + b + c;
    ans = max(ans, (a + b) * c);
    ans = max(ans, a + b * c);
    ans = max(ans, a * b + c);
    ans = max(ans, a * (b + c));
    ans = max(ans, a * b * c);
    cout << ans << endl;
    return 0;
}

俄罗斯方块

思路

用数组来模拟即可

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n, 0);
    while (m--) {
        int c;
        cin >> c;
        a[--c]++;
    }
    cout << *min_element(a.begin(), a.end()) << endl;
    return 0;
}

丰收

思路

维护前缀和数组之后，二分查找答案。

时间复杂度

O(m*logn)

参考代码

#include <bits/stdc++.h>

using namespace std;

int sum[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);
        sum[i] = sum[i - 1] + a;
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        int d;
        scanf("%d", &d);
        int pos = lower_bound(sum, sum + n + 1, d) - sum;
        printf("%d\n", pos);
    }
    return 0;
}

塔

思路

贪心。每次从最高的塔拿一块放到最低的塔上。

讲道理的话应该spj吧。。。

时间复杂度

O(k*logn)

参考代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {
    int n, k, m = 0;
    cin >> n >> k;
    set<pair<int, int> > s;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s.emplace(x, i);
    }
    vector<pair<int, int> > v;
    while (k && s.size() > 1 && s.rbegin()->first - s.begin()->first > 1) {
        auto a = *s.begin(), b = *s.rbegin();
        s.erase(a), s.erase(b);
        k--;
        a.first++;
        b.first--;
        s.insert(a);
        s.insert(b);
        v.emplace_back(b.second, a.second);
    }
    cout << s.rbegin()->first - s.begin()->first << " " << v.size() << endl;
    for (auto p : v) cout << p.first << " " << p.second << endl;
    return 0;
}

瞌睡

思路

以长度为k的滑动窗口做个dp

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), t(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int now = 0;
    for (int i = 0; i < n; i++)
        cin >> t[i], now += t[i] * a[i];
    int res = now;
    for (int i = 0; i < n;) {
        now += (!t[i]) * a[i];
        if (++i >= k) {
            res = max(res, now);
            now -= (!t[i - k]) * a[i - k];
        }
    }
    cout << res << endl;
    return 0;
}

整理房间

思路

暴力枚举每团杂物4 ^ 4次旋转

时间复杂度

O(256*n)

参考代码

#include <bits/stdc++.h>
using namespace std;

struct point {
    int x, y;
    point(int x = 0, int y = 0) : x(x), y(y) {}
    point operator+(const point &rhs) const {
        return point(x + rhs.x, y + rhs.y);
    }
    point operator-(const point &rhs) const {
        return point(x - rhs.x, y - rhs.y);
    }
    point rotate() { return point(-y, x); }
    point rotate(const point &o) const { return o + (*this - o).rotate(); }
    bool operator==(const point &rhs) const { return x == rhs.x && y == rhs.y; }
};

bool check(const point &a, const point &b) {
    if (a.x == 0 && a.y == 0 || b.x == 0 && b.y == 0) return false;
    if (a.x * a.x + a.y * a.y != b.x * b.x + b.y * b.y) return false;
    if (a.x * b.x + a.y * b.y != 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        point p[4], o[4], a[4];
        for (int i = 0; i < 4; i++)
            scanf("%d %d %d %d", &p[i].x, &p[i].y, &o[i].x, &o[i].y);
        int res = -1;
        int x, y, z, w;
        for (x = 0, a[0] = p[0]; x < 4; x++) {
            for (y = 0, a[1] = p[1]; y < 4; y++) {
                for (z = 0, a[2] = p[2]; z < 4; z++) {
                    for (w = 0, a[3] = p[3]; w < 4; w++) {
                        int cost = x + y + z + w;
                        if (a[0] + a[1] == a[2] + a[3] &&
                                check(a[0] - a[1], a[2] - a[3]) ||
                            a[0] + a[2] == a[1] + a[3] &&
                                check(a[0] - a[2], a[1] - a[3]) ||
                            a[0] + a[3] == a[1] + a[2] &&
                                check(a[0] - a[3], a[1] - a[2])) {
                            if (res == -1 || res > cost) res = cost;
                        }
                        a[3] = a[3].rotate(o[3]);
                    }
                    a[2] = a[2].rotate(o[2]);
                }
                a[1] = a[1].rotate(o[1]);
            }
            a[0] = a[0].rotate(o[0]);
        }
        printf("%d\n", res);
    }
    return 0;
}

小易的字典

思路

贪心。从前往后，对于当前位置是'a'还是'z'可以计算出来。

还是有其他高级一点的做法的(雾

时间复杂度

O(n^2)

参考代码

#include <bits/stdc++.h>

using namespace std; 

int check(int a, int b, long long lim){ 
    long long ret = 1;
    if(b * 2 > a) b = a - b; 
    for(int i = 0; i < b; i++) { 
        ret *= (a - i);
        ret /= (i + 1);
        if(ret >= lim) return -1; 
    } 
    if(ret >= lim) return -1; 
    return (int)ret; 
} 
string solve(int a, int z, int k){ 
    string out = "";
    int n = a + z, i, s; 
    s = check(a + z, a, (long long)k);
    if(s != -1) return out; 
    for(int i = 0; i < n; i++){ 
        if(a == 0 || z == 0) break; 
        s = check(a - 1 + z, a - 1, (long long)k); 
        if(s == -1){ 
            out += 'a';
            a--; 
        } else { 
            k -= s;
            out += 'z';
            z--; 
        } 
    } 
    for(int i = 0; i < a; i++) out += 'a';
    for(int i = 0; i < z; i++) out += 'z'; 
    return out; 
} 
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    string ans = solve(n, m, k);
    if(ans.size() == 0) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}