小红书笔试

求时间

给定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;
}