原文链接：算法竞赛>力扣>周赛 | weekly-contest-455

3591.检查元素频次是否为质数

解题思路

统计每个元素出现的次数，判断各次数是否为质数。由于次数<=100，可用试除法判断。

代码实现

bool isPrime(int x) {if (x < 2)return false;for (int i = 2, k = sqrt(x); i <= k; i++)if (x % i == 0)return false;return true;
}bool checkPrimeFrequency(vector<int>& nums) {unordered_map<int, int> mp;for (int v : nums) mp[v]++;for (auto [k,v] : mp)if (isPrime(v))return true;return false;
}

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。

3592.硬币面值还原

解题思路

总金额 i 一定是由小于等于 i 的硬币凑成的。

已给出每种金额的方案数 numWays[i]，如果集合存在，则一定是唯一的。那么，需要做的就是去构造这个集合。

不妨，从小到大考虑每种金额的硬币 i，是否需要硬币 i 呢？

设已考虑的硬币能凑成金额 i 的方案数为 dp[i]，金额 i 的事实方案数为 numWays[i]。

如果 dp[i]＜numWays[i]，那么就需要将硬币 i 考虑进来（再挣扎一下，看能否达到 numWays[i]，实际上金额 i 只会增加一种方案）。

将硬币 i 考虑进来后，需要更新各金额的方案数。

检查 dp[i] 与 numWays[i] 是否相等，如果不相等，说明不存在满足条件的集合。

• 若 dp[i]＜numWays[i]，说明即便是挣扎后依旧无法满足要求。
• 若 dp[i]＞numWays[i]，说明在满足 numWays[1:i-1] 的前提下，金额 i 的方案数已超过 numWays[i]，后续更无法满足要求。

代码实现

vector<int> findCoins(vector<int>& numWays) {int n = numWays.size();vector<int> dp(n + 1, 0), &v = numWays, cs;dp[0] = 1;for (int i = 1; i <= n; i++) {if (v[i - 1] > dp[i]) {cs.push_back(i);for (int j = i; j <= n; j++)dp[j] += dp[j - i];}if (v[i - 1] != dp[i])return {};}return cs;
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

3593.使叶子路径成本相等的最小增量

解题思路

根节点已经固定为节点 0。

最终需要使得根节点到所有叶子节点的成本相等，记这个成本为目标成本，这个目标成本是多少呢？由于每个节点的成本不能减少，所以目标成本应该越小越好，小一点，需要增加成本的节点就可能少一点。由于每个节点的成本不能减少，目标成本不能小于根节点到叶子节点的最大成本。综上，目标成本为根节点到叶子节点的最大成本。换句话说，根节点的目标成本为根节点到叶子节点的最大成本。

最终，对于任意节点 i，其到其各叶子节点的成本均相等，记该成本为预期成本。特别的，根节点的预期成本即为上述目标成本。

成本应该尽可能加在上面的节点，这样可以作用于更多的路径。

对于节点 i，设其预期成本为 tc，节点 i 应该加多少成本呢？应尽可能多加，设加的成本为 ac，其各子节点到叶子节点的成本的最大值为
cc，则需要满足 cost[i]+cc+ac≤tc，故 ac 的最大值为 tc-(cost[i]+cc)。

综上所述，首先计算得到目标成本，再计算得到 cc，最终便可确定 ac，ac 为 0 说明当前节点不需要增加成本。

代码实现

int minIncrease(int n, vector<vector<int>>& edges, vector<int>& cost) {typedef long long ll;int m = edges.size();// 建图vector<int> h(n + 1, -1), e((m << 1) + 1), ne((m << 1) + 1);int idx = 0;auto add = [&](int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;};for (auto v : edges) add(v[0], v[1]), add(v[1], v[0]);// ms[i] 节点i的子节点到叶子节点的距离的最大值vector<ll> ms(n);// 计算每个节点到叶子节点的最大距离function<ll(int, int)> dfs1 = [&](int x, int p) {ll mc = 0;for (int i = h[x]; ~i; i = ne[i]) {if (e[i] == p)continue;mc = max(mc, dfs1(e[i], x));}ms[x] = mc;return cost[x] + mc;};// 根节点到叶子节点的距离的最大值ll mc = dfs1(0, -1);// 应该尽可能地往当前节点加，减轻子孙节点的压力int cnt = 0;function<void(int, int, ll)> dfs2 = [&](int x, int p, ll tc) {if (cost[x] + ms[x] < tc)cnt++;for (int i = h[x]; ~i; i = ne[i]) {if (e[i] == p)continue;dfs2(e[i], x, ms[x]);}};dfs2(0, -1, mc);return cnt;
}

时间复杂度 $O(n)$，空间复杂度 $O(n)$。