原文鏈接：算法競賽>力扣>周賽 | 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)$。