A

我们只需要发现 $n = 1\pmod {n-1}$,就可以用如下方式构造:

  1. 操作 $[1,n]$ 使得 $\forall i\in [1,n],(n-1)|a_i$
  2. 操作 $[2,n]$ 可以消去所有的元素
  3. 单独操作 $[1,n]$ 。

注意特判 $n=1$ 就好了。

B

设 $sm = \sum_{i=1}^n a_i,mx = \max_{i=1}^n \{a_i\}$。注意到这个操作实际上是每次找两个不同的堆的石子配对的过程,如果 $mx > \frac{sm}{2}$ 一定会剩下来最大值那一堆,所以先手一开始选择最大值就可以保证必胜。

所以我们知道 $mx > \frac{sm}{2}$ 是先手必胜局面。

接下来考虑如果 $mx < \frac{sm}{2}$,意思就是存在一种配对方式满足不同堆内的能两两配对,显然双方都想让自己操作后不出现 $mx > \frac{sm}{2}$ 的情况。所以每次肯定会操作当前能操作的石子中最大的,所以答案就和 $sm$ 的奇偶性有关了。

C

我们可以算出来位置 $i$ 需要传送和不需要传送的代价 $v_1,v_2$。首先一个直观的想法是我们先确定哪些地方是要传送走的,把这些位置标记为 $1$,然后发现 $1$ 形成了若干连通块,先考虑不包含 $n$ 位置的连通块:一个长度为 $x$ 的连通块需要额外的代价 $2(d-1)$(当然 $d=1$ 的时候是个例外,代价为 $2$)。

我们可以发现 $2\lceil\frac{d}{2}\rceil \leq 2(d-1),d \geq 3$,所以在连通块中的路径一种最优的方式是:

$$ 1 \to 2 \to 1 \to 2 \to 3 \to 4 \to 3 \to 4 \to 5 \to \ldots $$

所以我们可以设 $f_i$ 表示前 $i$ 个的答案,转移的时候枚举第 $i$ 个是否和第 $i-1$ 配对即可。

注意在 $f_n$ 的时候我们可以

$$ n-1 \to n \to n-1 $$

可以减少一个 $d$,特判即可。

D

首先这个题显然可以离散化,我们只需要考虑那些边界上有点的矩形的情况即可,最后就是每种情况简单乘上一些东西。

一个暴力的做法是去枚举上边界,下边界($x$ 维),那么上下边界有一些活动的区域满足包含的点还是一样的,设可以活动的区间长度分别是 $d_1,d_2$。

然后我们考虑设 $f_i$ 表示左边界坐标为 $i$ 的时候最小的右边界是什么,显然 $i$ 和 $f_i$ 都只需要考虑包含点的那些坐标,显然有 $\forall i < j,f_i < f_j$,所以就可以双指针预处理出来,答案就是(按照 $y$ 坐标排好序)

$$ d_1d_2\sum_{i=1}^L (y_{i-1}-y_i)(L-f_i) $$

这样复杂度是 $O(n^3)$ 的,过不了。

这样的问题我们就要去考虑加点或删点能不能快速维护。我们发现加点不好维护,于是考虑维护删点操作:

设我们删除的点为 $x$,设和它相同颜色的前驱和后继分别是 $pre,suf$。我们考虑有哪些点会被影响:显然只有 $x \in [i,f_i] \cap (pre,x]$, 的所有 $f_i$ 会被影响,由于 $f$ 单调,我们可以通过用线段树维护在线段树上二分和 set 维护找出这个区间。

接下来考虑会被怎么影响:对于所有满足条件的 $x$,都会做操作 $f_x = \max \{f_x,y_{suf}\}$。所以我们用吉司机线段树维护这个东西就好了。时间复杂度 $O(n^2 \log n)$。

思维难度不是特别高,但是细节真的多QAQ。。 写了我一天,还是码力太差了

E

这种题目都挺套路的,记录一下。

首先我们考虑如何判断是否有解:我们先考虑找出匹配的最小价值和最大价值、

我们考虑每条边的贡献,设边 $e$ 两边的点个数分别为 $x,y$,那么通过这条边的最大代价为 $\min\{x,y\}$,最小代价为 $\min\{x,y\} \bmod 2$。

看到一条边两边最小值为代价的时候,要第一时间想到以重心为根,这样能保证最小值就是子树和。

所以设根为 $rt$,设 $i$ 的子树大小为 $sz_i$,就能得到:

$$ \begin{aligned} \text{maxans} &= \sum_{i = 1}^n [i \neq rt]sz_i\\ \text{minans} &= \sum_{i=1}^n [i \neq rt]sz_i\bmod 2 \end{aligned} $$

我们首先注意到最大答案所有的匹配都经过了 $rt$,所以我们如果取两个点 $u,v,\text{lca}(u,v) \neq rt$,将它们俩配对,可以得到答案减少了 $2 \times dep_{\text{lca}(x,y)}$。

所以我们可以猜一下有解的充要条件是 $k \in [\text{minans},\text{maxans}],(maxans-k) \bmod 2 = 0$。

充分性显然,必要性可以通过如下构造证明:

首先注意到如果每次删除两个 $rt$ 的最大子树内的点,重心的其中一个一定也是 $rt$,于是我们考虑每次找到 $rt$ 的最大子树内的两个点 $u,v$,我们可以把它们配对,答案减少 $2 \times dep_{\text{lca}(u,v)}$,然后删除这两个点。而根绝贪心的思想,是我们每次肯定会选择能选择的 $dep_{\text{lca(u,v)}}$ 尽量大的点,也就是每次删除两个叶子。可以发现这样构造一定有解。

Last modification:September 23rd, 2020 at 08:13 pm
如果觉得我的文章对你有用,请随意赞赏