参考：p_z_y 的博客，YellowBean 的代码启示。 尽量写短点。 dsu on tree 模板题：CF600E Lomsat gelral。 题意： 有一棵 $n$ 个结点的以 $1$ 号结点为根的有根树。 每个结点都有一个颜色，颜色是以编号表示的， $i$ 号结点的颜色编号为 $c_i$。 如果一种颜色在以 $x$ 为根的子树内出现次数…

文/流凡 20210118 作 神伤黯黯闻驹白， 却问谁言可弄潮。 生死勾销君一笔， 时光霎道夜潇潇。

第一道题 CF1515I Phoenix and Diamonds 题目链接。 题意（5s,1000MB）： $n$​ 种钻石，一颗第 $i$​ 种钻石重量为 $w_i$​，价值为 $v_i$​，一开始第 $i$​ 中钻石的库存为 $a_i$​。接下来进行 $m$​​ 次操作： 1 k d：进货了 $k$ 个种类为 $d$ 的钻石； 2 k d：卖…

题意 题目链接。 给定一个长度为 $n$ 的环，有 $k$ 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。 解析 先考虑如果是链的话就是一个朴素的贪心：每次在所有左端点不大于当前位置的点中选取一个右端点最大的跳过去。对于环，容易想到将其断开，在其后面复制一份即可。 问题转化为了一个长度为 $2n$ 的链，求最少数量的区域使其能够覆盖长度至少为 …

参考：泥土笨笨的博客，Leap_Frog 的博客。 好久没写学习笔记了啊…… 珂朵莉树 模板：CF896C Willem, Chtholly and Seniorious。 题意： 给定一个序列，支持区间加，区间赋值，询问区间第 $k$ 小，区间幂次和（即 $x$ 次方的和，取模）。 数据范围 $10^5$，数据随机。 珂朵莉树（Chtholly …

题目链接。 解析 考虑最终序列。由于序列较长，先考虑序列短小的情况，即长度为 $3$ 时。 对于一个长度为 $3$ 的序列 $S_{1,2,3}$，要使其不存在回文串，需要满足 $S_1\neq S_2,S_2\neq S_3,S_1\neq S_3$，你发现这三个字母必须是互不相同的，由于字符串仅由三种字母组成，最终序列的前三个字母一定是以下六种…

题意 题目链接。 数轴上有若干传送门，初始是关闭或开启。对于关闭的传送门，经过后就会开启；对于开启的传送门，到达后会被传送到一个位置，然后会关闭。求从 $0$ 点走到 $x_n+1$，即最后一个传送门右边一格的所需时间。 解析 首先离散化。然后记 $f_i$ 为被在 $i$ 点的传送门传走再走回到 $i$ 点的时间。若该位置没有传送门，则记 $f_…

题意 题目链接。 有 $n$​ 行 $m+1$​ 列格点，第 $1$​ 列和第 $2$​ 列格点之间有 $e$ 条边，第 $i$ 条边的边权为 $c_i$，保证联通。第 $i$ 与 $i+1$ 列中的边是由第 $1$ 列和第 $2$ 列的边复制得到的。对于前 $i$ 列（$2 \le i \le m+1$），求对于前 $i$ 列的点与端点都在前 $…

题意 题目链接。 有两组物品，每个物品都有一定的价值，你需要选择若干个物品，收益为两组物品中价值和较少的那组物品的价值和减去所选取的所有物品数。使收益最大化。 解析 发现肯定优先选择价值高的物品。 发现如果已经选择了若干个物品，接下来那个物品只有选择当前总价值低的那一组才有可能有更优解。 由上，本题可以用双指针解决。对于两组物品分别用一个指针维护，…

引用/参考：绍兴一中相关课件，Acfboy 的博客。 决策单调性 决策单调性指的是 dp 的决策时的最优位置是单调的。 常见地，若存在： $dp_i = f(dp_j)$ 中，$i$ 的决策位置是 $pos_i$，那么对于所有 $i\ge2,pos_i \ge pos_{i-1}$。 难点在于观察(猜)出其为决策单调，经常可以不证明。一般通过打表观…