- 博客(20)
- 收藏
- 关注
RSS订阅
原创 【清华集训2017】生成树计数 &【WC2019】数树
扩展prufer序列到N结点连成m个连通块的情形。结论：生成树个数为 N^(m-2) \prod ai。我们来表演一下用这个结论秒切WC题
2019-02-03 17:45:15
1312
原创 多项式取模优化齐次线性递推
线性递推可以用多项式取模优化做到O(mlogmlogn)的优秀复杂度。本文主要介绍了不借助矩阵来理解多项式取模与线性递推关系的巧妙方法
2018-06-30 20:40:24
1593
1原创 [51nod17E] Simple KMP 解题报告
对字符串S,将i向KMP的fail[i]连边,形成一颗树的形状,设f(S)是除了0以外所有点深度和,其中0号点的深度为-1。定义key(S)为所有非空子串S'的f(S')之和。每次在S最后添加一个字符，并输出key(S)
2018-08-03 22:28:25
411
原创 解题报告：一道关于进制转换的题
给定一个十进制数y，请选择一个进制b，使得y转成b进制后大于或等于b进制下的l，且每位均为0到9之间的数码。求最大的b。
2018-06-21 18:26:50
646
原创 Decompose解题报告
题目大意给一棵有根树，每个点有LLL个权值w[u][i]w[u][i]w[u][i]。把树划分为若干纵向的长度不超过LLL的树链，链中从深到浅第iii个点产生w[u][i]w[u][i]w[u][i]的权值。最大化权值和。支持单点修改权值。Solution显然dp状态要记子树根在链中是第几个。此题LLL很小，一个点对dp值所施加的变换就是一个L×LL×LL\times L的矩阵，然...
2018-04-28 22:47:34
379
原创 树链剖分维护DP
算法思想把树上dp的过程看作是结点uuu根据自身的数据对儿子传上来的dp值进行加工（变换），进一步表示为根据自身数据和轻儿子的dp值对重儿子传上来的dp值进行变换。 要满足变换是可合并的。例如矩阵（线性变换）、加乘max混合运算等。 然后用一个线段树维护一条链的和变换。 需要维护对轻儿子的dp值求并的操作。如果是取max可以对每个父亲开一个可删除堆来维护。修改操作单点修改并在链...
2018-04-28 22:15:07
301
原创 斯特林数
斯特林数第一类斯特林数将nnn个(区分)物品分成mmm个(不区分)非空环排列的方案数递推式O(nm)O(nm)O(nm)[n+1m]=n×[nm]+[nm−1][n+1m]=n×[nm]+[nm−1]\left[\begin{array}{c}n+1\\m\end{array}\right] = n\times\left[\begin{array}{c}n\\m\end{a...
2018-03-05 11:40:48
407
原创 虚树学习笔记
虚树一点理解将关键点按dfs序排序后，所有关键点与相邻关键点的lca合起来构成虚树（通常还要加上整棵树的根）。 虚树至多有2k2k2k个点。体现在实现中就是每次都pop若干点，并有机会push2个点。stk[]中存的是从根到当前点的递归栈中目前选入虚树的点。 stk中的点之间都未连边（因为事实上关系还未确定），pop掉一个点的同时把它的父边连上。插入一个点时，计算这个点与上一...
2018-02-18 21:29:12
426
原创 ZKW线段树模板总结
ZKW线段树模板总结初始化int N = 4;while (N-2 N 1;建树void build() { for (int i = N+n+1>>1; i; i--) pushup(i);}单点改，区间求和void modify(int x, long long val) { for (tr[x += N] = val; x
2018-02-04 20:42:37
373
原创 【动态点分】绿老师 解题报告
鉴于我从未写过动态点分，wxh佬建议我拿这道题练一下，作为我的第一道动态点分模板题。主要关于“树上最近/最远点对”问题的各种变形
2018-01-25 10:26:22
324
原创 【动态点分】[高新集训]Tree 改题报告
这题思路很明显的，很快想到，然后写挂。好像写出来bug数不胜数。因此本文主要聚焦在debug过程，故称“改题报告”
2017-12-26 21:35:13
277
原创 错题集
关于最终检查时机：可以写一道查一道，但离考试结束还有10-20分钟时，必须统一再检查一遍。流程：文件名 源程序文件名输入输出文件名freopen有没有被注释掉全局变量 对数组，检查大小有没有开错对所有类型的变量，考虑是否需要初始化 计数器（包括用于计数的数据结构）邻接表——h[]置为0手写栈或队列——h = t = 0STL——.clear()
2017-11-08 20:23:27
400
原创 【2017国庆雅礼集训】长沙雅礼划水记
结束那天在校门口遇到孔爷，他问我：“你好强啊，每天上课都去切题。为什么考试的时候就那么菜啊？”啊咧？我还以为我发挥得已经很好了呐。看来我毕竟还是太咸啦，能力还是不够啊，还需要学习。
2017-10-01 21:09:34
1223
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人