概率dp

dp题题集 目录dp题题集P1216 数字三角形 Number TrianglesP2196 挖地雷P1060 开心的金明P8707 [蓝桥杯 2020 省 AB1] 走方格 由于dp做一道卡一道，于是开始死磕的日日夜夜 P1216 数字三角形 Number Triangles dp入门，求路径数字 ......

我们通常采用递归的方式实现树形dp。 对于每个节点，先递归在它的每个子节点上进行dp，在回溯时，从子节点向根节点进行状态转移。 顺序一般为从叶子结点到根节点递推。 题目： 一. P1352 没有上司的舞会 以子树的根作为dp状态的第一维。容易发现，每个员工是否参加至于他的上司是否参加有关。 不妨设 ......

只做理解类记录，哪个知识点忘了去看视频。前四章是概率，看的框框老师。 概率论 1、随机试验：可重复性、可预知性、不确定性 2、样本空间：随机试验E的所有可能结果，记为S或Ω 3、样本点：样本空间中的每一个元素e 4、随机事件：样本空间的子集，简称事件 5、事件发生：子集中某个样本点出现，不需要全部样 ......

都快csps了，还什么都不会的菜鱼（我估计着马上就可以改了这句话了，成了都快noip了） 矩阵 我们要用矩阵优化dp，首先要知道矩阵是个什么东西（感觉其实可以不用知道）。 矩阵的很多定义啥的都可以选择去oi-wiki上去进行学习。很简单的一堆定义。读者自学不难，这里就不多赘述。 矩阵加法 就是将对应 ......

一、基本概念 1. 随机试验 具有以下特点的试验称为随机试验（通常用 \(E\) 表示）： 可以在相同条件下重复进行 可能出现的结果有多个且试验之前知道所有的结果 试验结束后出现哪种结果是随机的 说人话：就是在相同条件下对某随机现象进行的大量重复观测 例子 \(E_1\)：抛一枚硬币，观察正、反面出 ......

2023年10月13日 更新于2023年10月13日 一、前言 本栏，为状态机模型，题目主要来源日常，目前主要来源于Acwing的提高课。希望以后做到状态机的题目，也能加进来，不断完善。使用的分析方法均为闫式DP分析法。字臭。。。希望能用手写板慢慢写的好看。 二、状态机模型 2.1 对于状态机的考虑 ......

数位dp 引入 数位 ：是指把一个数字按位数一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制，就比如 链接: [SCOI2009] windy 数的二进制同理。 常见特征 要求统计满足一定条件的数的数量（即，最终目的为计数）； 这些条件经过转 ......

Codeforces Round 903 (Div. 3) E. Block Sequence 思路： 设dp[i]为当i~n为完美的最少删除次数 dp[n]=1,dp[n+1]=0; 从后至前对于dp[i]更新 若直接删除当前点，则为 dp[i+1]+1 若不删除 则为 min（dp[i+a[i] ......

给定序列 \(m_i\)，求有多少排列 \(p\) 满足：对于满足 \(l \le r \le m_l\) 的所有 \((l,r)\)，\(p_{l \sim r}\) 都不是 \(l \sim r\) 的排列。答案对 \(10^9 + 7\) 取模。 \(n \le 200\)，时限 \(\tex ......

背包 约定使用 \(v_i\) 表示放入第 \(i\) 件物品的花费，\(w_i\) 表示第 \(i\) 件物品的价值，背包容量 \(M\)，物品件数 \(N\)。 01 背包 每种物品仅有一件，可以选择放或不放。 设 \(f(i,j)\) 表示前 \(i\) 件物品恰填满容量为 \(j\) 的背包 ......

感觉非常牛逼。最牛逼的是很多情况下要去掉前导零。 去掉前导零的方法通常是先忽略前导零的约束，最后再容斥掉有多少0。 Luogu P2602 数字计数 来自【详细解释】数字计数 ZJOJ p2602 一道练习数位DP的好题 - moye到碗里来 的博客 - 洛谷博客 (luogu.com.cn) 那么 ......

思路: 性质1, 相当于重新对这个序列排序 性质2, 等式关于 值域, 对于任意一个都满足, 那么就是 当前点 比前面放入的点 的最大值 - k 都要大, 比后面最小值+k都要小, --> 每一个点都要满足, 那么对于当前点的放置是有限制的,以 值域 来看 1-i 里面都已经放置了, 那么放置 后面 ......

无线电对讲机既是移动通信中的一种专业无线通信工具，又是一种能满足人们生活需要的具有消费类产品特点的消费工具。顾名思义移动通信就是通信一方和另一方在移动中实现通信。它是一种无线的可在移动中使用的一点对多点进行通信的终端设备，可使许多人同时彼此交流，使许多人能同时听到同一个人说话，但是在同一时刻只能有一 ......

动态规划——树形DP 学习笔记 引入 前置知识：树基础。 树形 DP，即在树上进行的 DP，最常见的状态表示为 \(f_{u,\cdots}\)，表示以 \(u\) 为根的子树的某个东东。 本文将讲解一些经典题目（树的子树个数、树的最大独立集、树的最小点覆盖、树的最小支配集、树的直径、树的重心、树的 ......

产品简介DP4306F是一款高性能低功耗的单片集成收发机，集成MO核MCU，工作频率可覆盖200MHiz^ 1000MHz。 支持230/408/433/470/868/915频段。该芯片集成了射频接收器、射频发射器、频率综合器、GFSK调制器、GFSK解调器等功能模块。通过SPI接口可以对输出功率 ......

看到网上的方法多多少少比较复杂，所以决定写一下。 首先对于一道换根dp题应该是先要会不换根版本的。 然后可以按照欧拉序（括号序）换根。对于欧拉序中相邻的两个节点必有一条边把它们相连，所以换根的时候只需要从新统计 \(1\) 个子树的信息。 觉得自己的语言表达能力太烂，还是上题目比较好。 P3478 ......

1.什么情况下可以使用动态规划来解决问题： （1）往往在求最优解的问题中使用动态规划。 （2）一个大问题可以被分解为小问题，且每一个子问题都对应一个互不相同的状态。 （3）在问题状态每次发生改变时，需要进行判断来决定如何改变。 ......

突然想到了一些理解，感觉有些模糊，怕忘记，就赶紧记下来就是对于状态的设计 用01背包举例子吧，我们设计状态的时候一定是要保证所有可能在最后优秀的子状态在前面的时候是能够保留下来的也就是我们的状态设计要能够保留那些在最后优秀但是现在可能不优秀的情况，而不是一味的追求最优子结构所以，01背包，我们很显然 ......

2023年10月11日 更新于2023年10月11日 一、前言 本栏，为背包模型，题目主要来源日常，目前主要来源于Acwing的提高课。希望以后做到背包的题目，也能加进来，不断完善。使用的分析方法均为闫式DP分析法。字臭。。。希望能用手写板慢慢写的好看。 二、背包模型 2.1 目前的模型 01背包模 ......

1、经典车羊问题 假设你参加一个游戏节目，有三扇关闭的门，其中一扇后面有一辆汽车，而其他两扇后面是山羊。你首先选择一扇门，然后主持人打开另外两扇门中的一扇，露出其中一只山羊。 现在，你可以选择是否改变自己的选择，选择另外一扇未被打开的门。那么，应该改变选择还是保持原来的选择呢？ import ran ......

CodeTON Round 5 ( Div1+Div2 ) C. Tenzing and Balls 思路：设f[i]为从 1~i 能删去的最多数 f[i] = max( f[i-1] , i - j + 1+ f[j-1] ) ( a[j]=a[i] , 删去i到j , 再加上前 j-1 可删去的 ......

2023年10月10日 更新于2023年10月10日 一、前言 本栏，为线性DP，题目主要来源日常，目前主要来源于Acwing的提高课。希望以后做到线性DP的题目，也能加进来，不断完善。 二、线性DP 2.1 目前的模型： 数字三角形模型 最长上升子序列模型 2.2 目前解决的问题： 可以解决路径上 ......

已知c,e,n,dp 求m（dp=d%(p-1)）import gmpy2from Crypto.Util.number import *n =dp =c =e = tmp = e * dp -1#根据联立条件有: e*dp = 1 + k(p-1)，故求解p的式子为：(p-1) = (e*dp-1 ......

OI-wiki Link 引入 动态规划(Dynamic Programming，DP)，是一种将原问题分为一些子问题，通过局部最优解推出全局最优解。 一般来说，做一道 dp 题有 \(4\) 个步骤： 设计 dp 状态：根据几个关键信息定下状态和最优化属性。 定下拓扑序。 设计状态转移方程。 确定 ......

题目描述 一个软件有 \(s\) 个子系统，会产生 \(n\) 种 bug。 某人一天发现一个 bug，这个 bug 属于某种 bug，发生在某个子系统中。 求找到所有的 \(n\) 种 bug，且每个子系统都找到 bug，这样所要的天数的期望。 bug 的数量是无穷大的，所以发现一个 bug，出现 ......

题目补充: 使得 a=b, 思路: 在 y<=x 好处理 在 y>x 时 利用区间dp处理 a==b 0, a!=b 1, 1要变 先预处理 把 0的 位置删了 删除多余信息 方便后面处理 然后 对于 取2个点 为 y ,另外一种操作就是 选2个连续的点直接 (他们位置差)*x 以此区间dp即可 或 ......

思路 : 找各种性质 1 每一秒只有 史莱姆进入起始点 , 然后他会选一个方向走(右或者下), 每一秒 史莱姆都会这样走 在考虑 前 t 秒内 有S个史莱姆到达这个点, 然后就会 有 s+1/2 个 往右走, s/2 往下走 而且 问t秒 只会 有 t-n-m-1 秒后的时刻影响 (诈骗t ) 于是 ......

"此刻发生的所有事，都是你过去选择的结果。" 最近打模拟赛在状压dp上总是没有一点思路。来重学一遍。 状态压缩：通过一串 0 1 码来清晰地表示一个集合的状态。同时，在确定了最低位的前提下，一串 0 1 码与一个二进制数一一对应。 其本质上是进行了两次操作： 给这个集合的每个状态一个编号。 通过这个 ......

目录I. Interval Addition I. Interval Addition 题意 给定一个长度为 n $(1\le n \le 23) $ 的数组 a。你可以进行一种操作：选择区间 \([l, r]\) 并给这个区间所有的数都加上一个任意的数。问你使得整个数组均为 0 所需的最小操作次数 ......

动态规划——带权二分优化DP 学习笔记 引入 带权二分其实并不一定用于优化 DP，也可能用于优化贪心等最优化的算法。 带权二分也叫 WQS 二分，最初由王钦石在他的 2012 年国家集训队论文中提出。 定义 使用情况 要解决一个最优化问题（求最大 / 最小值） 有一个限制，一般是某个参数要求一定恰好 ......