20200808 网易秋招笔试题
总结：这一场笔试题比较无脑。。。
1. 第一题除2累加，100%；
2. 第二题 dp or 递推，100%；
3. 第3题二进制暴力枚举状态，100%；
4. 第4题 套 tarjar 有向图强连通分量 的模板，100%；或者 O(n^3) 的 floyd 也能骗50% ......
2. 第二题 dp or 递推，100%；
3. 第3题二进制暴力枚举状态，100%；
4. 第4题 套 tarjar 有向图强连通分量 的模板，100%；或者 O(n^3) 的 floyd 也能骗50% ......
第一题（100%）
#include <bits/stdc++.h>
using namespace std;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 1000005;
int n, A[MAXN];
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-1.txt", "r", stdin);
#endif // __LOCAL_WONZY__
scanf("%d", &n);
long long ans = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", &A[i]);
ans += A[i] / 2;
}
printf("%lld\n", ans);
return 0;
} 第二题（100%）
#include <bits/stdc++.h>
using namespace std;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 2005;
int T, n, A[MAXN], B[MAXN];
int dp[MAXN];
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-2.txt", "r", stdin);
#endif // __LOCAL_WONZY__
cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> A[i];
}
for (int i = 1; i < n; ++i) {
cin >> B[i];
}
dp[0] = A[0];
dp[1] = min(dp[0] + A[1], B[1]);
for (int i = 2; i < n; ++i) {
dp[i] = min(dp[i - 1] + A[i], dp[i - 2] + B[i]);
}
int hour = dp[n - 1] / 3600;
int minute = (dp[n - 1] - hour * 3600) / 60;
int second = dp[n - 1] - hour * 3600 - minute * 60;
hour += 8;
bool is_am = hour <= 12;
hour = is_am ? hour : hour - 12;
printf("%02d:%02d:%02d %s\n", hour, minute, second, is_am ? "am" : "pm");
}
return 0;
} 第三题（100%）
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 20;
int T, n, A[MAXN];
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-3.txt", "r", stdin);
#endif // __LOCAL_WONZY__
cin >> T;
while (T--) {
cin >> n;
int sum = 0;
for (int i = 0; i < n; ++i) {
cin >> A[i];
sum += A[i];
}
int ans = sum;
for (int f = (1 << n) - 1; f >= 0; --f) {
int sum_a = 0;
vector<int> buf;
for (int i = 0; i < n; ++i) {
if ((f >> i) & 1)
sum_a += A[i];
else
buf.push_back(A[i]);
}
if (sum - 2 * sum_a >= ans) continue;
if (sum_a * 2 > sum) continue;
int m = buf.size();
// if (m > n - m) continue;
bool okay = false;
for (int g = (1 << m) - 1; g >= 0; --g) {
int sum_b = 0;
for (int j = 0; j < m; ++j) {
if ((g >> j) & 1) sum_b += buf[j];
}
if (sum_a == sum_b) {
okay = true;
break;
}
}
if (okay) ans = min(ans, sum - 2 * sum_a);
}
cout << ans << endl;
}
return 0;
} 补充一下，第三题暴力应该是很科学的。数学上的复杂度我就不算的，暴力打出来最多计算量也就1e8左右。
// 求计算量的代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 15;
int comp_cnt = 0;
for (int f = (1 << n) - 1; f >= 0; --f) {
int bits_cnt1 = __builtin_popcount(f);
int bits_cnt2 = n - bits_cnt1;
comp_cnt += (1<<bits_cnt2) * bits_cnt2;
}
cout << comp_cnt << endl;
return 0;
} 第四题（100%）
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const long long infl = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 50005;
int n, m;
vector<int> edges[MAXN];
int low[MAXN], dfn[MAXN], stk[MAXN], belong[MAXN], num[MAXN];
int idx, top, scc;
bool in_stk[MAXN];
void tarjar(int u) {
low[u] = dfn[u] = ++idx;
stk[top++] = u;
in_stk[u] = true;
for (auto& v : edges[u]) {
if (!dfn[v]) {
tarjar(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v] && low[u] > dfn[v]) {
low[u] = dfn[v];
}
}
if (low[u] == dfn[u]) {
++scc;
int v = -1;
do {
v = stk[--top];
in_stk[v] = false;
belong[v] = scc;
++num[scc];
} while (v != u);
}
}
int main() {
#ifdef __LOCAL_WONZY__
freopen("input-4.txt", "r", stdin);
#endif // __LOCAL_WONZY__
cin >> n >> m;
memset(dfn, 0, sizeof(dfn));
memset(num, 0, sizeof(num));
memset(in_stk, 0, sizeof(in_stk));
for (int i = 1; i <= n; ++i) edges[i].clear();
idx = scc = top = 0;
int u, v;
for (int i = 1; i <= m; ++i) {
cin >> u >> v;
edges[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) tarjar(i);
}
long long ans = 0;
for (int i = 1; i <= scc; ++i) {
ans += (long long) (num[i] - 1) * num[i] / 2;
}
cout << ans << endl;
return 0;
} 
小米三面62人在聊