思路 这是一道简单的 DP 题，DP 题的核心就是状态转移。 先来说一说 dpdpdp 数组的含义。 dpi,jdp_{i,j}dpi,j​ 表示从 iii 这个点用 2j2 ^ j2j 条线段能走到的最远的点。 我们再来考虑一下边界情况。 因为我们只用 202 ^ 020 条线段，那么：dpi,0=max⁡(dpi,0,r)dp_{i,0} = \max(dp_{i,0},r)dpi,0​=ma

CCF 出的原题观摩一下。 思路 首先可以用一个 Trie 来维护。 在这里对本文中的一些变量做一下说明。 ppp 表示当前维护的 Trie 中，指向的元素编号。 tit_iti​ 表示在 Trie 中编号为 iii 的元素在原序列中的值。 fif_ifi​ 表示在 Trie 中编号为 iii 的元素在 Trie 中的父节点。 viv_ivi​ 表示在 Trie 中编号为 iii 被遍历的次数。

模拟赛最后 151515 分钟想到的做法。 思路 首先有一个显然的贪心策略：我们放炸弹的地方要尽可能的使这个炸弹能影响到更多的怪上。 那么我们可以将对于一个怪 iii 能够影响到它的区间表示出来 [max⁡(1,li−d),ai+r][\max(1,l_i - d),a_i + r][max(1,li​−d),ai​+r]。 然后将这些区间排个序，可以粗略画出这样的图： 根据上文提到的贪心策略，

板子题，模拟赛场切了。 思路 线段树换根板子题。 因为需要求每一个点的答案，所以定义 dpidp_idpi​ 表示以 iii 为根的最长距离。 考虑将一个点 vvv 转化为根，树的形态会发生什么变化（假设 vvv 的父亲节点是 uuu）。 发现在 vvv 子树中的节点，距离都会减少 wu→vw_{u \to v}wu→v​，其它节点都会加 wu→vw_{u \to v}wu→v​。这个变化显然是可

比较符合 CCF 造数据水平的题。 思路 首先可以用两个 vector<pair<int,int>> v[N] 分别将每一行、每一列的元素的权值与编号存储下来。 那么可以对所有的 viv_ivi​ 按照权值从小到大排序。那么发现对于所有的满足 v[i][p].fst < v[i][q].fst 的 (p,q)(p,q)(p,q) 都可以建一条从 ppp 指向 qqq

思路 定义 dpidp_idpi​ 表示将前 iii 个分为若干段的价值总和。容易得到状态转移方程： dpi=∑j=1i−1dpj×(max⁡k=j+1i{ak}−min⁡k=j+1i{ak}) dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\}

思路 题目要求的是 max⁡a=1n{∑i=1a∑j=1aAj}\max_{a = 1}^{n}\{\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}\}maxa=1n​{∑i=1a​∑j=1a​Aj​}，所以我们将 ∑i=1a∑j=1aAj\sum_{i = 1}^{a}\sum_{j = 1}^{a}{A_j}∑i=1a​∑j=1a​Aj​ 化简一下，得： i×A1+(

思路 首先，不难看出一个规律，就是对于一个序列 aaa，如果它将操作所有以 xxx 为第一关键字的二元组，那么序列的 ax∼na_{x \sim n}ax∼n​ 将循环右移一位。（注意，在这里的 xxx 指的是在 1∼(n−1)1 \sim (n - 1)1∼(n−1) 中的任意一个定值） 那么，我们就可以将编号分别为 l∼rl \sim rl∼r 的这些二元组分为三组： (x1,y1)∼(x1

思路 因为 1≤n,q≤2×1051 \leq n,q \leq 2 \times 10^51≤n,q≤2×105，所以对于每一次查询的时间复杂度一定要达到 Θ(log⁡n)\Theta(\log n)Θ(logn)，甚至于 Θ(1)\Theta(1)Θ(1)。 一个最简单的想法，我们先统计出整个序列 aaa 的和 sumsumsum，然后答案是 ∣sum−x×n∣|sum - x \times

day -1 早上还上了了 114514114514114514 小时的文化课，下午开始上信息。 上课没讲什么东西，老师给我们讲了一些考场的规则就完了。 然后，背了一些奇奇怪怪的模板 貌似一直在灌水。 2:00 老师带我们去做核酸，机房奆佬 逸之为一逸 \color{red}{之为一}逸之为一 顺手买了 114514114514114514 点小零食。 最后，看了一些模板，比如说：dijk,spf