2020-2021:teams:die_java:weeksummary11
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:weeksummary11 [2020/08/20 11:03] fyhssgss [每周推荐] |
2020-2021:teams:die_java:weeksummary11 [2020/08/21 16:23] (当前版本) mychael |
||
|---|---|---|---|
| 行 22: | 行 22: | ||
| **wxg: ** | **wxg: ** | ||
| - | \\ **题目大意** | + | \\ **题目大意** 给了一个字符串，问你有多少子串，自身是回文串而且一半也是回文串 |
| - | \\ **tag: ** | + | \\ **tag: ** 回文自动机 |
| - | \\ **做法:** | + | \\ **做法:** 由回文自动机的性质知道一个串的本质不同的回文串最多有 $n$ 个，我们可以用回文自动机统计不同回文串的个数并标记位置，之后枚举每个串并用哈希判断他的一半是不是回文串就行 |
| - | \\ **comment: ** | + | \\ **comment: ** 需要发现本质不同的回文串个数最多为串的长度 |
| **hxm:** | **hxm:** | ||
| - | \\ **题目大意：** | + | \\ **题目大意：** 给一棵树，每个点都有一种颜色，设$s(i,j)$为两点之间颜色种类数，求所有点对$s(i,j)$之和 |
| - | \\ **tag:** | + | \\ **tag:** 点分治，差分 |
| \\ **做法:** | \\ **做法:** | ||
| + | 点分治即可 | ||
| - | \\ **comment:** | + | 对于每棵分治出来的树，考虑过根的所有路径对树内点的影响 |
| + | 首先单独考虑一种颜色的影响，从根节点出发到每棵子树的每个点u，u节点在该颜色下会产生贡献当且仅当u到根的路径上有该颜色的节点 | ||
| + | 所以我们只要找出一个子树中所有颜色为该颜色，且其祖先中没有该颜色【也就是最高的该颜色点】，其子树所有点都会产生贡献，那么所有的对根的贡献就是所有这样点的子树大小之和 | ||
| + | |||
| + | 考虑对子树内的点，就减去该子树的贡献，就转化为和根类似的了 | ||
| + | 每当第一次经过一种颜色的点时，其子树内所有点经过该点必定产生该颜色的贡献，此时把该颜色的贡献改为剩余子树的大小即可 | ||
| + | |||
| + | 还有，根节点的颜色特殊考虑 | ||
| + | |||
| + | 写起来细节真的多 | ||
| + | |||
| + | \\ **comment:** 点分治练习 | ||
| ---- | ---- | ||
| 行 44: | 行 57: | ||
| ====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
| + | 复习了回文自动机，整理字符串模板 | ||
| ---- | ---- | ||
| ====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
| - | 比赛： | + | 复习了点分治，整理了点分治模板 |
| \\ | \\ | ||
2020-2021/teams/die_java/weeksummary11.1597892630.txt.gz · 最后更改: 2020/08/20 11:03 由 fyhssgss
