CF809E Surprise me!
Codefoces Luogu 分析 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题，报警了... 首先要知道 $f$ 和 $g$ 都很好转移，同时 $dp$ 也很好转移了。 因为 DP 只统计了 $i<j$ 的情况，所以要答案要乘 $2$ ；最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。 其实这题写起来挺休闲的 代码 ...
标签 动态规划 / DP 下的文章
- 首页
- 动态规划 / DP
洛谷2150 [NOI2015]寿司晚宴
Luogu 分析 先考虑一个 $30$ 分做法。 设 $dp_{i,j,k}$ 表示前 $i$ 个数，小 G 选的数的质因子集合为 $j$ ，小 W 选的数的质因子集合为 $k$ 的方案数。 转移枚举一下当前的数给谁即可。 $i$ 可以滚动数组滚掉。 注意到 $n$ 最多有一个 $>\sqrt{n}$ 的质因子，因此我们可以只状压 $<\sqrt{500}$ 的质因子，然后再单...
UVA1498 Activation
UVa Luogu 分析 首先把 $p_4=0$ 的情况判掉，答案显然为 $0$ 。 考虑 DP 。设 $dp_{i,j}$ 表示 $i$ 个人的队列，现在在第 $j$ 个，最后在前 $k$ 个位置的概率。 转移可以考虑后继状态，容易得到 于是可以得到 $dp_{1,1}=\frac{p_4}{1-p_1-p_2}$ 。 具体实现及细节见代码。 代码 // ================...
UVA1323 Vivian's Problem
UVa Luogu Vjudge 分析 梅森素数：形如 $2^p-1$ 的素数，其中 $p$ 是素数。 关于梅森素数有一个定理： $N$ 的约数和能够写成 $2^k\;(k\in\mathbb{N})$ 的充要条件为 $N$ 能够写成一些 $\textbf{互不相同}$ 的梅森素数的积。 于是考虑让 $N$ 为一些不同的梅森素数的积。 对于 $p_i$ ，如果它能够表示为不同的梅森素数的...
洛谷3779 [SDOI2017]龙与地下城
Luogu LOJ 分析 一种 FFT 做法 考虑 DP 。设 $dp_{i,j}$ 表示前 $i$ 个骰子和为 $j$ 的概率。 可以发现转移是一个多项式快速幂，于是直接 FFT 就可以了。 （大概）可以理解成概率生成函数卷积？ 然而 FFT 掉精度很严重，我只能过 $60$ 分。所以对于大数据要考虑其它做法。 一种定积分做法 首先要知道中心极限定理的一个推论： 设有 $n$ 个独立同分...
UVA10559 Blocks
UVa Luogu 分析 状态和转移都比较奇妙的 DP 。 设 $dp_{i,j,k}$ 表示 $[i,j]$ 区间，后面还有 $k$ 个和 $j$ 颜色相同的方块的最大分数。 转移有两种： 拿掉 $j$ 和后面的 $k$ 块：$dp_{i,j-1,0}+(k+1)^2\to dp_{i,j,k}$ 。 设 $p$ 为 $[i,j)$ 中与 $j$ 颜色相同的块，那么可以拿掉 $[p+1,...
CF98E Help Shrek and Donkey
Codeforces 分析 首先可以发现，不到最后是不会选择猜的。 假设你问了一张牌，对手没有，那么对手就会怀疑这张牌是桌上那张。 考虑这样一种神奇的操作：询问一张自己手上有的牌。这样子对手就会怀疑这张牌是桌上的，然后如果他问了他就输了。我们把这种操作称为欺骗。 考虑 DP 。设 $f_{n,m}$ 表示先手有 $n$ 张牌、后手有 $m$ 张牌时，先手的获胜概率。 我们列一个表格，表示在先...
洛谷3343 [ZJOI2015]地震后的幻想乡
Luogu LOJ 分析 首先看到题目里的提示： 对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,\cdots,x_n$，第 $k$ 小的那个的期望值是 $\frac{k}{n+1}$ 。 考虑一个暴力做法：枚举边权的相对大小，然后 Kruskal 求最小生成树并用这个提示算答案。 进一步考虑这样的一个做法：钦定一个边集 $S$ 作为前 $|S|$ 小的边，如果这个...
洛谷4495 [HAOI2018]奇怪的背包
Luogu LOJ 分析 先来考虑 $n=1$ 的情况，可以发现所有能取到的体积为 $k\cdot\gcd(v,P)$ 。于是我们可以直接把体积设成 $\gcd(v,P)$ 。 这样子所有体积都是 $P$ 的约数了。考虑预处理出 $P$ 的所有约数，然后求出每种约数在体积中的出现次数。 注意到一条性质：重复选取相同的体积对答案没有影响。于是假设第 $i$ 个约数有 $s_i$ 个，那么这个约...
ARC101F Robots and Exits
AtCoder 分析 我们先把所有只有只会从一个出口出去的机器人删掉，这些机器人不影响答案。 对于剩下的机器人，记它到左边第一个出口的距离为 $a$ ，到右边第一个出口的距离为 $b$ 。那么每个机器人可以看成一个点 $(a,b)$。 设 $x$ 为所有机器人往左移动的最远点到初始位置的距离，$y$ 为所有机器人往右移动的最远点到初始位置的距离。那么每次相当于把 $(x,y)$ 变成 $(x...