CF1208F Bits And Pieces 题解
题意 题目链接。 给你一个由 $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,>,<,= ) x$ 结果均为 False,只有…
CF1973D(CFR 945) Cat, Fox and Maximum Array Split 题解
题意 题目链接。 交互题。 狐狸给你两个正整数 $n,k$,并且她有一个长度为 $n$ 的隐藏数组。对于一段区间 $(l,r)$,其价值 $f(l,r)$ 等于长度乘以区间最大值。 你有 $2n$ 次查询次数,每次查询形如 ? l x,狐狸会告诉你一个数 $r$,表示最小的满足 $f(l,r)=x$ 的 $r$,或是 $n+1$ 表示不存在 $r$…
Codechef Starters 133 Fireworks 题解
题意 题目链接。 使用 coze.com 的 gpt-4 进行翻译和格式美化. 给定一个包含$N$个顶点的树$T$,设$F$是$T$的顶点的一个子集,如果$F$满足以下条件,则称$F$为$x$根火花: $F$包含顶点$x$ - $F$是$T$的连通子图——也就是说,由$F$导出的子图$T[F]$是连通的。 令$d_F(u)$表示节点$u$在$T[F…
Codechef Starters 133 Too Far For Comfort 题解
题意 题目链接。 使用 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…
2024 CCPC Final Chengdu (第九届 CCPC 总决赛): A 题 – Add One 2 题解
题意 题目链接。 给定一个序列 $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 …