Jxust weekly consent 1
Done
题目链接
A,B
签到
C
题意
给一个长度为 $n$ 的小写字母字符串，告诉每个字母的最长可以出现在最长子串，问分割方式的数量，所有情况的最长子串，最少分割的子串数量。
题解
- 定义 $dp[i]$ : 以第 $i$ 个字母结尾的方案数。
- 转移：暴力 $n^2 · 26$ 转移即可。
- 最长的子串在所有可以转移的情况求个 $\rm max$ 即可。
- 最少的子串数量在转移的时候记录一下每个串向左延伸的最远位置即可。
D
题意
给出 $n$ 个人名，已知 $m$ 条信息，每条信息告诉两个人名的关系是朋友还是敌人，之间的关系可传递，出现矛盾的信息忽略，现给出 $q$ 条询问，问两个人之间的关系。
题解
典型的带权并查集，比赛的时候写了个假的做法。
正解：
- 实际上带权并查集的题最难处理的就是这种情况，比如先告诉你(1,2)是队友，(3,4)是队友，然后再告诉两个集合之间的关系，其中关系的传递很难解决。
- 回到这个题，由于只给了两种关系，直接对每个点开一个正面一个反面，直接记录关系即可。
E
题意
给一颗 $n$ 个节点的树，每个节点有个权值，两个节点的路径的值定义为路径上所有节点权值的异或值。求所有节点对的值的和。
题解
树形 $dp$
- $xor$ 的问题通常独立考虑二进制的每一位，因为互不干扰，此题也一样。
- 定义: $dp[i][0/1]$：表示节点 $i$ 的儿子到节点 $i$ 的 $0/1$ 的路径数量。
- 转移：考虑节点 $i$ 在所有节点的贡献，那么转移应该有两种，1.节点 $i$ 的儿子到节点i的路径数量。2.节点$i$的父亲转移过来的路径数量。