2020.11.13笔记

2020.11.13笔记

CSP-S2周末刷题班（第四场）

A

考虑应该按照什么样的顺序打怪。

若有两个怪物 $x, y$。

按照两种顺序打怪对血量的影响分别是$-D_x+C_x-D_y$ 和 $-D_y+C_y+D_x$。

所以说应该让 $C$ 较大的靠前。

然后背包即可。

B

题意看起来很迷惑。

最终要求的东西是 $Tarjan$ 缩点之后的最长路径，这条路径上大小为 $1$ 的强连通分量不计入长度。

特别地，如果一个强连通分量不是简单环，则答案为 $-1$。

C

一开始想了个错误的假贪心。

暴力的做法是枚举所有的 $i$ 作为右端点，然后求出左端点最优可以是多少。

对于 $i < j$，则 $j$ 可以延伸到的左端点一定不比 $i$ 远，这也就意味着左端点有单调性。

对于当前的左端点 $i$，判断的过程相当于是求出左边第一个 $j$，满足 $l_j > r_j$，结合左端点的单调性，使用单调队列维护区间最大值即可。

D

对我来说是很难的一道计数 $DP$。

首先需要进行一些观察，观察原来的排列 $P$ 和新的序列 $S$ 的联系。

• $P$ 中的第 $i$ 个元素，若保留下来，则在 $S$ 中必定是一个连续的区间，且左右最多扩展到第一个比 $p_i$ 大的位置。
• 保留下来的 $p_i$ 的相对顺序一定是不变的。

利用上面两个性质，区间连续且相对顺序不变，则可以进行 $dp$。

设 $f_{i, j, k}$ 表示考虑 $P$ 中的前 $i$ 个元素，$S$ 中的前 $j$ 个元素已经放好了，已经用了 $k$ 步的方案数。转移考虑是否保留，保留的话延伸到哪里即可。

CSP-S2周末刷题班（第五场）

A

考虑枚举 $k$，然后计算不合法的 $i, j$。

不合法的应该满足 $i \times j < k$。

$i \times j$ 可以提前预处理出来，复杂度是 $O(n \log n)$ 的，然后前缀和即可。

B

题面里非常重要的细节是 $p$ 为奇数且是无向连通图。

对于一条长度为 $l$ 的边，可以无条件地走偶数次，也就是 $2lk$。

那么下面的式子一定有解。

$$2lk + k’p = \gcd(l, p)$$

也就是说所有 $\gcd(l, p)$ 的倍数都可以被表示出来。

同理，推广到多条边也是适用的。

因此只需要检查 $\gcd(w_1, \dots, w_n, p)$ 是否是 $L$ 的因子即可。

C

初步的的想法是使得 $A, B$ 在 $\mod P, \varphi(P)$ 意义下都相等。

即为：

$$A \equiv B \mod P$$
$$A \equiv B \mod \varphi(P)$$

也就是说 $xP = y \varphi (P)$。

直接使得 $x = \varphi(P),y=P$即可。

则 $B = A + P \times \varphi(P)$。

D

题目里的存在一个 $j$显然可以转化成直接使用最靠右的 $j$ 进行判断。

对于一对 $i, k$，有如下限制：

$$i + d_i \geq k - d_k \tag1$$
$$i + 1 < k \tag2$$
$$i + d_i \geq \frac{i + k}2\tag3$$

$(3)$ 可以化成 $i + 2d_i \geq k$。

观察上面的式子，可以发现是三维偏序问题，可以直接使用 $cdq$ 分治做到 $O(n \log ^ 2 n)$。

数据范围是 $3 \times 10^6$，三维偏序无法通过。

上面做法的问题在于，如果单纯从 $k$ 的角度去统计答案，则 $i+d_i, i+2d_i$ 之类的变量太多了，需要分别使用两个维度进行解决。

正解的做法是从 $i$ 考虑会影响哪些 $k$。

可以发现对于一个 $i$，被其影响的 $k$需要满足 $k \in [i+2, \min{n,i + 2d_i }]$。

因此可以类似扫描线一样，从前到后枚举一个 $k$，然后删除和插入 $i$ 的影响（具体插入到 $i+d_i$ 的位置），同时处理完删除和插入之后，查询 $[k-d_k, n]$ 的和。