双周赛-174

题一和题二都很简单直接秒了，可惜我昨天在看斯诺克，边看边做，就没打算做最后一道困难题了，其实挺简单的。以后尽量双周赛都参加一下，锻炼一下我的辣鸡算法能力。

题三：100918. 交替按位异或分割的数目

题意：给一个数列数组，把他划分为若干个子数列，每个数列的异或和在target1和target2之间轮转。

之前对异或不够熟悉。异或是位运算，相同为0，不同为1，从而有：

自己异或自己为零，即：a ^ a = 0
异或的逆运算是自己，因此：若a ^ b = c则a = c ^ b，即abc任意两个进行异或都等于第三个。

这个题用前缀异或和（类似前缀和）的特性，设置2个dp数组分别是dp1和dp2，表示：
dp1[sum](或dp2[sum])表示分割前缀异或和为sum的序列，分割成满足target1和target2交错，且最后一组的异或值为target1(或target2)的序列组的方法数；

这样之后，当遍历到输入参数nums的下标i时，此时dp1[sum]和dp2[sum]便表示：在下标i之前，分割前缀异或和为sum、且以target1或target2结尾的方法数。
因此状态转移方程，就是将下标i的情况数添加进去，先算出来nums[:i]的前缀异或和，记作pre_sum，本轮只需计算出下标i的情况数并累加到dp1[pre_sum]和dp2[pre_sum]中。

如果nums[:i]划分后，最后一组的前缀异或和是target1，则需要以pre_sum ^ target1为异或和的某个前缀。例如，现在i为5，即num[0:5]，如果num[0:2]的前缀和是pre_sum ^ target1，则xor(nums[2:5])的前缀和必然是target1。dp2[pre_sum ^ target1]可能不仅包含nums[0:2]的情况，还可能有nums[0:3]等等，而他们都满足最后一组的前缀异或和为target2。所以此处其实对下标进行压缩了。

状态转移方程：

1 2	dp1[pre_sum] += dp2[pre_sum ^ target1] dp2[pre_sum] += dp1[pre_sum ^ target2]

再设置一个边界条件，让dp2[0] = 1，即找第一段前缀和为target1的序列时，我们会遍历到pre_sum = target1，此时dp2[pre_sum ^ target1] = dp[0]，令其为1则充当了整个算法的数值起点，否则累加半天全是零；当然也可以设置当pre_sum第一次与target1相等时特殊处理dp2[pre_sum ^ target1]

class Solution:
    def alternatingXOR(self, nums: list[int], target1: int, target2: int) -> int:
        MOD = 1_000_000_007
        f1 = defaultdict(int)
        f2 = defaultdict(int)
        pre_sum = 0
        f2[0] = 1 # 若删去本行，则让行[1]和行[2]代替行[3]
        n = len(nums)
        
        for i, x in enumerate(nums):
            pre_sum ^= x
            # current_last1 = 1 if pre_sum == target1 else 0 # 行[1]
            # current_last1 = (current_last1 + f2[pre_sum ^ target1]) % MOD # 行[2]
            current_last1 = f2[pre_sum ^ target1] % MOD # 行[3]
            current_last2 = f1[pre_sum ^ target2] % MOD
            if i == n - 1:
                return (current_last1 + current_last2) % MOD
            f1[pre_sum] = (f1[pre_sum] + current_last1) % MOD
            f2[pre_sum] = (f2[pre_sum] + current_last2) % MOD
        return 0

题四：100954. 翻转树上最少边

题意：给一个树有n-1个节点，每个节点有个当前bool值和目标布尔值，可以选择一条边，将边的两个端点进行翻转。问最少的翻转方案。

从叶节点开始翻转，因为叶子的翻转情况是确定的。使用后序遍历，即自下而上的顺序，从叶子开始算起。对于每个节点，dfs函数返回它是否需要翻转，当遍历到叶子时，该函数的结果直接是确定的。
如果是非叶子，则考虑它的所有children，每一个需要翻转的children会造成自己翻转一次，自己的值是否和目标值相等也会导致翻转一次，考虑完这些就可以返回了。

class Solution:
    def minimumFlips(self, n: int, edges: List[List[int]], start: str, target: str) -> List[int]:
        out_nodes = collections.defaultdict(list)
        for i, edge in enumerate(edges):
            out_nodes[edge[0]].append((edge[1], i))
            out_nodes[edge[1]].append((edge[0], i))
        ans = []

        # 返回cur是否需要翻转，顺便携带它的father节点
        def dfs(cur: int, father: int):
            # 当下这个节点的值，是否需要翻转
            need_reverse = (start[cur] != target[cur])
            for node, edge_idx in out_nodes[cur]:
                # 遍历往树的叶节点方向遍历
                if node != father and dfs(node, cur):
                    # 如果children需要翻转，则自己也要跟着翻转一次，因此取反
                    ans.append(edge_idx)
                    need_reverse = not need_reverse
            return need_reverse
        
        if dfs(0, -1): # 根节点为0，父亲为-1，如果根节点需要翻转，则不可行。
            return [-1]

        ans.sort() # 排序
        return ans

周赛-486

题一和题二很简单，题二还是花了点时间搞下标的对应；题三是个和最短路径相关的，其实用DFS或BFS就行；题四是组合数学和二进制相关的，目前掌握得还不太行。

题二：3819. 非负元素轮替

可以用Java中Collections类的rotate方法，将非负数取出来进行轮转；再用双指针将非负数弄回原数组。

public int[] rotateElements(int[] nums, int k) {
    List<Integer> nonPos = new ArrayList<>();
    for (int v : nums) {
        if (v >= 0) {
            nonPos.add(v);
        }
    }
    // 库函数的数组旋转，默认是往右
    Collections.rotate(nonPos, -k);

    // 双指针，i指向原数组，j指向旋转后的非负数组
    int i = 0, j = 0;
    while (i < nums.length && j < nonPos.size()) {
        if (nums[i] >= 0) {
            nums[i++] = nonPos.get(j++);
        } else {
            i++;
        }
    }
    return nums;
}

题三：3820. 树上的勾股距离节点

可以用DFS或BFS来求xyz三点到其他所有点的最短路径，下面的代码都涉及到了：
如果是用DFS求，在树形结构中，只需要记录father(fa)节点就行，无需像图中那样使用onPath数组记录已经访问过的点；
如果是用BFS求，由于从队列中取出来时不知道谁是father(你也可以用int[2]把fa一起存到队列中)，可以用个标记数组来判断；

class Solution {
    public int specialNodes(int n, int[][] edges, int x, int y, int z) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            g[u].add(v);
            g[v].add(u);
        }

        // 也可以用this.bfs()
        int[] dx = this.dfs(x, g); 
        int[] dy = this.dfs(y, g);
        int[] dz = this.dfs(z, g);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (this.calc(dx[i], dy[i], dz[i])) {
                ans++;
            }
        }
        return ans;

    }

    int[] bfs(int start, List<Integer>[] g) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] dist = new int[g.length];
        Arrays.fill(dist, -1);
        dist[start] = 0;
        deque.offer(start);
        while (!deque.isEmpty()) {
            int u = deque.poll();
            for (int v : g[u]) {
                if (dist[v] == -1) { // DFS中是通过特判父节点实现的
                    dist[v] = dist[u] + 1;
                    deque.offer(v); // 别忘了加到队列中
                }
            }
        }
        return dist;
    }

    int[] dfs(int start, List<Integer>[] g) {
        int[] dist = new int[g.length];
        Arrays.fill(dist, -1);
        this._dfs(start, g, -1, dist);
        return dist;
    }

    void _dfs(int u, List<Integer>[] g, int fa, int[] dist) {
        dist[u] = fa == -1 ? 0 : dist[fa] + 1;
        for (int v : g[u]) {
            if (v != fa) {
                this._dfs(v, g, u, dist);
            }
        }
    }

    boolean calc(int dx, int dy, int dz) {
        int[] d = new int[]{dx, dy, dz};
        Arrays.sort(d);
        return (long) d[0] * d[0] + (long) d[1] * d[1] == (long) d[2] * d[2];
    }
}