网易互娱笔试第二、三、四题AC代码

第二题

#include <cstdio>
#include <vector>
#include <deque>
using namespace std;

int nodes[1010];
int ls[1010];
int rs[1010];
int T, N, value, left, right;

int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        scanf("%d", &N);
        vector<bool> root(N, true);
        for (int j = 0; j < N; j++) {
            scanf("%d%d%d", &nodes[j], &ls[j], &rs[j]);
            if (ls[j] > -1) root[ls[j]] = false;
            if (rs[j] > -1) root[rs[j]] = false;
        }
        deque<int> q;
        for (int j = 0; j < N; j++) {
            if (root[j]) {
                q.push_back(j);
                break;
            }
        }
        bool result = true;
        long long s = nodes[q.front()];
        while (!q.empty()) {
            int size = q.size();
            long long tmp = 0;
            for (int j = 0; j < size; j++) {
                int rank = q.front();
                q.pop_front();
                if (ls[rank] > -1) {
                    q.push_back(ls[rank]);
                    tmp += nodes[ls[rank]];
                }
                if (rs[rank] > -1) {
                    q.push_back(rs[rank]);
                    tmp += nodes[rs[rank]];
                }
            }
            if (q.size() > 0 && tmp <= s) {
                result = false;
                break;
            }
            s = tmp;
        }
        if (result) printf("YES\n");
        else printf("NO\n");
    }
}

第三题

#include <cstdio>

int T, M, K;
int days[31];
int main() {
    scanf("%d", &T);
    for (int i = 0; i < T; i++) {
        for (int j = 0; j < 31; j++) days[j] = 0;
        scanf("%d%d", &K, &M);
        int num = 0;
        for (int j = 0; j < M; j++) {
            int rank;
            scanf("%d", &rank);
            days[rank] = 1;
            num++;
            int l = rank - 1;
            while (l > 0 && rank - l <= K) days[l--] = 1;
            int r = rank + 1;
            while (r < 31 && r - rank <= K) days[r++] = 1;
        }
        int t = 0;
        for (int j = 1; j <= 30; j++) {
            if (days[j] != 0) t = 0;
            else if (t == 0) {
                t = K;
                num++;
            } else t--;
        }
        printf("%d\n", num);
    }
}

第四题

#include <iostream>
#include <string>
using namespace std;

int T;
int rec[2001][2001];
int M, N;
int A, B, C, D, MX;

int getNum(int a, int b, int c, int d) {
    return rec[c][d] - rec[a-1][d] - rec[c][b-1] + rec[a-1][b-1];
}
int testCross(int i, int j, int k) {
    if (getNum(i, j + k, i + 3*k - 1, j + 2*k-1) != k*k*3) return 0;
    if (getNum(i + k, j, i + 2*k - 1, j + 3*k-1) != k*k*3) return 0;
    if (getNum(i, j, i + 3*k - 1, j + 3*k - 1) != k*k*5) return 0;
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        A = B = C = D = -1;
        MX = 0;
        for (int j = 1; j <= N; j++) {
            string s;
            cin >> s;
            int num = 0;
            for (int q = 0; q < M; q++) {
                if (s[q] == '1') num++;
                rec[j][q+1] = rec[j-1][q+1] + num;
            }
        }
        int upper = min(M, N) / 3;
        while (upper * upper * 5 > rec[N][M]) upper--;
        auto isEmpty = [&](int j, int q, int k) {
            if (j + 3*k - 1 > N) return false;
            if (q + 3*k - 1 > M) return false;
            return getNum(j, q, j + k - 1, q + k - 1) == 0;
        };
        for (int j = 1; j <= N; j++) {
            if (j + 3 * (MX+1) - 1 > N) break;
            if (MX == upper) break;
            for (int q = 1; q <= M; q++) {
                if (MX == upper) break;
                if (q + 3 * (MX+1) - 1 > M) break;
                int l = MX + 1, r = upper;
                if (!isEmpty(j, q, l)) continue;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (isEmpty(j, q, mid)) l = mid + 1;
                    else r = mid - 1;
                }
                int K = l - 1;
                if (K > MX && testCross(j, q, K)) {
                    MX = K;
                    A = j; B = q;
                    C = j + 3 * K - 1; D = q + 3 * K - 1;
                    q += (3*K - 1);
                }
            }
        }
        cout << A << ' ' << B << ' ' << C << ' ' << D << '\n';
    }
}

#笔试题目##网易互娱##题解#