常州网站建设方案优化,呼伦贝尔市建设网站,网站开发项目源码,泉州那家做网站公司好前言 整体评价
T4感觉有简单的方法#xff0c;无奈树形DP一条路上走到黑了#xff0c;这场还是有难度的。 T1. 超过阈值的最少操作数 I
思路: 模拟
class Solution {public int minOperations(int[] nums, int k) {return (int)Arrays.stream(nums).filter(x - x …
前言 整体评价
T4感觉有简单的方法无奈树形DP一条路上走到黑了这场还是有难度的。 T1. 超过阈值的最少操作数 I
思路: 模拟
class Solution {public int minOperations(int[] nums, int k) {return (int)Arrays.stream(nums).filter(x - x k).count();}
}T2. 超过阈值的最少操作数 II
思路: 模拟
按题意模拟即可需要注意int溢出问题就行。
class Solution {public int minOperations(int[] nums, int k) {PriorityQueueLong 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;}
}T3. 在带权树网络中统计可连接服务器对数目
思路: 枚举 dfs/bfs 组合数学
因为树的点数n( n ≤ 1000 n\le1000 n≤1000), 所以枚举点从该点进行dfs/bfs然后对每个分支进行组合统计。
组合统计的核心 点 u 出发的各个分支满足整除的数组合序列为 c 0 , c 1 , c 2 , c 3 , . . . , c m 点u出发的各个分支满足整除的数组合序列为 c_0, c_1, c_2, c_3, ..., c_m 点u出发的各个分支满足整除的数组合序列为c0,c1,c2,c3,...,cm 其 s ∑ i 0 i m c i 其 s \sum_{i0}^{im} c_i 其si0∑imci 结果为 r e s [ u ] ( ∑ i 0 i m c i ∗ ( s − c i ) ) / 2 结果为 res[u] (\sum_{i0}^{im} c_i * (s - c_i)) / 2 结果为res[u](i0∑imci∗(s−ci))/2
这样时间复杂度为 O ( n 2 ) O(n^2) O(n2), 是可以接受的。
class Solution {Listint[] []g;int signalSpeed;// fa是阻断点int bfs(int u, int w, int fa) {int res 0;boolean[] vis new boolean[g.length];Dequeint[] 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;ListInteger 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 ≤ 1 0 5 n\le10^5 n≤105, 那该如何解呢 感觉换根 D P 可行但是需要限制 s i g n a l S p e e d 范围在 100 之内 , 这样可控制在 O ( 1 0 7 ) 感觉换根DP可行但是需要限制 signalSpeed 范围在100之内, 这样可控制在O(10^7) 感觉换根DP可行但是需要限制signalSpeed范围在100之内,这样可控制在O(107)
如果signalSpeed很大感觉没辙啊。 T4. 最大节点价值之和
思路: 树形DP
树形DP的解法更加具有通用性所以比赛就沿着这个思路写。 如果操作不是异或那这个思路就更有意义 如果操作不是异或那这个思路就更有意义 如果操作不是异或那这个思路就更有意义
对于任意点u, 其具备两个状态。 d p [ u ] [ 0 ] , d p [ u ] [ 1 ] , 表示参与和没有参与异或下的以 u 为根节点的子树最大和。 dp[u][0], dp[u][1], 表示参与和没有参与异或下的以u为根节点的子树最大和。 dp[u][0],dp[u][1],表示参与和没有参与异或下的以u为根节点的子树最大和。
那么其转移方程其体现在当前节点u和其子节点集合S( v ∈ u 的子节点 v\in u的子节点 v∈u的子节点)的迭代递推转移。
class Solution {int k;int[] nums;ListInteger[]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 次 任意两点u,v可以简单构造一条路径只有端点(u,v)出现1次其他点都出现2次 任意两点u,v可以简单构造一条路径只有端点(u,v)出现1次其他点都出现2次
异或涉及边的两点因此异或的点必然是偶数个这是唯一的限制.
class Solution {public long maximumValueSum(int[] nums, int k, int[][] edges) {long sum 0;PriorityQueueLong 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(keylambda 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写在最后
