小红书2023/08/06Java后端笔试 AK

T1（模拟、哈希表）

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<string, int> PSI;const int N = 1e5 + 10;void solve() {string line, t;getline(cin, line);line += ' ';vector<PSI> ans;unordered_map<string, int> cnt;for(int i = 0; i < line.size(); i ++) {if(line[i] == ' ') cnt[t] ++ , t = "";else t += line[i];}for(auto kv : cnt) {if(kv.second >= 3) ans.push_back(make_pair(kv.first, kv.second));}sort(ans.begin(), ans.end(), [](PSI& a, PSI& b) {if(a.second != b.second) return a.second > b.second;return a.first < b.first;});for(auto ss : ans) cout << ss.first << endl;}int main() {cin.tie(0); cout.tie(0);std::ios::sync_with_stdio(false);int T = 1;
//	cin >> T;while(T --) {solve();}return 0;
}

T2（01背包）

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 55, M = 510;int n, t_limit, h_limit;
int t[N], h[N], a[N];
LL f[N][M][M];void solve() {cin >> n;cin >> t_limit >> h_limit;for(int i = 1; i <= n; i ++) cin >> t[i] >> h[i] >> a[i];for(int j = t[1]; j < M; j ++) {for(int k = h[1]; k < M; k ++) {f[1][j][k] = a[1];}}for(int i = 2; i <= n; i ++) {for(int j = 1; j <= t_limit; j ++) {for(int k = 1; k <= h_limit; k ++) {f[i][j][k] = max(f[i][j][k], f[i - 1][j][k]);if(j - t[i] < 0 || k - h[i] < 0) continue;f[i][j][k] = max(f[i][j][k], f[i - 1][j - t[i]][k - h[i]] + 0ll + a[i]);}}}LL ans = 0;for(int j = 1; j < M; j ++)for(int k = 1; k < M; k ++)ans = max(ans, f[n][j][k]);cout << ans << endl;
}int main() {cin.tie(0); cout.tie(0);std::ios::sync_with_stdio(false);int T = 1;
//	cin >> T;while(T --) {solve();}return 0;
}

T3（树形DP）

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5 + 10, M = N * 2;int n, v[N];
int h[N], e[M], ne[M], idx;int cnt;
int primes[M];
bool st[M];int f[N][2];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void get_primes(int n) {st[1] = true;for(int i = 2; i <= n; i ++) {if(!st[i]) primes[cnt ++ ] = i;for(int j = 0; primes[j] <= n / i; j ++) {st[primes[j] * i] = true;if(i % primes[j] == 0) break;}}
}int dp(int u, int ban, int p) {int& cur_level = f[u][ban];if(cur_level != -1) return cur_level;cur_level = 0;int rec = 0, miv = M, node_id = -1;for(int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if(j == p) continue;if(!st[v[u] + v[j]]) {if(ban) {cur_level += max(dp(j, 1, u) + 1, dp(j, 0, u));} else {rec += dp(j, 0, u);if(miv > dp(j, 0, u)) {miv = dp(j, 0, u);node_id = j;}}} else {cur_level += max(dp(j, 1, u), dp(j, 0, u));}}if(node_id != -1) cur_level += (rec - miv) + max(dp(node_id, 0, u), dp(node_id, 1, u) + 1);return cur_level;
}void solve() {cin >> n;for(int i = 1; i <= n; i ++) cin >> v[i];memset(f, -1, sizeof f);memset(h, -1, sizeof h);for(int i = 0; i < n - 1; i ++) {int a, b;cin >> a >> b;add(a, b), add(b, a);}cout << max(dp(1, 0, -1), dp(1, 1, -1)) << endl;
}int main() {cin.tie(0); cout.tie(0);std::ios::sync_with_stdio(false);get_primes(200000);int T = 1;
//	cin >> T;while(T --) {solve();}return 0;
}