笔记参考:emofunc-牛客博弈论课程课件 博弈的基本概念 组合游戏 两个玩家 一个状态集合 游戏规则是指明玩家在一个状态下可以移动到哪些其它状态 玩家轮流进行移动 如果当前处于某个状态,玩家根据规则无法移动,则游戏结束 (大部分时候)无论玩家如何选择,游戏会在有限步以内结束 组合游戏是非常常见的博弈模型 经典模型 Bash 游戏:一堆石子,轮流…
Good problem. 题意 题目链接 Monocarp 词典包含 $n$ 个单词,由 $12$ 个拉丁字母组成。单词编号从 $1$ 到 $n$ 。每个单词中的每一对相邻字符都是不同的。对于每个单词 $i$ ,Monocarp 也有一个整数 $c_i$ ,表示他使用这个单词的频率。 Monocarp 想要设计一个键盘,让他可以轻松地输入其中的一…
内容参考: 牛客竞赛字符串专题-calabash_boy 樱雪喵-广义后缀自动机(广义 SAM)学习笔记 KMP KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ,即一个字符串同长度的完全相同的前后缀(通常不含自身)。 KMP 的做法是先求出要匹配的字符串(短串)的所有前缀的最长 Border,然后在于长串进行匹配,并在无法匹配…
这个笔记想写得稍微详细一点,部分内容来自我自己之前的博客: OI 里的数学内容整理(提高组)。 其中一些公式是 AI 从 PPT 上识别的,格式混乱,还请谅解。 整数分解与筛法 欧几里得算法 用于求解两个数的最大公因数。 $\gcd(a,b)=\gcd(b,a\bmod b)$。 int gcd(int a,int b){ return b==0?…
图匹配 二分图匹配 判定 静态:黑白染色。 动态:分层并查集。并查集可以维护的可以是点的连接关系,也可以是关系的连接方式。连接两个点,我们可以改为连接这两个点的逻辑关系,黑-白,白-黑。如果有一天同一个点的黑白被连在了一起,则这就不是一个二分图。 分层并查集经典例题:P2024 [NOI2001] 食物链。 最大匹配:匈牙利算法 模版:P3386 …
区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…