今日头条2018春季校园招聘研发岗位笔试 题解 临时版

前言

算算总分，98分，很难受。。。

临时版的题解都是只会把我的代码发上去，有问题的童鞋们可以留言，我尽力回答=w=

第一题

。。。这题很诡异，我只过了80%的数据，用set写会TLE，用hash写会WA，而且都是80%。。。

TLE版

#include <bits/stdc++.h>
using namespace std;
set<int> st;
set<pair<int, int> > ans;
int main() {
    int n, k, x;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (st.find(x + k) != st.end()) ans.insert(make_pair(x + k, x));
        if (st.find(x - k) != st.end()) ans.insert(make_pair(x - k, x));
        st.insert(x);
    }
    printf("%d\n", ans.size());
    return 0;
}

WA版

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e8 + 5;
const int INF = 1e8;
bool vis[MAX_N];
set<int> st[2];
int main() {
    int n, k, x;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        if (x - k >= 0 && vis[x - k]) st[0].insert(x);
        if (k != 0 && x + k <= INF && vis[x + k]) st[1].insert(x);
        vis[x] = true;
    }
    printf("%d\n", st[0].size() + st[1].size());
    return 0;
}

第二题

简单的广搜就可以，为了保险我加了一个记忆化，不知道不加可不可以。

#include <bits/stdc++.h>
using namespace std;
#define pr make_pair
#define fi first
#define se second
typedef pair<int, int> pii;
set<pii> st;
queue<pair<pii, int> > que;
int main() {
    int n, s, m, v;
    scanf("%d", &n);
    que.push(pr(pr(1, 1), 0));
    st.insert(pr(1, 1));
    while (!que.empty()) {
        s = que.front().fi.fi;
        m = que.front().fi.se;
        v = que.front().se;
        //printf("s = %d, m = %d, v = %d\n", s, m, v);
        que.pop();
        if (s == n) {
            printf("%d\n", v);
            break;
        }
        if (s + s <= n) {
            if (st.find(pr(s + s, s)) == st.end()) {
                que.push(pr(pr(s + s, s), v + 1));
                st.insert(pr(s + s, s));
            }
        }
        if (s + m <= n) {
            if (st.find(pr(s + m, m)) == st.end()) {
                que.push(pr(pr(s + m, m), v + 1));
                st.insert(pr(s + m, m));
            }
        }
    }
    return 0;
}

第三题

大模拟，细节考虑好就行。

由于构成数字的字符串只有四种，我比较讨巧的写了一个数字替代字符串的方法。

#include <bits/stdc++.h>
using namespace std;
string str;
const string ans[4] = {"66666", "6...6", "....6", "6...."};
const int num[5][10] = {{0, 2, 0, 0, 1, 0, 0, 0, 0, 0},
                           {1, 2, 2, 2, 1, 3, 3, 2, 1, 1},
                           {1, 2, 0, 0, 0, 0, 0, 2, 0, 0},
                           {1, 2, 3, 2, 2, 2, 1, 2, 1, 2},
                           {0, 2, 0, 0, 2, 0, 0, 2, 0, 0}};
long long cheng(int &pos, int len) {
    //printf("cheng(%d, %d)\n", pos, len);
    long long res = 0;
    while (pos < len) {
        if (str[pos] == '6') {
            res = res * 10 + 6;
            pos++;
        }
        else if (str[pos] == '+') return res;
        else if (str[pos] == '-') return res;
        else if (str[pos] == '*') {
            pos++;
            res *= cheng(pos, len);
        }
    }
    return res;
}
long long jian(int &pos, int len) {
    //printf("jian(%d, %d)\n", pos, len);
    long long res = 0;
    while (pos < len) {
        if (str[pos] == '6') {
            res = res * 10 + 6;
            pos++;
        }
        else if (str[pos] == '+') {
            return res;
        }
        else if (str[pos] == '-') {
            return res;
        }
        else if (str[pos] == '*') {
            pos++;
            res *= cheng(pos, len);
        }
    }
    return res;
}
long long cal(int &pos, int len) {
    //printf("cal(%d, %d)\n", pos, len);
    long long res = 0;
    while (pos < len) {
        if (str[pos] == '6') {
            res = res * 10 + 6;
            pos++;
        }
        else if (str[pos] == '+') {
            pos++;
            res += cal(pos, len);
        }
        else if (str[pos] == '-') {
            pos++;
            res -= jian(pos, len);
        }
        else if (str[pos] == '*') {
            pos++;
            res *= cheng(pos, len);
        }
    }
    return res;
}
vector<int> v;
int main() {
    int T, pos;
    cin >> T;
    while (T--) {
        pos = 0;
        cin >> str;
        long long result = cal(pos, str.length());
        v.clear();
        if (result == 0) v.push_back(0);
        else while (result) {
            v.push_back(result % 10);
            result /= 10;
        }
        for (int i = 0; i < v.size() / 2; i++) swap(v[i], v[v.size() - 1 - i]);
        for (int j = 0; j < 5; j++) {
            for (int i = 0; i < v.size(); i++) {
                if (i > 0) cout << "..";
                cout << ans[num[j][v[i]]];
            }
            cout << endl;
        }
    }
    return 0;
}

第四题

很明显，先交换较小的数可以让平均数的变化较小。所以贪心即可

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
long long a[MAX_N], b[MAX_N];
set<long long> sta, stb;
int main() {
    int n, m, ans = 0;
    long long suma = 0, sumb = 0, numa, numb;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        sta.insert(a[i]);
        suma += a[i];
    }
    for (int i = 0; i < m; i++) {
        scanf("%lld", &b[i]);
        stb.insert(b[i]);
        sumb += b[i];
    }
    numa = n;
    numb = m;
    sort(a, a + n);
    sort(b, b + m);
    for (int ai = 0, bi = 0; ai < n || bi < m; ) {
        if (ai == n) {
            if (sta.find(b[bi]) == sta.end() && numb > 0) {
                if ((suma + b[bi]) * numa > suma * (numa + 1)) {
                    if ((sumb - b[bi]) * numb > sumb * (numb - 1)) {
                        numa++;
                        suma += b[bi];
                        numb--;
                        sumb -= b[bi];
                        ans++;
                    }
                }
            }
            bi++;
        }
        else if (bi == m) {
            if (stb.find(a[ai]) == stb.end() && numa > 0) {
                if ((sumb + a[ai]) * numb > sumb * (numb + 1)) {
                    if ((suma - a[ai]) * numa > suma * (numa - 1)) {
                        numa--;
                        suma -= a[ai];
                        numb++;
                        sumb += a[ai];
                        ans++;
                    }
                }
            }
            ai++;
        }
        else if (a[ai] > b[bi]) {
            if (sta.find(b[bi]) == sta.end() && numb > 0) {
                if ((suma + b[bi]) * numa > suma * (numa + 1)) {
                    if ((sumb - b[bi]) * numb > sumb * (numb - 1)) {
                        numa++;
                        suma += b[bi];
                        numb--;
                        sumb -= b[bi];
                        ans++;
                    }
                }
            }
            bi++;
        }
        else if (a[ai] < b[bi]) {
            if (stb.find(a[ai]) == stb.end() && numa > 0) {
                if ((sumb + a[ai]) * numb > sumb * (numb + 1)) {
                    if ((suma - a[ai]) * numa > suma * (numa - 1)) {
                        numa--;
                        suma -= a[ai];
                        numb++;
                        sumb += a[ai];
                        ans++;
                    }
                }
            }
            ai++;
        }
        else {
            ai++;
            bi++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

第五题

鉴于每次可以跳的范围是2H，所以我们每次弹跳二分的找到所有可跳的位置就行，然后就可以广搜了。

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5;
bool vis[MAX_N * 2];
int n, T[MAX_N];
queue<int> que;
int erfen_big(int x) {
    int L = 0, R = n - 1, ans = n - 1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (T[mid] >= x) {
            ans = mid;
            R = mid - 1;
        }
        else {
            L = mid + 1;
        }
    }
    return ans;
}
int erfen_small(int x) {
    int L = 0, R = n - 1, ans = 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (T[mid] <= x) {
            ans = mid;
            L = mid + 1;
        }
        else {
            R = mid - 1;
        }
    }
    return ans;
}
int main() {
    int k, h, ans = 0;
    scanf("%d%d%d", &n, &k, &h);
    for (int i = 0; i < n; i++) {
        scanf("%d", &T[i]);
    }
    sort(T, T + n);
    que.push(0);
    vis[0] = true;
    while (!que.empty()) {
        int x = que.front(); que.pop();
        ans = max(ans, x);
        int L = erfen_big(x - h), R = erfen_small(x + h);
        //printf("x = %d, L = %d, R = %d\n", x, L, R);
        for (int i = L; i <= R; i++) {
            int y = 2 * T[i] - x;
            if (y <= 0) continue;
            if (vis[y]) continue;
            que.push(y);
            vis[y] = true;
        }
    }
    printf("%d\n", ans);
    return 0;
}