标签: ICPC

7 篇文章

【整理】算法竞赛动态规划学习笔记
一些动态规划类型 树形 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…
[Practice]算法竞赛小东西简记
分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma …
[Competition]大学算法竞赛比赛记录册
不知道过了多久,似乎是时候开始回归之路了。 CodeForces Pinely Round 3 (Div. 1 + Div. 2) 链接:Link 时间:23.12.23 分数:4109(solved:4/10) 排名:963/10976 Rating 变化:2006->2006 简评: 我好菜。 BC 观察+猜想 D 从假设目标已有的情况反推,可…