Codeforces Round #419 简要题解
Div1Div2Karen and Morning暴力枚举即可。代码Karen and Coffee差分求出每个点被覆盖的次数，再求一个被覆盖次数是否 $\geq k$ 的前缀和即可。代码Karen and Game先把行尽量删完，再把列尽量删完，如果最后剩下了则无解。但这不一定是最优的，还有可能先把列尽量删完，再把行尽量删完。两种情况比一下即可。代码Karen and Test$n$ 为偶...
标签 排列组合 下的文章
- 首页
- 排列组合
AtCoder Regular Contest 077 简要题解
比赛地址pushpush双端队列模拟即可。代码11显然有恰好一个数出现了 $2$ 次，设其出现的两个位置为 $l,r(l<r)$。考虑容斥。长度为 $k$ 的子序列数显然为 ${n+1\choose k}$，但其中有重复的。冷静分析一下可以发现，重复的一定是在 $l-1+(n+1-r)$ 个元素中选了 $k-1$ 个，和某个重复的数组成了子序列。所以答案为 ${n+1\choose k...
AtCoder Regular Contest 076 简要题解
比赛地址Reconciled?如果 $\lvert n-m\rvert>1$ 一定无解。否则，如果 $n=m$ 则答案为 $2\times n!\times m!$，如果 $\lvert n-m\rvert =1$ 则答案为 $n!\times m!$。代码Built?和某个切比雪夫距离最短路的题很像。对于每个点 $(x,y)$，向 $x$、$y$ 各连一条 $0$ 边。然后再把相邻两...
CF520E Pluses everywhere
CodeforcesLuogu分析考虑每个数 $a_i$ 的贡献。枚举长度可以得到预处理 $a_i$ 的前缀和即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== ...
AtCoder Regular Contest 067 简要题解
比赛地址Factors of Factorial直接把 $1\sim n$ 分解质因数即可。代码Walk and Teleport显然从左往右走是最优的，相邻两个选更小的方式即可。代码Grouping设 $dp_{i,j}$ 表示 $i$ 个人分成若干个人数 $\leq j$ 的组的方案数。转移时枚举人数 $=j$ 的组数 $k$，那么首先要在 $n-i+jk$ 个人中选出 $jk$ 个，然...
AtCoder Regular Contest 065 简要题解
比赛地址白昼夢 / Daydream如果当前字母是 d 则依次匹配 dreameraser、dreamerase、dreamer、dream，如果当前字母是 e 则依次匹配 eraser、erase。不如直接倒着做代码連結 / Connectivity开两个并查集，然后开个 map 维护一下 [find1(i),find2(i)] 即可。代码へんなコンパス / Manhattan Compa...
洛谷3643 [APIO2016]划艇
LuoguLOJ分析一个显然的想法是设 $dp_{i,j}$ 表示前 $i$ 个学校，第 $i$ 个学校派了 $j(j\neq 0)$ 艘划艇的方案数，然而第二维高达 $10^9$。可以想到把所有端点离散化一下（这里改成左闭右开区间会方便一些），$dp_{i,j}$ 的定义改为前 $i$ 个学校，第 $i$ 个学校派的划艇数在第 $j$ 个区间中的方案数。考虑转移。我们枚举一个 $k$，然后...
洛谷4491 [HAOI2018]染色
LuoguLOJ分析显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到可以发现是一个差卷积的形式，于是直接 NTT 即可。代码// =======================...
洛谷4841 [集训队作业2013]城市规划
Luogu分析设 $f_i$ 为 $i$ 个点的无向连通图个数，$g_i$ 为 $i$ 个点的无向图个数，那么显然有多项式求逆后卷起来求出 $[x^{n-1}]F(x)$ 从而求出 $f_n$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com...
洛谷6620 [省选联考 2020 A 卷] 组合数问题
LuoguLOJ分析预处理该处理的东西即可 $\mathcal{O}(m^2)$ 计算。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <b...