CF2051 题解

沉石鱼惊旋 · 2024-12-23 11:13:35 · 题解

我觉得这场 Div.3 难爆了。

A. Preparing for the Olympiad

考虑贪心。对于所有的 a_i\geq b_{i+1}，选上之后答案不劣。不会让自己比 Stereocarp 少做题。a_n 必选，因为 Stereocarp 第二天就已经过了期限了。对所有的 a_i\geq b_{i+1} 的 a_i 求和，再加上 a_n 即为答案。

好吧我也不知道为什么 Div.3 的 A 这么难。

https://codeforces.com/contest/2051/submission/297813124

B. Journey

数据范围如此大考虑 \mathcal O(1) 的数学做法。

先算出需要的周期个数是 \lfloor\frac{n}{a+b+c}\rfloor。则 \lfloor\frac{n}{a+b+c}\rfloor\times 3 天是周期内的答案。之后考虑 n\bmod (a+b+c) 也就是剩余路程的大小。自己模拟这个周期的跑步流程。

答案是 \lfloor\frac{n}{a+b+c}\rfloor\times 3+[n\bmod (a+b+c)\gt 0]+[n\bmod (a+b+c)-a\gt 0]+[n\bmod (a+b+c)-a-b\gt 0]。

https://codeforces.com/contest/2051/submission/297815421

C. Preparing for the Exam

分类讨论 k 和 n 的关系。

答案全 0 和全 1 可以先特判掉。全 0 即 k\leq n-2，全 1 即 k=n。

除了这两种只有 k=n-1 的情况了，我们求出他不会的那一门，可以直接开桶记录，或者算 x=(\bigoplus\limits_{i=1}^n i )\oplus (\bigoplus\limits_{i=1}^k q_i )。由于异或的性质我们可以知道最后答案就是遗失的那个数。

对于 m 个询问，答案为 [x=a_i]。

https://codeforces.com/contest/2051/submission/297822232

D. Counting Pairs

枚举一个 a_i，设 s=\sum\limits_{i=1}^n a_i，那么我们就是要找 a_j 的数量满足 x \leq s - a_j \leq y，移项得到 s - y \leq a_j \leq s - x。

把数组复制一份一样的 b 进行排序，通过二分求出满足条件的 s - y \leq b_j \leq s - x 的 j 的范围。那么 a_i 和这些 b_j 都可以满足条件。如果 b_j 里包含了 a_i 要减掉一的贡献。

这里计算的是无序对的数量，有序对数量除以二即可。

https://codeforces.com/contest/2051/submission/297830381

E. Best Price

一个发现是，单价只可能在 a_i 和 b_i 这 2n 个数中产生。

因为 a_i 和 b_i 是一个能接受的最大程度，我们要尽可能多地压榨（？）顾客。

将 a,b 分别排序。设目前枚举的单价是 c，通过二分找到 \geq c 的 b_i 的个数 B。那么这些人就是可能会给出差评但是一定会买的人数。

剩下的人不可能买了，考虑这些可能给出差评的人是否会给出好评。好评同理，\geq c 的 a_i 的个数 A 就是一定给出好评并且购买的人。如果 B-A\leq k 说明这个单价是合理的。c\times B 即为这个单价会购买的人产生的总花费。枚举所有的 c 依次算出 A,B，如果 B-A\leq k 则对 c\times B 取 \max 即可。

https://codeforces.com/contest/2051/submission/297848639

F. Joker

本场最后过的这题/xk

实现。

维护集合 pos 表示目前 Joker 可能处在的位置的集合。

每次操作第 x 个位置就是考虑哪些位置可能前移，哪些位置可能后移，哪些位置可能被新加入。

设有 y\in pos，如果 y\lt x 那么 y+1 可能成为新的答案（把 x 位置的卡牌放到第一个）；如果 y\gt x 那么 y-1 可能成为新的答案（把 x 位置的卡牌放到最后一个）；如果有 y=x 那么先从集合中删去 y，把 1 和 n 添加进来。

直接模拟这个过程 TLE on 8。详见 https://codeforces.com/contest/2051/submission/297931501。

分析这个做法的问题，就是一个位置可能本来就在集合里，但是被插进去太多次了。

我们维护两个可能成为答案的集合。分别表示通过 y+1 成为答案或者通过 y-1 成为答案。每次操作在集合中二分出这些位置，把它们全插到 pos 里。每次往 pos 里新插入的时候，判断是否有新的元素可能成为答案。删除的时候判断它是否有机会再次成为答案。

https://codeforces.com/contest/2051/submission/297945489

https://codeforces.com/contest/2051/submission/297946569

https://codeforces.com/contest/2051/submission/297947497

上面是三发不同的初始和加了卡常的版本。

G. Snakes

抽象题意毁我青春。

这个数据范围很诱人啊/se

这个数据范围无非就是往 \mathcal O(nq) 或者 \mathcal O(2^n) 什么复杂度上想。

但是如果复杂度是前者为什么不开 n\leq 3000，q\leq 3000。（x）

但是稍微想一下可以发现，如果我们知道的是 n 条蛇的初始顺序，我们可以在 \mathcal O(nq) 的时间求出这一组解的对应答案。但问题是我们没法枚举所有可能的初始位置。

但是这可以启发我们，我们可以先对所有的蛇的对，预处理出 a_{i,j} 表示：如果 i 蛇在 1，则 j 蛇的初始位置最早在 a_{i,j} 才合法。

这个位置是相对的，也就是如果蛇 i 在 x，蛇 j 最早在 x+a_{i,j}-1 才合法。

考虑怎么处理这个 a_{i,j}，有两种做法。

一种是二分答案，我一开始写的这个。观察到这个是单调的，直接二分然后模拟操作进行比较。如果有相交即为不合法。这里如果写的丑一点就会 TLE。丑一点的做法，指的是把 q 次操作都过一遍。这样子复杂度是 \mathcal O(n^2q\log V) 的。很难通过。

改的好一点就是你把每条蛇对应的操作存下来，然后归并这两条蛇。复杂度是 \mathcal O(nq\log V)。

这里 V 最无脑的取法就是 10^9。稍微分析一下发现其实 \mathcal O(q) 的范围就行了。常数可以再小一倍。

还有一种是，发现这个二分答案完全不必要。直接归并两条蛇的时候，算一下 j 蛇的 L 和 i 蛇的 R 的距离，取 \max。还是一样，存操作然后归并的话复杂度是 \mathcal O(nq)，把所有操作都过一遍是 \mathcal O(n^2q)。

预处理 a_{i,j} 之后直接套一个状压 DP 就行了。f_{S,k} 表示目前选出来集合为 S，最后一个选到的是 k，此时的 k 的最小开头。

注意求的内容不是最小开头是最小的覆盖位置，所有 \operatorname{popcount}(S)=n 的 DP 值要再加上一个最后的长度。

https://codeforces.com/contest/2051/submission/297903050

https://codeforces.com/contest/2051/submission/297908995

以上两份分别是归并二分答案和归并计算答案的两个版本。