LOJ6495 「雅礼集训 2018 Day1」树
LOJ 分析 设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。 显然树上一定存在 $(1,2)$ 这条边，因此我们转移时讨论以 $2$ 为根的子树（记做 $A$）和整棵树其它部分（记做 $B$，显然它也是一棵树）的高度关系。 转移讨论一下整棵树最深的节点在哪里即可 边界为 $dp_{1,1}=dp_{1,2}=1$。 代码 偷懒把第一问打了个表 QAq...
标签 排列组合 下的文章
- 首页
- 排列组合
洛谷3270 [JLOI2016]成绩比较
Luogu LOJ 分析 考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。 首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即 总时间复杂度为 $\mathcal{O}(n^2m)$。 代码 // ============...
CF1284E New Year and Castle Construction
Codeforces Luogu 分析 考虑任意五个点对答案的贡献。显然有 如果五个点的凸包为五边形，则贡献为 $0$； 如果五个点的凸包为四边形，则贡献为 $1$； 如果五个点的凸包为三角形，则贡献为 $2$。 我们只需要求出五个点凸包为为 $x$ 边形的方案数 $s_x$，然后答案即为 $s_4+2s_3$。 不知道怎么想到可以把答案拆成 $5(s_5+s_4+s_3)-(5s_5+...
51nod1667 概率好题
51nod 分析 甲胜和乙胜类似，三者概率之和为 $1$，因此只考虑计算甲胜的概率，即甲胜的方案数除以总方案数。 设甲的第 $i$ 个数为 $X_i$，乙的第 $i$ 个数为 $Y_i$，则甲胜当且仅当 则我们相当于要求这个 $k_1+k_2+1$ 元不定方程的非负解数，其中一些变量有上界。 考虑容斥掉上界的限制，即钦定一些变量超过了上界，则我们只需要计算不定方程 $\sum_{i=1}^...
洛谷4609 [FJOI2016]建筑师
Luogu LOJ 分析 显然左边看到的是前缀 $\max$，右边看到的是后缀 $\max$，而最大值前后都能看到。 除去最大的，剩下的 $n-1$ 个数需要划分成 $A+B-2$ 个圆排列（圆排列的原因是因为我们需要钦定最大的放在某个端点）；然后这 $A+B-2$ 个前后缀 $\max$ 中需要选出 $A-1$ 个放在左边。 于是答案为 代码 // ===================...
AGC005F Many Easy Problems
AtCoder Luogu 分析 设要求的东西是 $f_i$，考虑怎么求这个东西。 可以想到计算每个点在多少种方案中，进而想到计算每个点不在多少种方案中。于是容易得到包含 $u$ 的方案数为 可以发现后面已经是卷积的形式了，于是直接 NTT 即可。虽然这个模数很奇怪，但是它确实是 NTT 模数。 代码 // =================================== // ...
AGC001E BBQ Hard
AtCoder Luogu 分析 观察题目中给的这个式子 等价于从 $(0,0)$ 走到 $(a_i+a_j,b_i+b_j)$ 的方案数，等价于从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的方案数。 然后题目中要求的是 $\sum$，因此我们考虑求出以每个 $(-a_i,-b_i)$ 为起点走到每个 $(a_j,b_j)$ 的方案数之和。 注意到 $a_i,b_i$ 的...
SPOJ GSS 系列简要题解
GSS1 线段树上维护以下 $4$ 个东西： 区间和 区间最大前缀和 区间最大后缀和 区间最大子段和 合并两个区间应该比较简单，这里不再赘述。 GSS2 这题就很神仙了。 把所有询问离线并按右端点排序，然后从左往右扫。 对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。 设 $pre_i...