2020-team1-039

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 12/13  dirt: 29%
rank: 4
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
Emmy，神
Sakuya:今天倒着开题，把后面连续5道题都1A了，十分的开心，居然还从oscar手上抢来了构造。
== 题解 ==
A: 模拟
B: 众数
C: 找规律 (4-cnt[1])/(8-cnt[1]-cnt[i])，判0
D: dp，f[i][j]表示最终第i个左括号右边有j个右括号的最大收益
E: f数组代表以当前位置为结尾的最长上升子序列长度，根据性质拓扑排序贪心求出每个位置的最小可行值
F: 枚举log_p a[i]，预处理 a[i]/log 的前缀和，找一下在哪个区间搞一下
G: xz=zy，拖动一下，倍长一下，发现一个东西，SAM+线段树合并算贡献（也可以hash）
H: dp(i,j,0/1)代表i为根的子树前j个儿子全访问完，且是否把记录点往下移过的最小代价，枚举当前儿子是否需要把记录点往下移，如果不需要往下移就把贡献加上暴力走完子树的花费，如果需要往下移且没有往下移过就没有额外花费，否则需要从根再走一次，加上根到当前点路径长度作为贡献
I: 0~n-2分别连接n~2n-2，n-1连接3n-4。具体证明可以用塞瓦定理或者暴力建系，我懒得证了，反正proved by PP就对了。（SB出题人，SB题意）
J: 构造
K: 模拟（我的代码据说全场最短？）
L: 排序
M: 模拟

[/wiki/2020-team1 返回]

概述

solved: 12/13 dirt: 29%

rank: 4

流水账

总结

Emmy，神

Sakuya:今天倒着开题，把后面连续5道题都1A了，十分的开心，居然还从oscar手上抢来了构造。

题解

A: 模拟

B: 众数

C: 找规律 (4-cnt[1])/(8-cnt[1]-cnt[i])，判0

D: dp，f[i][j]表示最终第i个左括号右边有j个右括号的最大收益

E: f数组代表以当前位置为结尾的最长上升子序列长度，根据性质拓扑排序贪心求出每个位置的最小可行值

F: 枚举log_p a[i]，预处理 a[i]/log 的前缀和，找一下在哪个区间搞一下

G: xz=zy，拖动一下，倍长一下，发现一个东西，SAM+线段树合并算贡献（也可以hash）

H: dp(i,j,0/1)代表i为根的子树前j个儿子全访问完，且是否把记录点往下移过的最小代价，枚举当前儿子是否需要把记录点往下移，如果不需要往下移就把贡献加上暴力走完子树的花费，如果需要往下移且没有往下移过就没有额外花费，否则需要从根再走一次，加上根到当前点路径长度作为贡献

I: 0~n-2分别连接n~2n-2，n-1连接3n-4。具体证明可以用塞瓦定理或者暴力建系，我懒得证了，反正proved by PP就对了。（SB出题人，SB题意）

J: 构造

K: 模拟（我的代码据说全场最短？）

L: 排序

M: 模拟

附加文件