## 限时回归 真的受不了了 一个蓝桥杯省一等奖学校发3000你受的了吗？ 这还不复健打比赛？ ## A 不解释 ## B 不解释 ## C 不解释 ## D 随便宽搜一下，每次找到更短的路径的时候更新一下。小技巧是把那个记录方向的字符数组交换一下位置即可轻松实现。 ## E 一开始想到的是设 $f_{i,j}$ 表示第一个 C 在 $i$ 第一个 D 在 $j$ 这样的方案数。实际上是可行的。问题在于 D 的位置我们实际上不关心。因为，当 A 和 C 完全放完的时候，只有 $B+D$ 个位置留给 B 和 D 了。那么他们的放置方案唯一确定。 因此答案就是 $$ \sum_{i=A}^{A+B} \binom{i - 1}{A - 1} \binom{N - i}{C} $$ 钦定第一个C的位置实际上等价于钦定最后一个 A 的位置。假设最后一个 A 在 $i$，那么前 $i-1$ 个位置要选 $A-1$ 个位置放 A，剩下的 $N - i$ 个位置选 $C$ 个出来放 C 即可。 ## F 没绷住。 首先看下暴力。假设一条线段 $[a,b]$ 跟另外一条线段$[l,r]$有交，那么意味着 $a \in [l, r] \land b \in [1, l) \cup (r, 2n]$ 也就是 $a < l < r < b$ 或者 $b < l < a < r$ 实际上就拆成了两个偏序问题。首先把所有的询问离线下来，和所有的给定的线段一起按照左端点排序。那么，假如当前线段是给定的线段，就可以在其左端点的位置上 +1，如果是询问的线段，那么只要查 $[a,b]$ 内覆盖了多少个给定线段的左端点即可。类似的，再按照有端点排序。查每一个询问线段覆盖了多少有右端点即可。 ## G 首先还是想着往 $\log$ 的数据结构上靠，但是发现一个问题是，比如这里要用线段树，那考虑节点合并信息的时候是要套个 set 来处理的。那合并两个 set 的复杂度是 $O(n\log n)$，然后还要在用一个 $\log$ 来找最后一个 $\leq x$ 的索引。这样显然就复杂度爆炸了。 那考虑一下根号数据结构。这里肯定是考虑莫队了。可以是先把所有的询问离线下来，然后看看从 $[l,r]$ 扩展到邻近区间的答案的操作。 我们在值域上开块（值域 $2 \times 10^5$），那么每一次更新，首先更新 `cnt[x]` 表示当前莫队指针区间中 $x$ 的个数，然后更新 `b[bel[x]].sum` 表示 $x$ 所属的块的和。细节操作是这样，考虑简单组合数学。假设当前有 $m$ 个不同的元素，每个元素有 $cnt_i$ 个，那么不同的排列数就应该是 $$ \frac{m!}{\prod cnt_i!} $$ 因此，莫队也维护一下这个信息即可。具体操作看代码。 [Submission](https://atcoder.jp/contests/abc405/submissions/65775743) 此外，复健的时候发现OI-Wiki对莫队的总结还挺到位的，抄一下： > 这4种正确写法的共同特点是，前两步先扩大区间（`l--`或`r++`），后两步再缩小区间（`l++`或`r--`）。这样写，前两步是扩大区间，可以保持 ；执行完前两步后， 一定成立，再执行后两步只会把区间缩小到 ，依然有 ，因此这样写是正确的。 Loading... ## 限时回归 真的受不了了 一个蓝桥杯省一等奖学校发3000你受的了吗？ 这还不复健打比赛？ ## A 不解释 ## B 不解释 ## C 不解释 ## D 随便宽搜一下，每次找到更短的路径的时候更新一下。小技巧是把那个记录方向的字符数组交换一下位置即可轻松实现。 ## E 一开始想到的是设 $f_{i,j}$ 表示第一个 C 在 $i$ 第一个 D 在 $j$ 这样的方案数。实际上是可行的。问题在于 D 的位置我们实际上不关心。因为，当 A 和 C 完全放完的时候，只有 $B+D$ 个位置留给 B 和 D 了。那么他们的放置方案唯一确定。 因此答案就是 $$ \sum_{i=A}^{A+B} \binom{i - 1}{A - 1} \binom{N - i}{C} $$ 钦定第一个C的位置实际上等价于钦定最后一个 A 的位置。假设最后一个 A 在 $i$，那么前 $i-1$ 个位置要选 $A-1$ 个位置放 A，剩下的 $N - i$ 个位置选 $C$ 个出来放 C 即可。 ## F 没绷住。 首先看下暴力。假设一条线段 $[a,b]$ 跟另外一条线段$[l,r]$有交，那么意味着 $a \in [l, r] \land b \in [1, l) \cup (r, 2n]$ 也就是 $a < l < r < b$ 或者 $b < l < a < r$ 实际上就拆成了两个偏序问题。首先把所有的询问离线下来，和所有的给定的线段一起按照左端点排序。那么，假如当前线段是给定的线段，就可以在其左端点的位置上 +1，如果是询问的线段，那么只要查 $[a,b]$ 内覆盖了多少个给定线段的左端点即可。类似的，再按照有端点排序。查每一个询问线段覆盖了多少有右端点即可。 ## G 首先还是想着往 $\log$ 的数据结构上靠，但是发现一个问题是，比如这里要用线段树，那考虑节点合并信息的时候是要套个 set 来处理的。那合并两个 set 的复杂度是 $O(n\log n)$，然后还要在用一个 $\log$ 来找最后一个 $\leq x$ 的索引。这样显然就复杂度爆炸了。 那考虑一下根号数据结构。这里肯定是考虑莫队了。可以是先把所有的询问离线下来，然后看看从 $[l,r]$ 扩展到邻近区间的答案的操作。 我们在值域上开块（值域 $2 \times 10^5$），那么每一次更新，首先更新 `cnt[x]` 表示当前莫队指针区间中 $x$ 的个数，然后更新 `b[bel[x]].sum` 表示 $x$ 所属的块的和。细节操作是这样，考虑简单组合数学。假设当前有 $m$ 个不同的元素，每个元素有 $cnt_i$ 个，那么不同的排列数就应该是 $$ \frac{m!}{\prod cnt_i!} $$ 因此，莫队也维护一下这个信息即可。具体操作看代码。 [Submission](https://atcoder.jp/contests/abc405/submissions/65775743) 此外，复健的时候发现OI-Wiki对莫队的总结还挺到位的，抄一下： > 这4种正确写法的共同特点是，前两步先扩大区间（`l--`或`r++`），后两步再缩小区间（`l++`或`r--`）。这样写，前两步是扩大区间，可以保持 ；执行完前两步后， 一定成立，再执行后两步只会把区间缩小到 ，依然有 ，因此这样写是正确的。 最后修改：2025 年 05 月 14 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
1 条评论
暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%暴力膜托%%%