【整理】算法竞赛动态规划学习笔记
一些动态规划类型 树形 DP 树形 dp 的常用方法(例如树上背包)是将接下来要处理的儿子与以及处理完的儿子的全体进行合并,即把处理多个子树的问题转换为依次合并两个儿子的问题。 树形 dp 类型众多,故这里不多做赘述。 状压 DP 状压 dp 的核心是把状态用二进制数进行压缩(有些时候可能会用到四进制,如果一个点有三种或四种状态)。处理状压 dp …
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 …
牛客练习赛123 D 智乃想考一道完全背包(Hard version) 题解
题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包,每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个,我们需要这个答案序列先单调非降再单调非升,即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …
Codechef Starters 126 Uncommon Cycles 题解
题意 题目链接。 给你一棵树,你可以在树上连两条边,这两条边会分别形成两个环,要求这两个环没有任何相同的边或结点,求连边的方案数。 解析 蛮有趣的一个树形 dp。 考虑对于所有的连边方案,在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ,有多少方案是以其为 LCA 的,发现共有以下几种情况: $2-2$ 结构:在 $u$ 的两棵不…