【整理】算法竞赛博弈游戏学习笔记
笔记参考:emofunc-牛客博弈论课程课件 博弈的基本概念 组合游戏 两个玩家 一个状态集合 游戏规则是指明玩家在一个状态下可以移动到哪些其它状态 玩家轮流进行移动 如果当前处于某个状态,玩家根据规则无法移动,则游戏结束 (大部分时候)无论玩家如何选择,游戏会在有限步以内结束 组合游戏是非常常见的博弈模型 经典模型 Bash 游戏:一堆石子,轮流…
CF1739F Keyboard Design 题解
Good problem. 题意 题目链接 Monocarp 词典包含 $n$ 个单词,由 $12$ 个拉丁字母组成。单词编号从 $1$ 到 $n$ 。每个单词中的每一对相邻字符都是不同的。对于每个单词 $i$ ,Monocarp 也有一个整数 $c_i$ ,表示他使用这个单词的频率。 Monocarp 想要设计一个键盘,让他可以轻松地输入其中的一…
ICPC Online 2024 K AC Automation Chicken 题解
很涩的一个题。 题意 题目链接 假如我们有一个 AC 自动机,我们可以取出其中的点,字符边和 Fail 边,这样其就变成了一个有 $n$ 个点和 $2n-2$ 条边的有向图。现在给出你这样一个有向图,你需要找到其原始的 AC 自动机结构(包括 1. 找到根 2. 找到哪些边是 Trie 树边 3. 给所有的 Trie 树边分配一个字符,字符集大小不…
【笔记】概率论与数理统计 (施工中)
基本信息 课程老师:郑志浩 上课事件:周四下午 678 节 计分规则 平时成绩 60% 作业+到课率 25% 参与“学在浙大”讨论 5% 小测 30% 取三次测验的两次最高分,但是要求全部参加 测验一:到第二章,秋 7 周周日晚 21:30-22:30 测验二:到第四章,冬 3 周周六晚 21:30-22:30 测验三:到第七章,冬 7 周周五晚 …
CF1208F Bits And Pieces 题解
题意 题目链接。 给你一个由 $n$ 个整数组成的数组 $a$ 。 你需要在所有三元组 $(i,j,k)$ 中找出 $a_{i} | ( a_{j} \& a_ {k} )$ 的最大值,使得 $i < j < k$ . 这里 $\&$ 表示 位与运算,而 $|$ 表示 位与运算。 由 Codeforces Better!…
【整理】算法竞赛字符科技学习笔记
内容参考: 牛客竞赛字符串专题-calabash_boy 樱雪喵-广义后缀自动机(广义 SAM)学习笔记 KMP KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ,即一个字符串同长度的完全相同的前后缀(通常不含自身)。 KMP 的做法是先求出要匹配的字符串(短串)的所有前缀的最长 Border,然后在于长串进行匹配,并在无法匹配…
【整理】算法竞赛动态规划学习笔记
一些动态规划类型 树形 DP 树形 dp 的常用方法(例如树上背包)是将接下来要处理的儿子与以及处理完的儿子的全体进行合并,即把处理多个子树的问题转换为依次合并两个儿子的问题。 树形 dp 类型众多,故这里不多做赘述。 状压 DP 状压 dp 的核心是把状态用二进制数进行压缩(有些时候可能会用到四进制,如果一个点有三种或四种状态)。处理状压 dp …
【整理】算法竞赛计算几何学习笔记
好用的参考:来自俊杰哥哥的板子 二维基础 特殊值与精度 无穷 $1.0/0.0=\operatorname{INFINITY},1.0/0.0=\operatorname{-INFINITY}$ 非数 $0.0/0.0 =\operatorname{NAN}$ 要注意,$\operatorname{NAN} (\ge,\le,>,<,= ) …