网易互娱笔试第二、三、四题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';
}
} #笔试题目##网易互娱##题解#
