思路: 模擬

class Solution {public int minOperations(int[] nums, int k) {return (int)Arrays.stream(nums).filter(x -> x < k).count();}
}

思路: 模擬

按題意模擬即可，需要注意int溢出問題就行。

class Solution {public int minOperations(int[] nums, int k) {PriorityQueue<Long> pq = new PriorityQueue<>();for (long num : nums) {pq.offer(num);}int ans = 0;while (pq.peek() < k) {long x = pq.poll(), y = pq.poll();pq.offer(Math.min(x, y) * 2 + Math.max(x, y));ans++;}return ans;}
}

思路: 枚舉 + dfs/bfs + 組合數學

因為樹的點數n($n\le 1000$), 所以枚舉點，從該點進行dfs/bfs，然后對每個分支進行組合統計。

組合統計的核心

$$點u出發的各個分支滿足整除的數，組合序列為c_0,c_1,c_2,c_3,...,c_m$$

$$其s=\sum _{i=0}^{i=m}{c}_i$$

$$結果為res[u]=(\sum _{i=0}^{i=m}{c}_i?(s?c_i))/2$$

這樣時間復雜度為 $O(n^2)$, 是可以接受的。

class Solution {List<int[]> []g;int signalSpeed;// fa是阻斷點int bfs(int u, int w, int fa) {int res = 0;boolean[] vis = new boolean[g.length];Deque<int[]> deq = new ArrayDeque<>();vis[u] = true;deq.offer(new int[] {u, w});if (w % signalSpeed == 0) {res ++;}while (!deq.isEmpty()) {int[] cur = deq.poll();int p = cur[0];int v = cur[1];for (int[] e: g[p]) {if (e[0] == fa) continue;if (vis[e[0]]) continue;if ((v + e[1]) % signalSpeed == 0) res++;deq.offer(new int[] {e[0], v + e[1]});vis[e[0]] = true;}}return res;}public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {int n = edges.length + 1;g = new List[n];Arrays.setAll(g, x->new ArrayList<>());this.signalSpeed = signalSpeed;for (int[] e: edges) {g[e[0]].add(new int[] {e[1], e[2]});g[e[1]].add(new int[] {e[0], e[2]});}int[] res = new int[n];for (int i = 0; i < n; i++) {int sum = 0;List<Integer> lists = new ArrayList<>();for (int[] e: g[i]) {int tmp = bfs(e[0], e[1], i);lists.add(tmp);sum += tmp;}int tot = 0;for (int j = 0; j < lists.size(); j++) {tot += lists.get(j) * (sum - lists.get(j));}res[i] = tot / 2;}return res;}}

如果該題把n變成$n\le 10^5$, 那該如何解呢？

$$感覺換根DP可行，但是需要限制signalSpeed范圍在100之內,這樣可控制在O(10^7)$$

如果signalSpeed很大，感覺沒轍啊。

思路: 樹形DP

樹形DP的解法更加具有通用性，所以比賽就沿著這個思路寫。

$$如果操作不是異或，那這個思路就更有意義$$

對于任意點u, 其具備兩個狀態。

$$dp[u][0],dp[u][1],表示參與和沒有參與異或下的以u為根節點的子樹最大和。$$

那么其轉移方程，其體現在當前節點u和其子節點集合S($v\in u的子節點$)的迭代遞推轉移。

class Solution {int k;int[] nums;List<Integer>[]g;long[][] dp;void dfs(int u, int fa) {// 該節點沒參與， 該節點參與了long r0 = nums[u], r1 = Long.MIN_VALUE / 10;for (int v: g[u]) {if (v == fa) continue;dfs(v, u);long uRev0 = r0 + (nums[u]^k) - nums[u];long uRev1 = r1 - (nums[u]^k) + nums[u];long vRev0 = dp[v][0] + (nums[v]^k) - nums[v];long vRev1 = dp[v][1] - (nums[v]^k) + nums[v];long x0 = Math.max(r0 + Math.max(dp[v][0], dp[v][1]),Math.max(uRev1 + vRev1, uRev1 + vRev0));long x1 = Math.max(r1 + Math.max(dp[v][1], dp[v][0]),Math.max(uRev0 + vRev0, uRev0 + vRev1));r0 = x0;r1 = x1;}dp[u][0] = r0;dp[u][1] = r1;}public long maximumValueSum(int[] nums, int k, int[][] edges) {int n = nums.length;this.g = new List[n];this.nums = nums;this.k = k;this.dp = new long[n][2];Arrays.setAll(g, x -> new ArrayList<>());for (int[] e: edges) {g[e[0]].add(e[1]);g[e[1]].add(e[0]);}dfs(0, -1);return Math.max(dp[0][0], dp[0][1]);}
}

class Solution:def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:n = len(nums)g = [[] for _ in range(n)]for e in edges:g[e[0]].append(e[1])g[e[1]].append(e[0])dp = [[0] * 2 for _ in range(n)]def dfs(u, fa):r0, r1 = nums[u], -0x3f3f3f3f3ffor v in g[u]:if v == fa:continuedfs(v, u)uRev0 = r0 + (nums[u]^k) - nums[u];uRev1 = r1 - (nums[u]^k) + nums[u];vRev0 = dp[v][0] + (nums[v]^k) - nums[v];vRev1 = dp[v][1] - (nums[v]^k) + nums[v];t0 = max(r0 + max(dp[v][0], dp[v][1]), max(uRev1 + vRev0, uRev1 + vRev1))t1 = max(r1 + max(dp[v][0], dp[v][1]), max(uRev0 + vRev0, uRev0 + vRev1))r0, r1 = t0, t1dp[u][0], dp[u][1] = r0, r1dfs(0, -1)return max(dp[0][0], dp[0][1])

由于異或的特點，所以這題可以拋棄邊的束縛。

$$任意兩點u,v，可以簡單構造一條路徑，只有端點(u,v)出現1次，其他點都出現2次$$

異或涉及邊的兩點，因此異或的點必然是偶數個，這是唯一的限制.

class Solution {public long maximumValueSum(int[] nums, int k, int[][] edges) {long sum = 0;PriorityQueue<Long> pq = new PriorityQueue<>(Comparator.comparing(x -> -x));for (int v: nums) {pq.offer((long)(v ^ k) - v);sum += v;}while (pq.size() >= 2) {long t1 = pq.poll();long t2 = pq.poll();if (t1 + t2 > 0) {sum += t1 + t2;} else {break;}}return sum;}
}

class Solution:def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:s = sum(nums)arr = [(v ^ k) - v for v in nums]arr.sort(key=lambda x: -x)n = len(nums)for i in range(0, n, 2):if i + 1 < n and arr[i] + arr[i + 1] > 0:s += arr[i] + arr[i + 1]return s