后一修订版 | 前一修订版 | ||
2020-2021:teams:die_java:weeksummary11 [2020/08/20 10:59] fyhssgss 创建 |
2020-2021:teams:die_java:weeksummary11 [2020/08/21 16:23] (当前版本) mychael |
||
---|---|---|---|
行 6: | 行 6: | ||
====== 团队训练 ====== | ====== 团队训练 ====== | ||
- | [[front_page_SummerTrain12|2019 Multi-University Training Contest 2]] | + | [[front_page_SummerTrain13|2019 Multi-University Training Contest 2]] |
---- | ---- | ||
====== 每周推荐 ====== | ====== 每周推荐 ====== | ||
- | fyh: | + | **fyh:** |
- | \\ 题目大意:定义一个无根树的权值为所有点的度数的平方的和,求有标号的$n$个点形成的所有森林的权值的和。 | + | \\ **题目大意:**定义一个无根树的权值为所有点的度数的平方的和,求有标号的$n$个点形成的所有森林的权值的和。 |
- | + | \\ **tag:**prufer序列,计数问题 | |
- | \\ tag:prufer序列,计数问题 | + | \\ **做法:**设$f[i]$表示$i$个带标号的节点有多少种不同的森林,递推式为$f[i]=\sum_{j=1}^i C_i^j*f[i-j]*j^{j-2}$。 |
- | \\ 做法:设$f[i]$表示$i$个带标号的节点有多少种不同的森林,递推式为$f[i]=\sum_{j=1}^i C_i^j*f[i-j]*j^{j-2}$。 | + | |
设$w[i]$表示$i$个点能形成的所有无根树的权值和,考虑每一个点以及不同的度数对答案的贡献,递推式子为:$w[i]=i*\sum_{d=1}^{i-1}d^2*C_{n-2}^{d-1}*(n-1)*(n-2-(d-1))$ | 设$w[i]$表示$i$个点能形成的所有无根树的权值和,考虑每一个点以及不同的度数对答案的贡献,递推式子为:$w[i]=i*\sum_{d=1}^{i-1}d^2*C_{n-2}^{d-1}*(n-1)*(n-2-(d-1))$ | ||
那么最终答案$ans[i]$就是$ans[i]=\sum_{j=1}^iC_i^j*(j^{j-2}*ans[i-j]+f[i-j]*w[i])$ | 那么最终答案$ans[i]$就是$ans[i]=\sum_{j=1}^iC_i^j*(j^{j-2}*ans[i-j]+f[i-j]*w[i])$ | ||
- | \\ comment:prufer序列一定要单独讨论N=1,N=2的情况,另外多开longlong取模会导致常数巨大 | + | \\ **comment:**prufer序列一定要单独讨论N=1,N=2的情况,另外多开longlong取模会导致常数巨大 |
+ | |||
+ | **wxg: ** | ||
+ | \\ **题目大意** 给了一个字符串,问你有多少子串,自身是回文串而且一半也是回文串 | ||
+ | \\ **tag: ** 回文自动机 | ||
+ | \\ **做法:** 由回文自动机的性质知道一个串的本质不同的回文串最多有 $n$ 个,我们可以用回文自动机统计不同回文串的个数并标记位置,之后枚举每个串并用哈希判断他的一半是不是回文串就行 | ||
+ | \\ **comment: ** 需要发现本质不同的回文串个数最多为串的长度 | ||
+ | |||
+ | **hxm:** | ||
+ | \\ **题目大意:** 给一棵树,每个点都有一种颜色,设$s(i,j)$为两点之间颜色种类数,求所有点对$s(i,j)$之和 | ||
+ | \\ **tag:** 点分治,差分 | ||
+ | \\ **做法:** | ||
+ | 点分治即可 | ||
+ | |||
+ | 对于每棵分治出来的树,考虑过根的所有路径对树内点的影响 | ||
+ | 首先单独考虑一种颜色的影响,从根节点出发到每棵子树的每个点u,u节点在该颜色下会产生贡献当且仅当u到根的路径上有该颜色的节点 | ||
+ | 所以我们只要找出一个子树中所有颜色为该颜色,且其祖先中没有该颜色【也就是最高的该颜色点】,其子树所有点都会产生贡献,那么所有的对根的贡献就是所有这样点的子树大小之和 | ||
+ | |||
+ | 考虑对子树内的点,就减去该子树的贡献,就转化为和根类似的了 | ||
+ | 每当第一次经过一种颜色的点时,其子树内所有点经过该点必定产生该颜色的贡献,此时把该颜色的贡献改为剩余子树的大小即可 | ||
+ | |||
+ | 还有,根节点的颜色特殊考虑 | ||
- | wxg: | + | 写起来细节真的多 |
- | \\ 题目大意 | + | |
- | \\ tag: | + | |
- | \\ 做法: | + | |
- | \\ comment: | + | |
- | hxm: | + | |
- | \\ 题目大意: | + | |
- | \\ tag: | + | |
- | \\ 做法: | + | |
- | \\ comment: | + | \\ **comment:** 点分治练习 |
---- | ---- | ||
行 39: | 行 51: | ||
====== 傅云濠 ====== | ====== 傅云濠 ====== | ||
- | 比赛:[[https://www.cnblogs.com/FYH-SSGSS/p/13480766.html|Codeforces Round #663 (Div. 2)]] | + | 比赛:educf#93(ABCD),abc175(ABCDE),cfglobal#10(ABCDE),topcoder???(打了个寂寞) |
- | \\ 补第九场J 第十场J | + | \\ 补第七场I,并做了一些有关prufer序列的题 |
- | 整理了树上哈希的板子 | + | 整理了构建prufer序列的板子 |
---- | ---- | ||
====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
- | 补了cf664的部分题 | + | 复习了回文自动机,整理字符串模板 |
---- | ---- | ||
====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
- | 比赛:无 | + | 复习了点分治,整理了点分治模板 |
- | \\ 整理单纯形板子 | + | \\ |