2020-team1-013

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
开局跟榜A不会做，于是去跟J的榜，Oscar和Grammy各推出一个柿子，Grammy说因为和为m的性质，这两个柿子是一样的，他上去写完过不了样例，看了很久也不知道为什么，Oscar看了一会觉得枚举了一侧的人车数后还要考虑有多少个车，Grammy改完仍然过不了样例，他造了组数据叉掉后调出来发现还要考虑一个组合数的选择，增加了一个dp，J1Y93
Oscar觉得A有个性质，根据这个性质可以用二分图最大权匹配做，Grammy觉得非常对，于是Oscar找了一个KM的板子，A1Y107
两人跟榜讨论C，一开始都觉得对每个联通块找在他下面的所有联通块，然后按联通块最下的格子的高度从底往上处理每个联通块这样做非常对，Grammy写完wa了，然后两人讨论了一下发现不止要考虑一个联通块底层下面的联通块，并且联通块之间这样的关系可能成环，接着发现这是个差分约束。Grammy写完交上去非常迷惑的MLE了。正常算空间应该不会爆，推测可能是vector额外占用了一些空间，Grammy把vector省掉，并且缩小了一些边的上界后过了. C3Y175.
两人接着讨论D，觉得分类讨论很可行，Oscar上机写。写完Grammy帮忙造了几组数据都过了，交上去D1Y249
Grammy提出I的一个dp思路，但是中间有一个部分还没想好怎么处理比较好，Oscar提出一个性质：这部分有用的边肯定都是连回1的。Grammy觉得非常对，想了一会设计了一个状态，给Oscar讲了一下。Grammy原来想直接O(n^3^m)上去，Oscar觉得会T，建议他优化，于是Grammy加了一个差分的优化。写完未能通过样例，他造了一个小数据卡掉后调了出来中间一个dp的转移条件不太对，改完I1Y289
== 总结 ==
这场好稳，几乎没有罚时。
== 题解 ==
A:
B:
C:
D:
E:
F: 
G:
H:
I:
J:
K:
L:

[/wiki/2020-team1 返回]

概述

solved: 5/11 dirt: 29%

rank: 34

流水账

开局跟榜A不会做，于是去跟J的榜，Oscar和Grammy各推出一个柿子，Grammy说因为和为m的性质，这两个柿子是一样的，他上去写完过不了样例，看了很久也不知道为什么，Oscar看了一会觉得枚举了一侧的人车数后还要考虑有多少个车，Grammy改完仍然过不了样例，他造了组数据叉掉后调出来发现还要考虑一个组合数的选择，增加了一个dp，J1Y93

Oscar觉得A有个性质，根据这个性质可以用二分图最大权匹配做，Grammy觉得非常对，于是Oscar找了一个KM的板子，A1Y107

两人跟榜讨论C，一开始都觉得对每个联通块找在他下面的所有联通块，然后按联通块最下的格子的高度从底往上处理每个联通块这样做非常对，Grammy写完wa了，然后两人讨论了一下发现不止要考虑一个联通块底层下面的联通块，并且联通块之间这样的关系可能成环，接着发现这是个差分约束。Grammy写完交上去非常迷惑的MLE了。正常算空间应该不会爆，推测可能是vector额外占用了一些空间，Grammy把vector省掉，并且缩小了一些边的上界后过了. C3Y175.

两人接着讨论D，觉得分类讨论很可行，Oscar上机写。写完Grammy帮忙造了几组数据都过了，交上去D1Y249

Grammy提出I的一个dp思路，但是中间有一个部分还没想好怎么处理比较好，Oscar提出一个性质：这部分有用的边肯定都是连回1的。Grammy觉得非常对，想了一会设计了一个状态，给Oscar讲了一下。Grammy原来想直接O(n3m)上去，Oscar觉得会T，建议他优化，于是Grammy加了一个差分的优化。写完未能通过样例，他造了一个小数据卡掉后调了出来中间一个dp的转移条件不太对，改完I1Y289

总结

这场好稳，几乎没有罚时。

题解

A:

B:

C:

D:

E:

F:

G:

H:

I:

J:

K:

L:

附加文件