前言
整体评价
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) { PriorityQueue 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_{i=0}^{i=m} c_i 其s=i=0∑i=mci
结果为 r e s [ u ] = ( ∑ i = 0 i = m c i ∗ ( s − c i ) ) / 2 结果为 res[u] = (\sum_{i=0}^{i=m} c_i * (s - c_i)) / 2 结果为res[u]=(i=0∑i=mci∗(s−ci))/2
这样时间复杂度为 O ( n 2 ) O(n^2) O(n2), 是可以接受的。
class Solution { List []g;
int signalSpeed;
// fa是阻断点
int bfs(int u, int w, int fa) { int res = 0;
boolean[] vis = new boolean[g.length];
Deque 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 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;
List[]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], -0x3f3f3f3f3f
for v in g[u]:
if v == fa:
continue
dfs(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, t1
dp[u][0], dp[u][1] = r0, r1
dfs(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;
PriorityQueue 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