2021洛谷11月月赛1游记

2021洛谷11月月赛1游记

才打了 200 p t s 200 pts 200 pts，退步了。

传送门

【 L G R − 096 】 洛 谷 11 月 月 赛 I rm 【LGR-096】洛谷~11~月月赛~I~ 【LGR−096】洛谷 11 月月赛 I 

Prob A. Addition (Statement)

有一个初始长度为 n n n 的序列 a a a。你需要进行 n − 1 n − 1 n−1 次操作。每一次操作先选出两个相
邻的数 x , y x, y x,y 并删掉（原序列中 x x x 在 y y y 左边），再往原位置插入一个 x + y x + y x+y 或一个 x − y x − y x−y。求
n − 1 n − 1 n−1 次操作之后能最终剩下的数的最大值。 1 ≤ n ≤ 1 0 5 1 ≤ n ≤ 10^5 1≤n≤105, ∣ a i ∣ ≤ 1 0 9 |ai| ≤ 10^9 ∣ai∣≤109。

	分值	n n n	a b s ( a i ) abs(a_i) abs(ai​)	特殊性质
S u b t a s k 1 Subtask 1 Subtask 1	10 10 10	≤ 2 leq 2 ≤2	无特殊限制	无
S u b t a s k 2 Subtask 2 Subtask 2	20 20 20	≤ 100 leq100 ≤100	无特殊限制	无
S u b t a s k 3 Subtask 3 Subtask 3	5 5 5	无特殊限制	无特殊限制	a i ≥ 0 a_i ge 0 ai​≥0
S u b t a s k 4 Subtask 4 Subtask 4	30 30 30	无特殊限制	≤ 1 leq 1 ≤1	无
S u b t a s k 5 Subtask 5 Subtask 5	35 35 35	无特殊限制	无特殊限制	无

Subtask 1

输出 max ⁡ ( a 1 + a 2 , a 1 − a 2 ) max(a_1 + a_2, a_1 − a_2) max(a1​+a2​,a1​−a2​)。期望得分 10 10 10 分。

Subtask 2

区间 dp， f l , r , g l , r f_{l,r}, g_{l,r} fl,r​,gl,r​ 表示只考虑 [ l , r ] [l, r] [l,r] 时的最大/最小答案。
枚举 i i i 表示最后一次合并的位置，容易得出转移方程式：

​ f l , r = max ⁡ i − 1 r − 1 f l , i + f i + 1 , r , f l , i − g i + 1 , r f_{l,r} = maxlimits_{i-1}^{r-1}{f_{l,i} + f_{i+1,r}, f_{l,i} − g_{i+1,r}} fl,r​=i−1maxr−1​fl,i​+fi+1,r​,fl,i​−gi+1,r​

​ g l , r = min ⁡ i − 1 r − 1 g l , i + g i + 1 , r , g l , i − f i + 1 , r g_{l,r} = minlimits_{i-1}^{r-1}{g_{l,i} + g_{i+1,r}, g_{l,i} − f_{i+1,r}} gl,r​=i−1minr−1​gl,i​+gi+1,r​,gl,i​−fi+1,r​

时间复杂度 O ( n 3 ) mathcal{O}(n^3) O(n3)。期望得分 30 30 30 分。

Subtask 3

输出 ∑ i = 1 n a i sumlimits_{i=1}^{n}a_i i=1∑n​ai​。期望得分 5 5 5 分。

Subtask 4

输出 a 1 + ∑ i = 2 n ∣ a i ∣ a_1 + sumlimits_{i=2}^{n}|ai| a1​+i=2∑n​∣ai∣。

依次加入每一个数，假设当前答案是 x x x，新加入的数是 w w w。

如果 w < 0 w < 0 w<0 则 x − = w x− = w x−=w。否则 x + = w x+ = w x+=w。

显然这样可以得到最大答案。时间复杂度 O ( n ) mathcal{O}(n) O(n)。

Prob B. Lines (Statement)

平面直角坐标系中有 n n n 条直线，任意 3 3 3 条直线不交于一点且没有两条直线重合。现在
这些直线形成了不超过 n ( n − 1 ) 2 frac{n(n − 1)}{2} 2n(n−1)​ 个交点，请你求出至少选取其中几条直线才能覆盖到所
有交点。 1 ≤ n ≤ 1 0 5 , ∣ a ∣ , ∣ b ∣ , ∣ c ∣ ≤ 1 0 9 1 ≤ n ≤ 10^5, |a|, |b|, |c| ≤ 10^9 1≤n≤105,∣a∣,∣b∣,∣c∣≤109。

	分值	n n n	特殊性质
S u b t a s k 1 Subtask 1 Subtask 1	10 10 10	≤ 20 leq20 ≤20	无
S u b t a s k 2 Subtask 2 Subtask 2	30 30 30	≤ 100 leq100 ≤100	无
S u b t a s k 3 Subtask 3 Subtask 3	10 10 10	无特殊限制	a b = 0 ab=0 ab=0
S u b t a s k 4 Subtask 4 Subtask 4	50 50 50	无特殊限制	无

Subtask 1

暴力枚举每一条直线是否选择，判断是否合法。期望得分 10 10 10 分。

Subtask 2

假设 a = 0 a = 0 a=0 的有 t t t 条。输出 min ⁡ ( t , n − t ) min(t, n − t) min(t,n−t)。期望得分 10 10 10 分。

Subtask 3

没有删掉的直线一定是互相平行的，否则一定有至少一个交点没有被删掉。所以其实就是
要选出最多的直线使它们两两平行。
对于每一条直线暴力找出有多少条直线与它平行，取最大值即可。
时间复杂度 O ( n 2 ) mathcal{O}(n^2) O(n2) 或 O ( n 2 log ⁡ n ) mathcal{O}(n^2 log n) O(n2logn)。期望得分 40 40 40 分。

Subtask 4

对斜率排序或用 map 统计。时间复杂度 O ( n log ⁡ n ) O(n log n) O(nlogn)。期望得分 100 100 100 分。

C. ABC (Statement)

给定一个长度为 n n n 的只包含 A, B, C 的字符串 S S S，你可以进行若干次操作，每次操作为：

• 先选择一个区间 [ l , r ] [l, r] [l,r]，你需要保证 1 ≤ l ≤ r ≤ n 1 ≤ l ≤ r ≤ n 1≤l≤r≤n。

• 再选择三个字符 p A , p B , p C ∈ A , B , C pA, pB, pC in {A, B, C} pA,pB,pC∈A,B,C，并将 S l . . . r S_{l...r} Sl...r​ 中所有 A 变为 p A pA pA，所有 B 变为 p B pB pB，
  所有 C 变为 p C pC pC， p A pA pA, p B pB pB, p C pC pC 可以相等。

  你的目标是用最小的操作数使得任意相邻两个字符不同。要求构造方案。

  1 ≤ n ≤ 5 × 1 0 3 1 ≤ n ≤ 5 × 10^3 1≤n≤5×103。

Subtask 1

输出 0 0 0。期望得分 1 1 1 分。

Subtask 2

暴搜。期望得分 20 20 20 分。

Subtask 3

把所有偶数位置改为 B。期望得分 10 10 10 分。

Subtask 4 ∼ 6

假设 a i = a i + 1 a_i = a_{i+1} ai​=ai+1​ 的位置个数为t，显然答案 ≥ ⌈ t 2 ⌉ ge leftlceil frac{t}{2} rightrceil ≥⌈2t​⌉ 考虑构造方案达到这个下界。
对于每一个 a i = a i + 1 a_i = a_{i+1} ai​=ai+1​ 的位置在 i i i 与 i + 1 i + 1 i+1 之间切一刀，最终将序列分出 t + 1 t + 1 t+1 段。
对于所有编号为偶数的段执行一次 p A = pA = pA= B, $pB = $ C, $pC = $ A 的操作。
因此操作次数是 ⌊ t + 1 2 ⌋ = ⌈ t 2 ⌉ leftlfloor frac{t+1}{2} rightrfloor= leftlceil frac{t}{2} rightrceil ⌊2t+1​⌋=⌈2t​⌉，达到下界，正确性显然。
时间复杂度 O ( n ) mathcal{O}(n) O(n)。期望得分 100 100 100 分。

D. Permutation (Statement)

对于一个 1 ∼ n 1 sim n 1∼n 的排列 p p p，定义 G p G_p Gp​ 为使用以下方法构造出来的无向图：

• 对于每一个 i ∈ ( 1 , n ] i in (1, n] i∈(1,n]，找到最大的 j ∈ [ 1 , i ) j in [1, i) j∈[1,i) 满足 p i > p j p_i > p_j pi​>pj​，然后连一条 i , j i, j i,j 之间的边，
  如果不存在这样的 j j j 则不连。

  给定一棵有 n n n 个节点的树T。把 p p p 称为好排列当且仅当 G p G_p Gp​ 与 T T T 同构。如果存在好排

  列，输出其中字典序最大的一个。否则输出 − 1 −1 −1。 1 ≤ n ≤ 5 × 1 0 3 1 ≤ n ≤ 5 × 10^3 1≤n≤5×103。

	分值	n n n	特殊性质
S u b t a s k 1 Subtask 1 Subtask 1	15 15 15	≤ 8 leq 8 ≤8	无
S u b t a s k 2 Subtask 2 Subtask 2	5 5 5	无特殊限制	树退化为一条链
S u b t a s k 3 Subtask 3 Subtask 3	15 15 15	无特殊限制	度数 ≥ 3 ≥ 3 ≥3 的节点个数 ≤ 1 ≤ 1 ≤1
S u b t a s k 4 Subtask 4 Subtask 4	20 20 20	≤ 100 leq 100 ≤100	无
S u b t a s k 5 Subtask 5 Subtask 5	20 20 20	≤ 1 0 3 leq 10^3 ≤103	无
S u b t a s k 6 Subtask 6 Subtask 6	25 25 25	无特殊限制	无

Subtask 1

暴力枚举排列，构造树，判断同构。期望得分 15 15 15 分。

Subtask 2

a n s 1 = 1 , a n s 2 = n , ∀ i ∈ ( 2 , n ] , a n s i = i − 1 ans_1 = 1, ans_2 = n, forall i in (2, n], ans_i = i − 1 ans1​=1,ans2​=n,∀i∈(2,n],ansi​=i−1。期望得分 5 5 5 分。

Subtask 3

设每一条链的长度为 m a_{1...m} a1...m​。不妨 ∀ i ∈ [ 1 , m ) , a i ≤ a i + 1 forall i in [1, m), a_i ≤ a_{i+1} ∀i∈[1,m),ai​≤ai+1​。
a n s 1 = 1 , a n s 2 = n , ∀ i ∈ ( 2 , a i + 1 ] , a n s i = i − 1 ans_1 = 1, ans_2 = n, forall i in (2, a_i + 1], ans_i = i − 1 ans1​=1,ans2​=n,∀i∈(2,ai​+1],ansi​=i−1。
依次考虑 j = 2 ∼ m j = 2 sim m j=2∼m。对于一个 j j j，假设 x = ∑ k = 2 j a k x = sumlimits_{k=2}^{j} a_k x=k=2∑j​ak​。

依次往 a n s ans ans 中加入 n − x ∼ n − x + a j − 1 n − x sim n − x + a_j − 1 n−x∼n−x+aj​−1。期望得分 20 20 20 分。

Subtask 4 ∼ 5

先枚举根。令 f u f_u fu​ 表示 u u u 这棵子树可以对应到的字典序最大的答案， w u w_u wu​ 表示 u u u 对应的 p p p 值，
s i z e u size_u sizeu​ 表示 u u u 子树的大小。
结论
每一棵子树在 p p p 中的下标一定对应一段区间。
证明：
如果不是，假设 v v v 不在 u u u 的子树中但是插在了 u u u 的子树的中间。
此时一定有 w u > w v w_u > w_v wu​>wv​，否则 v v v 就是 u u u 子树中的点了。
但是出现在 v v v 之后第一个本应在 u u u 子树中的点一定不能连到 u u u 的子树中，矛盾。

我们考虑计算出每一个 f u f_u fu​。假设所有 v ∈ s o n u v in son_u v∈sonu​ 的 f v f_v fv​ 都已经计算好了。
首先 f u , 1 = 1 f_{u,1} = 1 fu,1​=1，否则一定不是一棵树。
把所有 v ∈ s o n u v in son_u v∈sonu​ 的 f v f_v fv​ 按 ∣ f v ∣ |f_v| ∣fv​∣ 第一关键字从小到大， f v f_v fv​ 字典序第二关键字从大到小排序。
然后把所有 f v f_v fv​ 依次插入 f u f_u fu​。容易发现这样可以使得 f u f_u fu​ 字典序最大。
时间复杂度 O ( n 3 ) mathcal{O}(n^3) O(n3) 或 O ( n 3 l o g n ) mathcal{O}(n^3 log n) O(n3logn)。期望得分 35 ∼ 55 35 sim 55 35∼55 分。

Subtask 5 ∼ 6

上面直接枚举根暴力太慢了，我们可以考虑换根。
设 g u g_u gu​ 为 u u u 的外子树的字典序最大的答案。
那么从 g u g_u gu​ 转移到某个儿子只需要按之前的排序方法找到 g u g_u gu​ 在 v ∈ s o n u v in son_u v∈sonu​ 的 f v f_v fv​ 中位置即可。
时间复杂度 O ( n 2 ) mathcal{O}(n^2) O(n2) 或 O ( n 2 l o g n ) mathcal{O}(n^2 log n) O(n2logn)。期望得分 55 ∼ 100 55 sim 100 55∼100 分。