51nod1805 小树
51nod分析考虑一棵满足条件的树的 prufer 序列，可以发现有恰好 $m$ 个数没有出现过。考虑容斥，则我们需要求出至少 $i$ 个数没有出现的方案数，即为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ================...
标签 排列组合 下的文章
- 首页
- 排列组合
51nod1667 概率好题
51nod分析甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^n x_i=...
洛谷6076 [JSOI2015]染色问题
Luogu分析考虑容斥。枚举 $i$ 行 $j$ 列不填、$k$ 种颜色不用。不难得到答案为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bi...
洛谷4609 [FJOI2016]建筑师
LuoguLOJ分析显然左边看到的是前缀 $\max$，右边看到的是后缀 $\max$，而最大值前后都能看到。除去最大的，剩下的 $n-1$ 个数需要划分成 $A+B-2$ 个圆排列（圆排列的原因是因为我们需要钦定最大的放在某个端点）；然后这 $A+B-2$ 个前后缀 $\max$ 中需要选出 $A-1$ 个放在左边。于是答案为代码// ===========================...
AtCoder Grand Contest 002 简要题解
比赛地址Range Product简单讨论一下即可。代码Box and Ball简单模拟一下即可。注意盒子里仅有一个球的情况。代码Knot Puzzle能全部解开当且仅当存在两条相邻的绳子满足长度之和 $\geq L$。正确性显然。代码Stamp Rally先考虑怎么算从 $x,y$ 出发最多能到达的点数。显然，如果 $x,y$ 连通，则为 $sz_x$，否则为 $sz_x+sz_y$。这里...
AtCoder Grand Contest 001 简要题解
比赛地址BBQ Easy排序后相邻的两个放一组即可。正确性显然。Mysterious Light可以发现每次反射之后问题都变为一个子问题，于是直接递归做下去即可。可以发现边界为 $n\bmod x=0$。Shorten Diameter当 $k$ 为偶数时，枚举一个根，然后删掉所有到根距离 $>\frac{k}{2}$ 的点。在所有这样算出来的答案中取 $\min$ 即可。当 $k$ ...
CF1228E Another Filling the Grid
CodeforcesLuogu分析显然可以考虑容斥。枚举 $i$ 行 $j$ 列的最小值不为 $1$，可以得到答案为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #in...
CF839D Winter is here
CodeforcesLuogu分析设 $dp_i$ 表示 $\gcd$ 为 $i$ 的子序列的总长度。考虑容斥，用 $\gcd$ 为 $i$ 的倍数（包括 $i$）的子序列的总长度减去 $\gcd$ 为 $i$ 的倍数（不包括 $i$）的子序列的总长度。先考虑第一部分。设 $s$ 为 $i$ 的倍数的个数，则第一部分的答案为于是就很容易算出 $dp_i$ 了。实现上统计 $i$ 的倍数个数时...