A. Giao 徽的烤鸭
给定一棵树，边权为 \(1\)。在第 \(i\) 家店办卡花费 \(w_i\) 元。对于任意一家店，如果 Giao 徽在到 \(i\) 的距离小于等于 \(p\) 的所有店办了卡，可得到 \(v_p\) 元的代金券。求最大利润。
\(f_{u,i}\) 表示在以 \(u\) 为根的子树中，到 \(u\) 距离小于等于 \(i\) 的最大利润。
要求父节点第二维 \(\ge i - 1\)，儿子第二维 \(\ge i - 1\)。
\(f_{u,i}+=\max(f_{v,i-1},f_{v,i},f_{v,i+1})\)
初始化 \(f_{u,i}=v_i-w_u\)。
注意考虑不选的情况。
点击查看代码
void dfs(int u, int fa)
{
for(int i = 1; i <= n; ++ i) f[u][i] = b[i - 1] - a[u];
for(int i = head[u], v; i; i = e[i].nex)
{
if((v = e[i].to) == fa) continue; dfs(v, u);
f[u][0] += max(f[v][0], f[v][1]);
for(int j = 1; j <= n; ++ j)
f[u][j] += max(f[v][j - 1], max(f[v][j], f[v][j + 1]));
}
}
B. A Dance of Fire and Ice
有一个数 \(val\)，初始值为 \(1\)。\(n\) 次操作，每次赋值或者 \(val \times x \bmod p\)，\(p\) 是质数。选出任意操作并以任意顺序执行操作。问最终 \(val\) 有多少种可能的取值。
用原根转换成加法，bitset 优化背包就能过了。好像还可以二分哈希，但是我不会。
点击查看代码
f[0] = 1;
for(int i = 1, o, x; i <= n; ++ i)
{
scanf("%lld%lld", &o, &x); x %= mod;
if(!x) ++ ans;
else o == 0 ? f[val[x]] = 1 : vis[val[x]] ++;
}
for(int i = 0; i < mod; ++ i)
{
while(vis[i] --)
{
h = f | (f << i) | (f >> (mod - 1 - i));
if(h == f) break; f = h;
}
}
for(int i = 0; i < mod - 1; ++ i) if(f[i]) ++ ans;
C. 挖掘机技术哪家强
\(n\) 个数，\(a_i=i\)。每次把 \(a_x\) 和 \(a_{x+1}\) 连边，并且交换。问最大团。
暴力 dfs 可得到 60pts。
标签：val,省选,++,2024,int,ge,联测,mod From： https://www.cnblogs.com/Estelle-N/p/17966171