标签: ACM

19 篇文章

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$ 的两棵不…
【自主命题】牛客小白月赛 89 题解
这是第一场所有赛题都由我命制的公开比赛,也是第二场我参与命题的公开比赛。 比赛时由于内测下来大家都觉得 D 比 E 难,就更换了 DE 的顺序,本篇题解中没有发生更换,望读者注意。 比赛链接:Link. A. 伊甸之花 题目链接:Link. 若乐曲中同时存在 $1$ 和 $m$ 则无解,否则一定可以通过整体上移/下移一个音调来满足条件,时间复杂度 …
【整理】算法竞赛数据结构学习笔记
区间信息维护 前缀和与差分 多维前缀和 多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。 例如二维前缀和求法: $sum_{i,j}=a_{i,j}$ $sum_{i,j}+=sum_{i-1,j}$ $sum_{i,j}+=sum_{i,j-1}$ 例题:NC225630 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…
[Practice]算法竞赛小东西简记
分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma …
[Competition]大学算法竞赛比赛记录册
团队赛 队伍信息 队名:普罗旺斯 / Lavender Field 成员:water_tomato, 514inparadox, temp6 2024 CCPC 网络预选赛 链接:Link 时间:24.9.8 过题数:10/12 排名:48/($\approx$ 2100) 2024 ICPC 网络预选赛 I 链接:Link 时间:24.9.15 …