题意 题目链接。 给你一个由 $n$ 个整数组成的数组 $a$ 。 你需要在所有三元组 $(i,j,k)$ 中找出 $a_{i} | ( a_{j} \& a_ {k} )$ 的最大值，使得 $i < j < k$ . 这里 $\&$ 表示 位与运算，而 $|$ 表示 位与运算。 由 Codeforces Better!…

KMP KMP 是一种用于两个字符串匹配的算法。其核心概念是 Border ，即一个字符串同长度的完全相同的前后缀（通常不含自身）。 KMP 的做法是先求出要匹配的字符串（短串）的所有前缀的最长 Border，然后在于长串进行匹配，并在无法匹配时跳转到其 Border 进行再次尝试匹配。详细方法可以参考我之前的学习笔记。 有时也会用 $next_i…

一些动态规划类型 树形 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,>,<,= ) …

题意 题目链接。 交互题。 狐狸给你两个正整数 $n,k$，并且她有一个长度为 $n$ 的隐藏数组。对于一段区间 $(l,r)$，其价值 $f(l,r)$ 等于长度乘以区间最大值。 你有 $2n$ 次查询次数，每次查询形如 ? l x，狐狸会告诉你一个数 $r$，表示最小的满足 $f(l,r)=x$ 的 $r$，或是 $n+1$ 表示不存在 $r$…

题意 题目链接。 使用 coze.com 的 gpt-4 进行翻译和格式美化. 给定一个包含$N$个顶点的树$T$，设$F$是$T$的顶点的一个子集，如果$F$满足以下条件，则称$F$为$x$根火花： $F$包含顶点$x$ - $F$是$T$的连通子图——也就是说，由$F$导出的子图$T[F]$是连通的。 令$d_F(u)$表示节点$u$在$T[F…

题意 题目链接。 使用 coze.com 的 gpt-4 进行翻译和格式美化. 一个长度为$M$的数组$A$被称为前缀平衡，如果它满足以下条件： 让$S_A$表示在$A$中出现的所有元素的集合。 对于每个$x \in S_A$，和索引$i(1 \leq i \leq M)$，让$f_i(x)$表示$x$在$[A_1, A_2, \dots, A_i…

题意 题目链接。 给定一个序列 $y$​, 初始有一个全零序列 $x$​。每次可以选择一个长度为 $k$​ 的前缀或者一个长度为 $k$​ 的后缀将其加一，代价是 $k$​。问最少需要多少代价能使得对于所有 $i$​ 都满足 $b_i\geq a_i$​。 序列的长度范围为 $1 \le n \le 10^6$。 解答 Key 1: 考虑什么情况下…

这个笔记想写得稍微详细一点，部分内容来自我自己之前的博客: OI 里的数学内容整理（提高组）。 其中一些公式是 AI 从 PPT 上识别的，格式混乱，还请谅解。 整数分解与筛法 欧几里得算法 用于求解两个数的最大公因数。 $\gcd(a,b)=\gcd(b,a\bmod b)$。 int gcd(int a,int b){ return b==0?…

图匹配 二分图匹配 判定 静态：黑白染色。 动态：分层并查集。并查集可以维护的可以是点的连接关系，也可以是关系的连接方式。连接两个点，我们可以改为连接这两个点的逻辑关系，黑-白，白-黑。如果有一天同一个点的黑白被连在了一起，则这就不是一个二分图。 分层并查集经典例题：P2024 [NOI2001] 食物链。 最大匹配：匈牙利算法 模版：P3386 …