Warning: session_start(): open(/tmp/sess_efeed08b1e129d15c322fe24a28f96f6, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:die_java:weeksummary11 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:die_java:weeksummary11

到此差别页面的链接

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