牛客237787563号
牛客237787563号
全部文章
未归档
归档
标签
去牛客网
登录
/
注册
牛客237787563号的博客
全部文章
/ 未归档
(共11篇)
关于斯特林数
第一类斯特林数 定义 $S_1(n,m)$表示$n$个元素,形成$m$个环的方案数,记作$\begin{bmatrix}n\\m\end{bmatrix}$。 其中每个元素是不同的,每个环是相同的。 递推公式 从实际含义上去考虑,第一类斯特林数递推公式为: $\begin{bmat...
容斥
组合计数
数学
斯特林数
二项式反演
2019-12-11
0
428
省选模拟2 题解
A. 铁轨建设 暴力插头dp+网络流判断可行性,可以拿到85分。 然而这个题看起来就很像无限之环,只要稍微改一下建图就好了。 然而这个建图还蛮难想到的。 B. 圈地游戏 因为不会做+看不懂题解+std太长,所以咕掉了。 C. 组合数学 70分部分分:考虑到状态数很少,直接暴...
dp
网络流
二项式反演
容斥
组合计数
2019-12-24
0
408
省选模拟26 题解
A. 染色问题 不然想到一个50分的dp,然而我的dp转移和正解不一样所以没法优化所以就死了。。要是用我的dp推正解大概只能考虑实际含义。 考虑每次在已有的颜色序列中间插入一段,那么考虑转移的方案数,不难得到一条dp转移路径的贡献是每次颜色序列长度+1的乘积。 所以枚举一共经过了多少次转移,转...
dp
倍增
多项式
二项式反演
容斥
线段树
2020-02-22
0
388
省选模拟33 题解
A. 盗梦空间 考虑首先构建一棵虚树,然后跑一遍多源点最短路,求出每个虚树上的点到达最近的关键点的距离。 分类讨论最终的答案 $u$ 的出现位置。 1.出现在虚树节点的一个满足子树不含虚树节点的儿子子树中。 一个很好的性质是我们只关注最大值。 所以考虑对每个节点维护一个 multiset ...
容斥
莫比乌斯函数
二项式反演
倍增
数学
虚树
树剖
2020-02-28
0
346
省选模拟39 题解
A. gift 考虑把需要 $swap$ 的关系表示在图上。于是形成若干个环。 容易发现交换的次数就是点数减环数。 所以原题转化为环的计数问题。 考虑把已有的每个连通块的部分表示出来。 容易发现对于一条链我们并不关注中间是谁,只关注链首和链尾的状态,于是可以转化为五种形态。 如果已...
lct
二项式反演
后缀自动机
容斥
组合计数
2020-03-06
0
410
省选模拟40 题解
A. 染色问题 考虑对每条边 $(a,b)$ 附加两种边权 $(x,y)$ 。 对于一种染色方案,当 $col_a=col_b$,边权为 $x$,否则边权为 $y$。 取 $x=1,y=0$,一种染色方案的贡献是所有边权的乘积,那么答案就是对于每种染色方案的贡献的和。 发现这个玩意可以合并。...
组合计数
状压
网络流
二项式反演
2020-03-08
0
754
省选模拟42 题解
A. coin 容易发现每种假钞的期望贡献是独立的。 对于每种假钞,做一个 $n^2$的 dp 求出来选择 $i$张假钞的贡献。 然后对这个贡献做一个背包就完事了。 考虑一个东西,就是对于每种假钞,只能选择一个数目加入背包的贡献中。 所以可以考虑对于每种假钞一张张加入贡献。 然后发现发现...
矩阵树定理
二项式反演
dp
2sat
2020-03-10
0
353
组合计数 题解乱写
3.组合计数 上 1.ARC102E 把当前限制对应的每个二元组提出来。 枚举有多少个二元组中的数字出现了,然后问题是每个组中二选一。 出现的数字可以出现 $>0$ 次,不在任何一个二元组中的数字可以出现 $\geq 0$ 次。 统一一下就可以直接插板法了。 2.小Z的礼物 通过...
二项式反演
轮廓线
容斥
组合计数
2020-03-17
0
747
省选模拟53 题解
A. 数(number) 对于 $n$ 为偶数,容易发现确定一半就行了,答案为 $10^{\frac{n}{2}}$。 对于 $n$ 为奇数,列式子可以发现形如 $\sum 2x_i = \sum 2y_i \ \ +y_{mid}$。 一步很神的操作是,把 $y_i$ 转化为 $9-y_i$...
容斥
二项式反演
二分答案
贪心
线段树
2020-03-25
0
396
省选模拟69 题解
A. 最小生成树 因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值, 所以最优的策略肯定是将这棵树弄成一个菊花图。 然后考虑把所有的边权按顺序列出来。 如果当前还没有超出 $m$ 条边的限制,那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。 那考虑一个特殊的情况,如果说...
二项式反演
多项式
动态dp
dp
分治
构造题
结论题
容斥
贪心
2020-04-13
0
381
首页
上一页
1
2
下一页
末页