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

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

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

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

  1. 自己异或自己为零，即：a ^ a = 0
  2. 异或的逆运算是自己，因此：若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]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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会造成自己翻转一次，自己的值是否和目标值相等也会导致翻转一次，考虑完这些就可以返回了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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