2021-team7-019

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team7 返回]

== Rank和提交情况 ==
[[Image(1.jpg, 1000px)]]

Solved: 11/11

rank：1/470

== 流水账 ==

by fr

题外话：被某些不方便说的离谱事件搞的状态极差，于是今天不进行正常训练。

和 SSerxhs 一起单打 vp

开局签到 A(1,4/0), B(2,10/1), J(3,16/1), K(4,22/1), G(5,29/1).

看到榜上 D 和 H 过的比较多，看 H 感觉是大分类，于是先看 D，是个树剖板子 + 区间开根区间求和，17 min 打完 (6,46/1)。然后做 H，看 SSerxhs 连挂 4 发很慌，但别的题都没人过就硬开了。讨论一半后发现可以 O(n) 无脑大枚举于是删掉一大半讨论交一发就过了 (7,74/1)。然后 C 过的比较多，打开一眼秒了，~~不知道现场是谁带的节奏开 H~~ (8,90/2)。还剩 EFI 都没人过。看榜发现 SSerxhs 15 min 把 E 过了于是跟 E，是一道假的树形 DP 题，开个 map 一通乱搞就过了 (9,140/3)。SSerxhs 此时已经过了 F，但我对 DP 优化并不熟练于是先开 I，一看 k<=50 直接大力爆搜，顺利抢到 I 的现场一血 (10,159/4)。最后做 F，3h 左右想到 DP 方程然后套路单调队列优化，然而代码写的太 /shit 了结果直到封榜前才调完 (11,239/5)。因罚时优势比现场第一快 2min 罚时 AK。

== 题解 ==

A: 签到

B: n(n+1)/2/最大约数

C: 令所有 x_i=1，把 F_i(x_i+1)-F_i(x_i) 扔进堆里，取最大的更新

D: 树剖板子 + 区间开根区间求和

E: map 存一个部门的所有爱好，暴力乱搞即可

F: 单调队列优化 DP

G：高考数学题

H: 分两种情况：顺（逆）时针走完所有点，先顺（逆）时针走一些点，再反向走完剩下的点

I：爆搜 A B C 形成的七个不交集合的所有情况

J: 7+n*(n+11)/2

K: m 和 n 都是 4 的倍数时直接复制样例，否则不合法

[/wiki/2021-team7 返回]

Rank和提交情况

Solved: 11/11

rank：1/470

流水账

by fr

题外话：被某些不方便说的离谱事件搞的状态极差，于是今天不进行正常训练。

和 SSerxhs 一起单打 vp

开局签到 A(1,4/0), B(2,10/1), J(3,16/1), K(4,22/1), G(5,29/1).

看到榜上 D 和 H 过的比较多，看 H 感觉是大分类，于是先看 D，是个树剖板子 + 区间开根区间求和，17 min 打完 (6,46/1)。然后做 H，看 SSerxhs 连挂 4 发很慌，但别的题都没人过就硬开了。讨论一半后发现可以 O(n) 无脑大枚举于是删掉一大半讨论交一发就过了 (7,74/1)。然后 C 过的比较多，打开一眼秒了，不知道现场是谁带的节奏开 H (8,90/2)。还剩 EFI 都没人过。看榜发现 SSerxhs 15 min 把 E 过了于是跟 E，是一道假的树形 DP 题，开个 map 一通乱搞就过了 (9,140/3)。SSerxhs 此时已经过了 F，但我对 DP 优化并不熟练于是先开 I，一看 k<=50 直接大力爆搜，顺利抢到 I 的现场一血 (10,159/4)。最后做 F，3h 左右想到 DP 方程然后套路单调队列优化，然而代码写的太 /shit 了结果直到封榜前才调完 (11,239/5)。因罚时优势比现场第一快 2min 罚时 AK。

题解

A: 签到

B: n(n+1)/2/最大约数

C: 令所有 x_i=1，把 F_i(x_i+1)-F_i(x_i) 扔进堆里，取最大的更新

D: 树剖板子 + 区间开根区间求和

E: map 存一个部门的所有爱好，暴力乱搞即可

F: 单调队列优化 DP

G：高考数学题

H: 分两种情况：顺（逆）时针走完所有点，先顺（逆）时针走一些点，再反向走完剩下的点

I：爆搜 A B C 形成的七个不交集合的所有情况

J: 7+n*(n+11)/2

K: m 和 n 都是 4 的倍数时直接复制样例，否则不合法

附加文件

• 1.jpg by fr200110217102