2020.08.08 网易秋招算法岗笔试
每个人的题目可能是不一样的。
T1：把数组里的数拆成素数，要求统计数组中所有数的素数个数和。
贪心拆成2然后统计即可，注意1E6个数，每个数最大为1E9，答案会爆int.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;
const int maxn = 1001000;
int n;
int a[maxn];
signed main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
while (~scanf("%d", &n)) {
LL tot = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
tot += a[i] / 2;
}
printf("%lld\n", tot);
}
return 0;
}
T2：n个人排队操作，每个人花费时间为ai，也可以第i个人和前一个人一起操作花费时间为bi，问最少花费时间并且转成要求格式。
DP，f(i,j)维护到第i个人按照j操作时的总最少花费，转移看代码；转换格式感觉数据弱了，不表了。
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;
const int maxn = 2020;
int n;
int a[maxn], b[maxn];
int f[maxn][2];
void gao(int second) {
int minute = second / 60;
second %= 60;
int hour = minute / 60;
minute %= 60;
hour += 8;
string suf = (hour <= 12 ? "am" : "pm");
if (hour > 12) hour -= 12;
printf("%02d:%02d:%02d %s\n", hour, minute, second, suf.c_str());
}
signed main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
memset(f, 0x7f, sizeof f);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 2; i <= n; i++) {
scanf("%d", &b[i]);
}
f[0][0] = f[0][1] = 0;
f[1][0] = f[1][1] = a[1];
for (int i = 2; i <= n; i++) {
f[i][0] = min({f[i][0], f[i - 1][0] + a[i], f[i - 1][1] + a[i]});
f[i][1] = min({f[i][1], f[i - 2][0] + b[i], f[i - 2][1] + b[i]});
}
gao(min(f[n][0], f[n][1]));
}
return 0;
}
T3：n个数字，扔掉任意个，然后再把剩下的数拆成两组和相同的数，问扔掉数字的最小和。
爆搜3^n
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pii = pair<LL, LL>;
const int maxn = 16;
int n;
int a[maxn];
int ret = INT_MAX;
void dfs(int id, int l, int r, int drop) {
if (id == n + 1) {
if (l == r) {
ret = min(ret, drop);
}
return;
}
dfs(id + 1, l + a[id], r, drop);
dfs(id + 1, l, r + a[id], drop);
dfs(id + 1, l, r, drop + a[id]);
}
signed main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
ret = INT_MAX;
dfs(1, 0, 0, 0);
printf("%d\n", ret);
}
return 0;
}
T4：题意翻译一下就是给一个有向图，问有多少点对可以互相可达。
tarjan求强连通分量，缩点后统计每个强连通分量中的点数，答案就是sum((k-1)*k/2)，k为每个强连通分量中的点数，注意开LL.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int maxn = 50050;
const int maxm = 600600;
typedef struct Edge {
int u;
int v;
int next;
Edge() { next = -1; }
}Edge;
int head[maxn], ecnt;
Edge edge[maxm];
int n, m;
int bcnt, dindex;
int dfn[maxn], low[maxn];
int stk[maxn], top;
int belong[maxn];
int in[maxn], out[maxn];
bool instk[maxn];
void init() {
memset(edge, 0, sizeof(edge));
memset(head, -1, sizeof(head));
memset(instk, 0, sizeof(instk));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(belong, 0, sizeof(belong));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
ecnt = top = bcnt = dindex = 0;
}
void adde(int uu, int vv) {
edge[ecnt].u = uu;
edge[ecnt].v = vv;
edge[ecnt].next = head[uu];
head[uu] = ecnt++;
}
void tarjan(int u) {
int v = u;
dfn[u] = low[u] = ++dindex;
stk[++top] = u;
instk[u] = 1;
for(int i = head[u]; ~i; i=edge[i].next) {
v = edge[i].v;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instk[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
bcnt++;
do {
v = stk[top--];
instk[v] = 0;
belong[v] = bcnt;
} while(v != u);
}
}
int main() {
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
int uu, vv;
while(~scanf("%d %d", &n, &m)) {
init();
for (int i = 1; i <= m; i++) {
scanf("%d %d", &uu, &vv);
if (uu == vv) continue;
adde(uu, vv);
}
for(uu = 1; uu <= n; uu++) {
if(!dfn[uu]) {
tarjan(uu);
}
}
for(int i = 0; i < ecnt; i++) {
if(belong[edge[i].u] != belong[edge[i].v]) {
in[belong[edge[i].u]]++;
out[belong[edge[i].v]]++;
}
}
unordered_map<int, int> vis;
for (int i = 1; i <= n; i++) {
vis[belong[i]]++;
}
LL ret = 0;
for (const auto x : vis) {
LL cnt = x.second;
ret += (cnt - 1) * cnt / 2;
}
printf("%lld\n", ret);
}
return 0;
}
