小红书笔试
求时间
给定7组时间,求出总共有多少分钟
#include <cstdio> #include <iostream> using namespace std; int a[20],b[20]; int main() { int n = 14,res = 0; for (int i = 0; i < n; i ++ ) scanf("%d:%d",&a[i],&b[i]); for (int i = 0; i < n; i += 2) { if (a[i + 1] < a[i]) a[i + 1] += 24; res += a[i + 1] * 60 + b[i + 1] - (a[i] * 60 + b[i]); } cout << res << endl; return 0; }
01背包变种
#include <iostream> using namespace std; const int N = 510; long long dp[N][N]; int t[N],h[N],a[N]; int T,H; int main() { int n; cin >> n; cin >> T >> H; for (int i = 0; i < n; i ++ ) cin >> t[i] >> h[i] >> a[i]; for (int i = 0 ; i < n; i ++ ) { for (int j = T; j >= t[i]; j -- ) { for (int k = H; k >= h[i]; k -- ) { dp[j][k] = max(dp[j][k],dp[j - t[i]][k - h[i]] + a[i]); } } } cout << dp[T][H] << endl; return 0; }
树形dp
给定一颗树,树上有n个节点,编号为[0,n - 1], 每个点上有权值a[i]并且最开始为白色,当相邻的两个点的权值之和为质数并且都为白色,则可以染红其中一个,问最多能染红多少个。
数据量:1 < n < 1e5
思路:
f[i, color] 表示以 i 点为根的子树,且 i 点是 color 色的时候,最多有多少个红点,color 是红色时,就是 sum( f[child, 白]) + 1,
color 是白色时,就是 sum( max( f[child, 白], f[child, 红] ) )。
考场上发现是树形dp了,奈何太久没碰算法没做出来,这里给出课后的代码,不准确,仅提供思路,缺少测试,欢迎大佬指正
#include <iostream> #include <vector> using namespace std; const int N = 100010; int dp[N][2],cnt = 0; int a[N],primes[N * 2]; bool st[N * 2]; vector<int> v[N]; void get_prime(int n) { for (int i = 2; i <= n; i ++ ) { if(!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] * i <= n; j ++ ){ st[primes[j] * i ] = 1; if(i % primes[j] == 0) break; } } } void dfs(int root) { dp[root][1] = 1; for (int i = 0; i < v[root].size(); i ++ ) { int k = v[root][i]; dfs(k); if (st[a[root] + a[k]]) continue; dp[root][0] += max(dp[k][1],dp[k][0]); dp[root][1] += dp[k][0]; } } int main() { int n; cin >> n; get_prime(N * 2); for (int i = 0; i < n; i ++ ) cin >> a[i]; for (int i = 0; i < n - 1; i ++ ) { int x,y; cin >> x >> y; v[y].push_back(x); v[x].push_back(y); } dfs(0); cout << max(dp[0][1],dp[0][0]) << endl; return 0; }#小红书信息集散地##我的实习求职记录##软件开发薪资爆料##你们的毕业论文什么进度了##实习,投递多份简历没人回复怎么办#