https://wiki.cvbbacm.com/ 2026-04-30T01:03:39+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-09-23T16:03:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E5%B9%B6%E6%9F%A5%E9%9B%86&rev=1600848219&do=diff MAIN 暴力维护启发式合并信息，集合大小、父亲关系 查询模拟启发式合并过程跳转父亲，时间复杂度 $O(\log^2n)$，空间复杂度 $O(n\log n)$ text/html 2020-10-10T22:31:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:%E5%AD%97%E7%AC%A6%E4%B8%B2&rev=1602340298&do=diff Manacher 原串插入特殊字符，长度变为 $2\times n+1$。 记录当前最右回文边界 $r$ 以及对应中心点 $c$，第 $i$ 个中心点以对称点长度为起始点出发暴力匹配，可证 $r$ 单调递增或 $O(1)$ 直接得到答案。 最终最长回文串长度为 $\max_{0\leq i<len}{p_i-1}$$O(n)$ text/html 2020-07-24T17:10:30+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:2020_07_11--2020_07_17_%E5%91%A8%E6%8A%A5&rev=1595581830&do=diff 404 text/html 2020-07-24T17:12:42+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:2020_07_18--2020_07_24_%E5%91%A8%E6%8A%A5&rev=1595581962&do=diff 7.18 牛客三 abce 7.19 牛客三 g 7.20 牛客四 bh 7.21 无 7.22 百度之星初赛一 67 7.23 加训 g|i 7.24 无 text/html 2020-07-31T14:12:21+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:2020_07_25--2020_07_31_%E5%91%A8%E6%8A%A5&rev=1596175941&do=diff 7.25 牛客五·ef，脑补H大致做法 自闭atcoder 7.29 自闭 edu 7.30 VP div2 div2 暴涨 text/html 2020-08-07T11:49:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:2020_08_01--2020_08_07_%E5%91%A8%E6%8A%A5&rev=1596772152&do=diff 8/1 牛客 8/2 atcoder 自闭 round up 8/3 牛客，只写了G，还没过 8/4 摸了 8/5 摸了 8/6 集训队加训，只写了H，还没过 8/7 队内加训，整理 wiki text/html 2020-08-14T17:40:11+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:2020_08_08--2020_08_14_%E5%91%A8%E6%8A%A5&rev=1597398011&do=diff 8.8 牛客 8.9 百度之星复赛 8.10 牛客 8.11 摸 8.12 杭电多校2018·二 8.13 摸 8.14 wiki除草，反思 复习模板 本周小结：太摸了 text/html 2020-08-19T10:48:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:2020_08_15--2020_08_21_%E5%91%A8%E6%8A%A5&rev=1597805338&do=diff 8.15 atcoder，补完F 8.16 看了眼 cf global D 8.17 训练，准备补HI 8.18 tc，爆零 8.19 训练 8.20 8.21 text/html 2020-08-07T17:49:01+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:atcoder_beginner_contest_174&rev=1596793741&do=diff contest link round up: 向上取整 round down: 向下取整 round: 四舍五入 E题 题意：见题目 题解：二分即可，比较坑的是以为最终结果采用四舍五入近似，其实 round up 是指向上取整。 只对最终答案取 ceil 依然 wa 了两个点，可能精度不够？目前只通过全程 int 才过 text/html 2020-09-14T11:28:12+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:atcoder_beginner_contest_175&rev=1600054092&do=diff contest link F 题意：最小拼接代价，得到回文串。 题解一：将字符串翻转，原串、翻转串分别拼成一个常婵，最小化 $f_{tij}$，以原字符串 t 开始，$ij$ 分别指代原串、翻转串的匹配位置，匹配长度相同且过程中字符均相等的最小代价。统计答案时，$ij$$j$$t$$\text{状态数}<n*Len*Len$$600ms/2s$$5ms$ text/html 2020-09-14T11:31:50+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:atcoder_beginner_contest_178&rev=1600054310&do=diff Task Link D题 枚举容器数 $i$，削去 $3*i$，剩余 $m$ 球装入 $i$ 个容器的方案。 解法一：视作 $i$ 种体积为 $1$、数量无限的物品装入容积为 $m$ 的完全背包 解法二：插板法 $C(i+m-1,i-1)$ F题 存在 $f[i]+g[i]>n$ 则无解（鸽巢原理）。 解法一：反序，设重叠部分值为 $i$$i$$n-a-b + a\cap b=n-f[i]-g[i]+a\cap b>= a\cap b$$i$$f[i]+g[i]<n$$f[i]+g[i]$$i={\max\arg}_{i} f[i]+g[i]$$j$$n-1$$j$$f[i]+g[i]==f[j]+g[j]$ text/html 2020-09-23T16:03:45+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:dsu_on_tree&rev=1600848225&do=diff MAIN 主要依据轻重链思想，暴力统计轻儿子对当前节点答案贡献，先递归解决轻儿子并消除影响，再递归重儿子并保留影响用于此节点统计答案。 全局时间复杂度 $O(n\log n)$ text/html 2020-12-12T23:38:04+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:front_page&rev=1607787484&do=diff Immortal.S/Front Page " Everybody should move on and grow. Some do. But not me." Todo ---------- * 复习模板 * SAM/SA/KMP/MANACHER Done * splay/lct Done * cdq分治 * 主席树系列 Done * sap/dinic网络流 * spfa/dijkstra 费用流