• 欢迎光临~

2022.7.18 做题记录

开发技术 开发技术 2022-07-18 次浏览

Luogu3863 序列 Future 7.0

给定一个长度为 (n) 的序列,给出 (q) 个操作,形如:

(1~l~r~x) 表示将序列下标介于 ([l,r]) 的元素加上 (x) (请注意,(x) 可能为负)

(2~p~y) 表示查询 (a_p) 在过去的多少秒时间内不小于 (y) (不包括这一秒,细节请参照样例)

开始时为第 (0) 秒,第 (i) 个操作发生在第 (i) 秒。(1le n,qle 10^5)

考虑一个 (ntimes q) 的矩阵 (A),其中 (A_{i,j}) 存的是序列中第 (i) 个数在第 (j) 时刻的值。

对于一个修改操作,相当于将 (A) 的第 (lsim r) 行在 ([t,q]) 范围内全部 (+k)

查询操作则相当于查询矩阵一行内某个区间内 (ge y) 的数的个数。

我们将时间与序列顺序反演,依次扫过 (1sim n)(A) 的每一行,同时处理相应的操作。

对于修改,考虑套路地差分掉,在第 (l) 行处设置一个区间加操作,在 (r+1) 行处减掉。

对于查询,不难发现这等价于区间 ([0,i-1])(ge k) 的数的个数。

这是经典分块问题,把每一块分别排序后二分即可。不妨设 (n,q) 同阶,则时间复杂度 (O(nsqrt{nlog n}))。AC Code

UVa10559 Blocks Future 7.5

(n) 个带有颜色的方块,消除一段长度为 (x)连续的相同颜色的方块可以得到 (x^2) 的分数。

你需要用一种最优的顺序消除所有方块,使得得分最多。(1le nle 200)

例:(12233321to 12221to 11to varnothing),得分为 (3^2+3^2+2^2=22)

考虑设 (f(l,r)) 为消除 (l,r) 所能得到的最大得分。

按照套路我们先考虑使用 (f(l,k),f(k+1,r)) 来转移 (f(l,r)),但这样并没有涵盖所有的操作。

我们有可能先把 ([l,k])([k+1,r]) 内消到各剩下一些,然后拼起来消掉,这种操作是没有被考虑到的。

实际上这个 DP 设的就有些问题:(12233321) 消掉 (333) 后变成 (12221),这样的子串是从来没有被考虑过的。

我们考虑枚举「第 (r) 个方块什么时候被消掉」。

(p) 是最小的满足 ([p,r]) 内方块颜色均相等的正整数,那么有两种可能的方案:

  • 直接消去 ([p,r])
  • 找到 (q) 使得第 (c_q=c_r),消去 ([q+1,p-1]),再消去 (c_q)(c_{pcdots r})。其中 (c) 为颜色序列。

但第二种决策仍然有些问题:我们不一定在消去 ([q+1,p-1]) 后立刻消除 (r),而是有可能在右边再消去一些方块,然后一起消去。

我们发现消去 ([q+1,p-1]) 后此时的序列变成了「一段区间最右边添上若干个和最右端颜色相等的方块」。

考虑把这种状态写进 DP:设 (f(l,r,k)) 为考虑区间 ([l,r]),在最右端把 (c_r) 复制 (k) 份后得到的颜色序列,的答案。

这样一来有两种转移:

  • 直接消去 ([p,r]),分数为 (f(l,p-1,0)+(r-p+k+1)^2)
  • 找到 (q) 使得 (c_q=c_r),先消去 ([q+1,p-1])。分数为 (f(l,q,r-p+k+1)+f(q+1,p-1,0))

一些思考:

  • 这个状态也没有涵盖所有能得到的子序列啊,为什么就是对的?

确实没有涵盖所有可能的状态,但,这个状态涵盖了所有最优解能到达的状态

例如,对于 (f(l,r,k)),我们的确可能先消掉 ([l,r]) 中间的某些方块,再来看最右端的方块。

但不管怎么样,我们总要消掉 (r) 和后面那 (k) 个同色方块。因此,「先消掉谁」其实并没有那么要紧。

相当于我们可能有两种操作方式:(Ato Bto D)(Ato Cto D),我们确定了 (Ato Bto D) 一定不劣,因此就只需记录 (Ato Bto D) 就行了。

  • 为什么要先找到 (p) 满足 ([p,r]) 都相等,再做进一步的转移?直接考虑 (r) 自己不行吗?

因为如果直接考虑 (r),那么将导致我们直接拆掉了 ([p,r]) 这个连续段,考虑不到更优的状态。

一共有 (O(n^3)) 个状态,转移复杂度 (O(n))。总的复杂度为 (O(n^4))

注意到如果用记忆化搜索实现,大多数状态实际上转移不到,足够通过 (n=200) 的测试点。AC Code

写了两道题之后发现今天有 cf,于是去刷了一会 B 站打算晚上打个 cf()

CF1706E Qpwoeirut and Vertices Present 7.0

给定一个 (n)(m) 边的无向图,有 (q) 次询问,每次给定 (l,r),你需要输出最小的 (k),满足:

  • 如果只保留图中的第 (1,2,cdots,k) 条边,那么对于任意的 (lle a,ble r),点 (a,b) 仍然连通。

(1le nle 10^5,1le m,qle 2times 10^5)

首先套路地求个最小生成树,那么两点最早连通的时刻就是链上边权 (max)

现在相当于给出点集 (l,r),设 (E(i,j))(ito j) 路劲上边所构成的集合,要求出来边集

[bigcup_{lle x,yle r}E(x,y) ]

中的边权最大值。

我们可以用线段树维护虚树,得到一个 2log 的愚蠢大常数做法。

看到树上边权最值一类问题,考虑并查集:我们依次从小到大加入每一条边,那么 (E(x,y)) 的最大值就是 (x,y) 所在集合第一次被合并时该边的边权。

这启发我们在合并两个集合的时候,新建一个点 (u),从 (u) 向两个集合所代表的的点连边。令 (u) 的点权为其对应边的边权,那么 (E(x,y)) 中的最大值就是 (x,y) 在新树上的 (text{LCA}) 的点权。

那么现在只需要求一个区间 (text{LCA}) 就行了。这个可以随便做。

我一开始为了追求 1log 写了个 (text{ST}) 表求两点 (text{LCA}),再用 (text{ST}) 表求区间 (text{LCA}),后来发现常数巨大。。把求两点 (text{LCA}) 改成树剖立马快了五倍。。启示:求 (text{LCA}) 一定要写树剖!!!!

AC Code

UPD:场后发现这东西好像叫 (text{kruskal}) 重构树?所以我在场上发明了一个 (text{kruskal}) 重构树???

程序员灯塔
转载请注明原文链接:2022.7.18 做题记录
喜欢 (0)