2019-team321/C009

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(standings.png,500px)]]

[[Image(submissions.png,500px)]]

== 流水账 ==

B题zkx读错题了，读成了曼哈顿距离，还上去写了一发。

A题zkx也读错题意了，导致yay想了一下错误的题意。

H题ypl没有发现要flush，结果wall time limit exceeded了几发。


== 总结 ==

=== zkx ===

1. B题写之前应该考虑一下，榜上没人过的话肯定不太可做。

==== G 题解 ====

  设 f[i] 为对于前 i 个元素，拆分成一个上升序列，一个下降序列，且上升序列以 i 结尾是否可行。
  g[i] 是下降序列以 i 结尾是否可行。[[BR]]
  g[j] = 1，如果存在某个 f[i] = 1 且 [i+1, j] 下降，且 a[i] < a[j+1] [[BR]]
  用线段树区间取 max，单点询问来快速求。

==== E 题解 ====

  拉格朗日乘数法，可以直接解出 mu，看是否存在 p<0，如果存在的话直接把那个物品扔掉。

  也可以直接枚举有多少个物品被扔掉（从小的开始扔）

=== yay ===

=== ypl ===

A: 5000 个点 1000000 次加边， 每条边颜色在 【1， 200】。 定义两个点连通， 当且仅当在每种颜色的边的作用下联通。 每次加边后， 问联通的点对个数。 对每种颜色用并查集， 点 x 的联通信息为 S（x） = 【点 x 在颜色 i 的边联通下的并查集的根】。 两个点联通当且仅当 S 相等。 对 S（x） 用 Hash 进行分类。 为了保证复杂度， 并查集需要按秩合并。

流水账

B题zkx读错题了，读成了曼哈顿距离，还上去写了一发。

A题zkx也读错题意了，导致yay想了一下错误的题意。

H题ypl没有发现要flush，结果wall time limit exceeded了几发。

总结

zkx

1. B题写之前应该考虑一下，榜上没人过的话肯定不太可做。

G 题解

设 f[i] 为对于前 i 个元素，拆分成一个上升序列，一个下降序列，且上升序列以 i 结尾是否可行。

g[i] 是下降序列以 i 结尾是否可行。

g[j] = 1，如果存在某个 f[i] = 1 且 [i+1, j] 下降，且 a[i] < a[j+1]

用线段树区间取 max，单点询问来快速求。

E 题解

拉格朗日乘数法，可以直接解出 mu，看是否存在 p<0，如果存在的话直接把那个物品扔掉。

也可以直接枚举有多少个物品被扔掉（从小的开始扔）

yay

ypl

A: 5000 个点 1000000 次加边， 每条边颜色在 【1， 200】。 定义两个点连通， 当且仅当在每种颜色的边的作用下联通。 每次加边后， 问联通的点对个数。 对每种颜色用并查集， 点 x 的联通信息为 S（x） = 【点 x 在颜色 i 的边联通下的并查集的根】。 两个点联通当且仅当 S 相等。 对 S（x） 用 Hash 进行分类。 为了保证复杂度， 并查集需要按秩合并。