CF582D Number of Binominal Coefficients
CodeforcesLuogu分析首先有一个定理：${a+b\choose a}$ 质因数分解后 $p$ 的幂次等于 $p$ 进制下 $a+b$ 的进位次数。于是可以把 $A$ 转成 $p$ 进制，然后考虑数位 DP。设 $dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，第 $i-1$ 位是否向第 $i$ 位进位，$a+b$ 是否顶着 $A$ 的上界的方案数。转移比...
标签 动态规划 下的文章
- 首页
- 动态规划
JOISC2019 简要题解
官网AtCoderLOJ試験 / Examination三维偏序板子，CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
洛谷6295 有标号 DAG 计数
Luogu分析设 $f_i$ 为 $i$ 个点的 DAG 数量。一个想法是枚举入度为 $0$ 的点的数量，有多项式求逆即可。现在还要求弱连通，那么把 $F(x)$ 求个多项式 $\ln$ 即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ /...
CF1349D Slime and Biscuits
Codeforces分析设 $E(x)$ 为游戏结束时所有饼干都在 $x$ 手中的期望次数，$E'(x)$ 为游戏结束当且仅当所有饼干都在 $x$ 手中时的期望次数，$P(x)$ 为游戏结束时所有饼干都在 $x$ 手中的概率，$C$ 为所有饼干都在某个人手中时全部到另一个人手中的期望次数，则有又因为 $g_0=f_0-f_1=n-1$，所以我们可以递推求出所有 $g_i$，从而求出所有 $f...
AGC028E High Elements
AtCoder分析因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我们交换这两...
AtCoder Regular Contest 081 简要题解
比赛地址Make a Rectangle求出每种边的数量，$\geq 4$ 的看成 $2$ 个，$\in[2,3]$ 的看成 $1$ 个，将最大值和次大值作为长和宽即可。代码Coloring Dominoes根据当前列和上一列的情况算出当前的方案数，用乘法原理乘起来即可。代码Don't Be a Subsequence设 $nxt_{i,j}$ 表示 $[i,n]$ 中最靠前的 $j$ 字符...
Codeforces Round #419 简要题解
Div1Div2Karen and Morning暴力枚举即可。代码Karen and Coffee差分求出每个点被覆盖的次数，再求一个被覆盖次数是否 $\geq k$ 的前缀和即可。代码Karen and Game先把行尽量删完，再把列尽量删完，如果最后剩下了则无解。但这不一定是最优的，还有可能先把列尽量删完，再把行尽量删完。两种情况比一下即可。代码Karen and Test$n$ 为偶...
AtCoder Regular Contest 078 简要题解
比赛地址Splitting Pile枚举即可。代码Fennec VS. Snuke双方显然是先把对方到自己这边来的路堵上。于是我们只要找到分界点，看看哪边的点多即可。需要注意的是，如果两边的点一样多，那么是后手胜。代码Awkward Response首先可以把 $N$ 的位数确定出来：依次问 $1,10,100,\cdots$ 直到回答是 N，则前一个数和 $N$ 的位数相同。那么可以考虑二...
AtCoder Regular Contest 074 简要题解
比赛地址Chocolate Bar横着竖着是一样的，这里只考虑横着。那么要么是横切三刀，要么是先横切一刀再竖切一刀。前面只要看 $H$ 是不是 $3$ 的倍数，不是的话差最小是 $W$。后面可以直接枚举横切在哪，竖切一定切在 $\frac{W}{2}$ 的位置。代码3N Numbers显然存在一个分界线 $i\in[n,2n]$，满足在 $[1,i]$ 中选了最大的 $n$ 个、在 $[i+...
AtCoder Regular Contest 073 简要题解
比赛地址Sentou按题意算一下即可。代码Simple Knapsack这个 $w_1\leq w_i\leq w_i+3$ 非常的有趣。可以想到设 $dp_{i,j,k}$ 表示前 $i$ 个物品，已选的体积是 $j\times w_1+k$ 时的最大价值，转移和背包相同。最后算答案时枚举一下合法的 $j,k$ 即可。代码Ball Coloring不妨设 $x_i\leq y_i$，最小的...