简介 如标题，本文主要记录中学物理中的一些不那么重要但是又确实会用到的边角料知识。有些需要微积分，有些不需要。 测电阻实验的电流表内外接误差分析 设待测电阻为 RRR，电流表电压表内阻为 RA,RVR_A,R_VRA​,RV​ 并且 RA≪R≪RVR_A\ll R\ll R_VRA​≪R≪RV​，下面分析为什么将 RRR 与 RARV\sqrt{R_AR_V}RA​RV​​ 比较。 内接法 对于内 ...

机器分配 总公司拥有 M 台 相同 的高效设备，准备分给下属的 N 个分公司。 各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。 问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。 分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数 M。 链接：AcWing 1013。 本题考查多重背包问题与求方案数，代码如下： 1234567891011 ...

背包问题求具体方案 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N。 链接：AcWing 12。 当判断当前物品 i 是否取时，判断下列是否成立即可： j \ge ...

模板 最长上升子序列问题有 DP 和 贪心 两种解法，见前文，这里再写一遍思路。 表示：f[i] 是以第 i 元素结尾的子序列。 存储：这些子序列中的长度最大值。 状态转移方程：f[i] = max(f[i], f[j]+1)，其中 j 是 0~i 中能与第 i 元素构成上升子序列的所有元素下标。 123456789101112131415161718192021222324#include ...

简介 数字三角形类问题的特点是当前状态可以由上一行计算出的状态得出，在之前写的一篇文章中记录过，本文记录两道基于数字三角形模型的实际问题。 方格取数 设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。 某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。 在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人 ...

区间选点 给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。位于区间端点上的点也算作区间内。 题目链接：AcWing 905。 先把区间按照右端点排序，然后每个区间尽量选择右端点，如果选过的点包含了当前区间则跳过，因为这样选择之后一定会选中 M 个不相互重叠的区间，想覆盖这些区间的最小点数一定是 M： 12345678 ...

分割棋盘 求把 N x M 的棋盘分成若干个 1 x 2 的长方形有几种方案。 题目链接：AcWing 291。 把某种状态以一个二进制数表示出来就是状态压缩，这里用一个二进制数储存在 n 行中有哪些长方形伸了出来，这里设 n 行 m 列，分析如下： 状态表示 f[i, j]： 含义：第 i 列中从 i-1 列中伸出来了状态为 j 的横着放的长方形的方案。由于剩下的位置只有竖着放长方形这一 ...

简介 本文包含数字三角形问题、最长上升子序列问题的几道基础例题，更多内容参考本站其它相关文章。 然后把一些不好分类的题也写在这里了。 数字三角形 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 12345 7 3 8 8 1 0 2 ...

01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。 原题：AcWing 2。 动态规划最入门的问题，我们开辟一个二维数组 f[i][j]，它的含义是在前 i 个物品中在体积最大为 j 的基础上的最优解。 可以得到状态转移方程：f[i][ ...

快速幂 快速幂是在 O(log⁡k)O(\log k)O(logk) 的复杂度下计算 ak mod pa^k\bmod pakmodp 的结果。 可以用二进制的方式理解，令 k=∑bi2ik=\sum b_i2^ik=∑bi​2i，那么 ak=a∑bi2i=∏(a2i)bia^k=a^{\sum b_i2^i}=\prod (a^{2^i})^{b_i}ak=a∑bi​2i=∏(a2i)bi​，所 ...