LWLAymh的备忘录

由于准备再战XCPC, 因此我要开始复健OI! 图论 2 SAT 感觉之前打oi的时候理解的并不透彻啊. 首先,2 SAT算法的本质是以下两个公式: 1. 2. 因此,当我们遇到一个2 CNF的时候,我们会尝试把其中的所有 转化为 , 得到的会是和原本公式完全等价的新公式. 你可…

贪心 排除不优策略 Example1(CF1612E) 先把期望写开,我们发现如果选择了 个消息 ,那么答案就是 .显然如果 固定,那么每个 的贡献是独立的.于是只需要枚举 然后取贡献最大的. 但是,如果 ,这个时候 的答案是 个数之和除以 , 的答案是这 个数之和加上另一个更小…

二项式系数 上升幂和下降幂 定义下降幂 . 定义上升幂 . 上升幂和下降幂的定义是可以引申到复数域的. 例如我们有加倍公式: . 他们之间存在转换: . 同时存在大小关系: ,其中 . 二项式系数的定义 考虑令 表示从一个大小为 的子集中选出大小为 的子集的方案数.第一次有 个选…

抽象代数 群 定义 如果一个非空集合 上定义了一个二元运算 (不引起混淆的前提下,通常省略不写,例如 记作 ),满足: 0. 封闭性: . 1. 结合律: . 那么称作 是一个 半群 . 如果它还满足: 2. 存在幺元: ,使得 . 那么称作 是一个 幺半群(monoid) . …

高数基础补档 复数相关 棣莫弗定理: . 欧拉公式: . 也就是 ,同时又有 ,证明直接使用泰勒展开. 单位根:对于 ,我们会有 个根,设第 个根为 .那么我们有: . 单位根有以下性质: 1. 折半引理: ,由我们上面推导的通项公式即可证明. 2. 消去引理: ,同样使用通项，…

十一岁的时候，所有人都知道她喜欢谁。她早就跟无数人谈起过她有多喜欢那个会打架子鼓的男生，而且总会谈起他去年在元旦晚会上表演的节目，他当时穿着牛仔裤，一条裤腿挽着，就那么一边打鼓一边晃着身子。她不懂架子鼓，她也没有仔细去听他的鼓点，而只是呆呆地看着他挽起的裤腿。她就这么发呆到表演结…

离散概率 基本定义 概率空间 :在一个给定问题中可能发生的所有情况. 事件: 的一个子集. 基本事件 : 中的单个元素,也可以看作集合大小为 的事件. 概率:若 ,我们称它发生的概率为 ,有 且 . 随机变量:在概率空间的基本事件上定义的函数. 联合分布:如果两个随机变量 和 定…

我怀疑洗袜子这件事中有某种神性。 首先，手洗袜子毫无疑问是一件苦役：一只袜子正反要搓四次，那一个周就要搓 次袜子。而且宿舍水槽太低，以至于手洗袜子时不得不弯头哈腰，而且还要忍受不时飞溅到脸上的水珠。 其次，比起机洗袜子，选择手洗袜子似乎也并没有什么足够的理由。这首先就不可能是因为…

Regular Languages 略 DFA 略. NFA 考虑一个五元组 ,比起DFA,这里的 ,也即现在一个点可能会有若干条字符相同的边指向若干其它结点. 利用NFA容易证明当 是正则语言的时候, 都是正则语言. GNFA 考虑一个五元组 ,这里其实一般认为 .比起NFA,…

前言 本笔记是Paolo Aluffi《Algebra: Chapter0》一书的笔记.并在过程中参考李文威《代数学讲义》和《代数学方法》,复旦大学出版社的《集合论: 对无穷概念的探索》.中途也许会部分重复指涉本人的高等代数笔记,以及网络资料. 本文应该会只在个人博客上连载,标题…