题意 题目链接 有 $n$ 种有体积和价值的物品和一个容量为 $m$ 的背包,每种物品有无数多个。 记第 $i$ 中物品最终在背包里放了 $a_i$ 个,我们需要这个答案序列先单调非降再单调非升,即有一个 $k$ 使得答案数列呈现 $a_1\le a_2\le \dots \le a_k \ge \dots \ge a_n$。 对于每一个背包容量 …
题意 题目链接。 给你一棵树,你可以在树上连两条边,这两条边会分别形成两个环,要求这两个环没有任何相同的边或结点,求连边的方案数。 解析 蛮有趣的一个树形 dp。 考虑对于所有的连边方案,在这四个点的 LCA 处进行统计。那么我们考虑对于一个点 $u$ ,有多少方案是以其为 LCA 的,发现共有以下几种情况: $2-2$ 结构:在 $u$ 的两棵不…
这是第一场所有赛题都由我命制的公开比赛,也是第二场我参与命题的公开比赛。 比赛时由于内测下来大家都觉得 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 智乃酱的子集与超集。 数列上加多项式 给一个数列的一部分连续…
分层并查集 P2024 [NOI2001] 食物链。 并查集通过分层可以有效用于逻辑关系,相同的思路还可以用于动态判断当前图是否为二分图。 异或方程组 例题。 有一个 key 点是奇偶性问题可以转化为异或问题。例如判断分成两块,就可以给其中一块的所有点标记为 $1$,另一块所有点标记为 $0$,这样对于每个点只需要进行一些异或运算 $\Sigma …
团队赛 很快就会有了 个人赛 CodeForces Pinely Round 3 (Div. 1 + Div. 2) 链接:Link 时间:23.12.23 分数:4109(solved:4/10) 排名:963/10976 Rating 变化:2006->2006 简评: 我好菜。 BC 观察+猜想 D 从假设目标已有的情况反推,可以发现玄妙之处…