一、3512. 使數組和能被 K 整除的最少操作次數

題目鏈接

本題實際上求的就是數組 nums 和的余數，代碼如下：

class Solution {public int minOperations(int[] nums, int k) {int s = 0;for(int x : nums){s += x;}return s % k;}
}

二、3513. 不同 XOR 三元組的數目 I

題目鏈接

本題給出的數組 nums 包含 [1,n] 中的所有數，問選 3 個時可以得到的所有異或值，分情況討論：

• n = 1，只能與自己異或，答案為 {1}
• n = 2，必有兩個相同值異或（a^a=0），然后再與 1/2 異或，答案為 {1,2}
• n > 2:
  • 1 ^ 2 ^ 3 = 0，所以可以取到 0
  • a ^ a ^ a = a，所以可以得到 [1,n]
  • 對于大于 n 的值，可以使用構造的方式來獲得，比如說 1101，可以通過 {1000,100,1} 獲得；1100 可以通過 {1000,101,1} 獲得；得到一般公式，對于 [n+1，$2^l$-1] 中任意一個數 a 來說，它可以通過 {$2^{l?1}$，a ^ 1 ^ $2^{l?1}$，1} 獲得。
  • 特殊情況，a = $2^{l?1}$ + 1（即1001，100001 這種情況），無法使用上述公式得到，這里特殊處理，可以使用 {$2^{l?1}$，2，3} 得到

代碼如下：

class Solution {public int uniqueXorTriplets(int[] nums) {int n = nums.length;if(n == 1) return 1;if(n == 2) return 2;// [1, n] 選 3 個數for(int i = 31; i >= 0; i--){if((n >> i & 1) == 1){return 1 << (i + 1);}}return -1;}
}

三、3514. 不同 XOR 三元組的數目 II

題目鏈接

本題數據范圍小，可以使用 O($n^2$) 的時間復雜度解決，先處理出 nums數組 中兩個數的異或值，然后拿該異或值再與 nums 數組異或。代碼如下：

class Solution {public int uniqueXorTriplets(int[] nums) {int mx = 0;for(int x : nums){mx = Math.max(mx, x);}int u = 1 << (32 - Integer.numberOfLeadingZeros(mx));// 這里不要使用 set 來存儲，會超時boolean[] has = new boolean[u];for(int i = 0; i < nums.length; i++){for(int j = i; j < nums.length; j++){has[nums[i] ^ nums[j]] = true;}}boolean[] has1 = new boolean[u];for(int i = 0; i < u; i++){if(!has[i]) continue;for(int x : nums){has1[i ^ x] = true;}}int ans = 0;for(boolean x : has1){if(x) ans++;}return ans;}
}

四、3515. 帶權樹中的最短路徑

題目鏈接

本題的難點在于怎么知道更新的(u,v)之間的邊權會影響根節點到哪些點的路徑距離，由于本題是一個樹，所以影響的肯定是(u,v)的所有子節點，那么問題變成了如何維護一個節點的所有子節點？這里可以使用 dfs時間戳 來維護：

• dfs時間戳就是通過先序遍歷，對于每個節點 x，記錄進入 x 節點的時間in[x]以及出該節點的時間out[x]，如果其他節點的[in[y], out[y]] 在[in[x],out[x]] 中，說明 y 是 x 的子節點。

此時，對于 (u,v) 之間邊權的更新，就可以轉換成 [in[v], out[v]] 區間的更新（u 是 v 的父節點），可以使用差分的思想來做，由于數據最多只能支持 O(nlogn) 的時間復雜度，所以需要一個 logn 查詢/修改的數據結構來維護，可以選擇線段樹/樹狀數組，這里使用樹狀數組。

代碼如下：

class Solution {// 樹狀數組模板static class FenwickTree{int[] tree;public FenwickTree(int n){tree = new int[n + 1];}public void update(int i, int val){while(i < tree.length){tree[i] += val;i += i & -i;}}public int pre(int i){int res = 0;while(i > 0){res += tree[i];i -= i & -i;}return res;}}// 根據進出時間來記錄每次修改干涉的路徑// 根據{進出時間+差分}來修改/得到最短路徑public int[] treeQueries(int n, int[][] edges, int[][] queries) {List<Integer>[] g = new ArrayList[n+1];Arrays.setAll(g, e->new ArrayList<>());for(int[] e : edges){int u = e[0];int v = e[1];g[u].add(v);g[v].add(u);}in = new int[n+1];out = new int[n+1];dfs(1, -1, g);weight = new int[n+1];// 記錄邊權FenwickTree t = new FenwickTree(n);for(int[] e : edges){update(e[0], e[1], e[2], t);}List<Integer> ans = new ArrayList<>();for(int[] q : queries){if(q[0] == 1){update(q[1], q[2], q[3], t);}else{ans.add(t.pre(in[q[1]]));}}return ans.stream().mapToInt(i -> i).toArray();}int clock = 0;int[] in;int[] out;int[] weight;void dfs(int x, int fa, List<Integer>[] g){in[x] = ++clock;for(int y : g[x]){if(y == fa) continue;dfs(y, x, g);}out[x] = clock;}void update(int x, int y, int w, FenwickTree t){if(in[x] > in[y]){y = x;}int d = w - weight[y];weight[y] = w;t.update(in[y], d);t.update(out[y]+1, -d);}
}