retep

分类

笔记(6) 题解(2)

/ 注册

全部文章（共8篇）

Kemija 题解

题目简述输入 nnn 个化学方程式，判断每个式子是否配平。配平的意义为 -> 前后每个原子的数量相等，也就是说符合质量守恒定理。需要注意的是，以 + 为分隔符的每个小项中，第一个数字表示之后整个原子团的个数。这之后每个大写字母表示一个原子，若其后方跟了一个数字 xxx，则表示有 xxx 个...

C++

2022-07-21

0 319

莫比乌斯反演

运用莫比乌斯反演，我们可以将一些函数转化，从而降低计算难度。在一些于 gcd 相关的算法问题中，莫比乌斯反演非常重要。狄利克雷卷积英文名为 Dirichlet 卷积，以下用符号 ∗*∗ 表示。 (f∗g)(n)=∑d∣nf(d)×g(nd)(f*g)(n)=\sum_{d|n}f(d)\time...

数论

2022-06-28

0 265

快速傅里叶变换（后）

单位根有了幅角和模长，怎么具体的把这个复数写出来呢？三角函数是个很有用的公式，高中知识告诉我们 sinθsin\thetasinθ 表示当幅角为 θ\thetaθ，模长为 111 时的 yyy 坐标，cosθcos\thetacosθ 表示 xxx 坐标。复平面中 xxx 和 yyy 分别表示 ...

C++ 快速傅里叶变换

2022-06-17

0 434

快速傅里叶变换（前）

快速傅里叶变换 FFT，也就是 Fast Fourier Transform，是利用离散傅里叶变换（DFT）的高效、快速计算方法的算法统称。对于一个 OIer，FFT 最大的用处是用来加速多项式乘法。其本质是以 O(nlgn)O(nlgn)O(nlgn) 的时间复杂度将点值表示法与系数表示法相互转换...

C++ 快速傅里叶变换

2022-06-17

0 298

分配问题——线性规划模型

题目简述 nnn 个人分配给 mmm 个工作岗位 (n⩾m)(n \geqslant m)(n⩾m)，每个岗位 111 个人。已知第每个人在每个岗位上的效率，求最佳分配方案使得所有人的效率总和最大。设立变量设立变量 xi,jx_{i,j}xi,j，1⩽i⩽n1\leqslant i \leqs...

2022-05-28

0 593

二分队列，用于优化决策单调性动态规划的方法之一

若有方程 f[i]=min{f[j]+cost(j,i)∣j<i}f[i]=min\left\{f[j]+cost(j , i) | j<i\right\}f[i]=min{f[j]+cost(j,i)∣j<i}，这种方程一般是经典的切割问题，如果 f[i]f[i]f[i] 的最...

动态规划队列

2022-05-12

0 432

插头dp学习笔记

插头DP是一类基于连通性的状态压缩动态规划，是用状压DP处理联通问题的强劲武器。本文以P5056【模板】插头dp为例进行分析。一个格子有四个插头，上下左右，就像拼图凸出来和凹进去的地方。一个格子会选出两个插头，形成一条经过此格的路径。当两个左右在一起的格子，左边的格子选了右插头，右边的格子选了左插...

动态规划状态压缩

2022-05-12

0 501

题解 | #牛牛的计算机内存#

题意可以对 nnn 条 010101 字符串进行任意排序，排好序后的代价为从前往后每次加入新 010101 串后多出 111 位置数的平方的累加。解法本体是经典的状态压缩，状态表示的是m块内存哪些已经访问过了。用记忆化搜索实现非常方便。函数传递的参数为已经访问过几块内存了、n个位置中哪些位置...

C++ 动态规划

2022-05-12

1 593