date: 2020.07.05 13:00-18:00

practice link

题目大意：给你一棵树，每个结点有一个颜色。要求支持两种操作，一种是将某个结点的子树颜色全改为 $c$，一种是查询某个结点子树中不同颜色的数量。

题解：修改时，将 $u$ 子树中所有子树中的 label 删除，将 $u$ 的 label 设为 $c$。显然，一个结点的颜色是其祖先中离它最近且有 label 的那个。那么就变成了一道带修莫队。时间复杂度 $\mathcal{O}(n^{\frac{5}{3}})$。

标算似乎是 $\mathcal{O}(n\log n)$ 的。

题目大意：给一个串，$n\le3000$，$\Sigma\le70$。问将这个串重排后回文子串数量的最大值，以及达到该数量的重排方案数。

题解：考虑所有回文子串的集合和所有相同字符对的集合。容易注意到前者有一到后者的单射。因而回文子串数量 $\le$ 相同字符对的数量。而当所有相同字符排列在一起时，能取到最大值。

接下来考虑有哪些其它 pattern 也能达到最大值。首先一个字符可以如前所述全部排在一起。除此之外，若一个字符 a 有三个以上，首先它们自己的位置必须成一等差数列，其次相邻两个 a 之间的串都相等，且是回文串。考虑 a***a***a，第一个 a 后的 * 和第二个 a 后的 * 应当相等，这将导致第一个 a 后的第二个 *=a，矛盾。因此相邻 a 之间只能是单个字符，即 ababab... 的模式。对于有两个的字符，还可以包在某个回文串的外部，如 abcbcba。只有一个的字符，要么单独排列，要么被若干有两个的字符包围，如 abcba。

使用 $dp$ 计数。考虑出现次数从大到小转移。设 $dp[i][j][k][u][v]$，表示当前字符出现次数为 $i$，已经使用出现 $i$ 次的字符 $j$ 个，已经使用出现 $i-1$ 次的字符 $k$ 个，有 $u$ 个回文串，$v$ 个非回文串。

• 首先将出现次数为 $1$ 的字符直接算入 $u$ 中，不参与转移，即 $dp[\Sigma+1][0][0][cnt[1]][0]=1$
• $dp[i][j+1][k][u+1][v]+=dp[i][j][k][u][v]$
• $dp[i][j+2][k][u][v+1]+=dp[i][j][k][u][v]*2(cnt[i]-j-1)$
• $dp[i][j+1][k+1][u+1][v]+=dp[i][j][k][u][v]*(cnt[i-1]-k)$
• 这些转移都不难。最后当 $i=2$ 时，要注意记录用来包围 $u$ 的字符
• 最后所有 $u+v$ 可任意排列

其中 $i,j$ 可滚动。时间复杂度 $O(\Sigma^{4})$。

题目大意：给一个点集，不断将其中的点对之间连线段，把交点加入点集。如果最终可有无限的点，称该点集为无限的。给定一个点集，求所有非空有限子集。无重点。

题解：一个点集有限，当且仅当点数 $\le4$ 或存在一条直线上至少有 $3$ 个点，而该直线两侧分别至多有一个点。然后扫描线即可做。

证明自己多画画图即可。