2020-team1-008

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 9/10  dirt: 36%
rank: 15 (现场榜1~2)
[[Image(Rank.png,800px)]]

== 流水账 ==
Oscar开局飞快的切了G1Y11，B1Y38，他跟Grammy说可以去看一看J，他觉得J是个dp。Grammy看完J感觉是dp，设计了一个状态感觉复杂度不太对，想了一会意识到这个是棵树，复杂度不能那样算，重新算了一下就对了，写完调完交上去因为空间开小白给一发，J2Y59
Oscar说A很像之前某道题，Grammy去跟榜开F，A1Y74，Grammy飞速的写完F然后wa了。Oscar开C，C1Y113. Grammy仍然在F自闭，Oscar来看也看不出什么错误，他出了一些数据，成功hack掉了程序，Grammy发现是之前一次fix把对的改成错的了。F3Y119. 
Oscar觉得D是dp让Grammy去做，Grammy卡完秒出做法，正准备上去写，想了想自己把自己的做法叉掉了，然后他就不会了。Oscar觉得可以直接暴力dp，Grammy觉得复杂度太大了，肯定会T，但他想了想好像没有其他做法，就上去写完然后T了。他想了一会，觉得这个dp可以加一些剪枝，把他想得到的剪枝全加了上去，D3Y175. 
两人讨论了一会E感觉没什么思路，各自在纸上开始推。过了一会Oscar说他会了，讲给Grammy，后者觉得很有道理，就去看其他题。E1Y227.
两人讨论了一会I，觉得只有一种做法，复杂度又是挺大的，因为榜上过了很多，而且没什么其他想法，决定故技重施，直接上暴力dp+剪枝，然后他又过了（，I1Y269.
H讨论了一会得到一个扫描线做法，但是复杂度太巨大了而且也没时间了。
（赛后发现H就是这么做的...）
== 总结 ==
怎么这么多暴力+剪枝题啊
Grammy：这场骗Oscar去写了好多题，真爽啊（bushi）
== 题解 ==
A:
B:
C:
D: 暴力dp加剪枝
E:
F: 分类讨论+模拟
G:
H: 怒斥出题人
I:
J: 每个点其实只有O(1)种状态，可以不dp，O(n)直接做

[/wiki/2020-team1 返回]

概述

solved: 9/10 dirt: 36%

rank: 15 (现场榜1~2)

流水账

Oscar开局飞快的切了G1Y11，B1Y38，他跟Grammy说可以去看一看J，他觉得J是个dp。Grammy看完J感觉是dp，设计了一个状态感觉复杂度不太对，想了一会意识到这个是棵树，复杂度不能那样算，重新算了一下就对了，写完调完交上去因为空间开小白给一发，J2Y59

Oscar说A很像之前某道题，Grammy去跟榜开F，A1Y74，Grammy飞速的写完F然后wa了。Oscar开C，C1Y113. Grammy仍然在F自闭，Oscar来看也看不出什么错误，他出了一些数据，成功hack掉了程序，Grammy发现是之前一次fix把对的改成错的了。F3Y119.

Oscar觉得D是dp让Grammy去做，Grammy卡完秒出做法，正准备上去写，想了想自己把自己的做法叉掉了，然后他就不会了。Oscar觉得可以直接暴力dp，Grammy觉得复杂度太大了，肯定会T，但他想了想好像没有其他做法，就上去写完然后T了。他想了一会，觉得这个dp可以加一些剪枝，把他想得到的剪枝全加了上去，D3Y175.

两人讨论了一会E感觉没什么思路，各自在纸上开始推。过了一会Oscar说他会了，讲给Grammy，后者觉得很有道理，就去看其他题。E1Y227.

两人讨论了一会I，觉得只有一种做法，复杂度又是挺大的，因为榜上过了很多，而且没什么其他想法，决定故技重施，直接上暴力dp+剪枝，然后他又过了（，I1Y269.

H讨论了一会得到一个扫描线做法，但是复杂度太巨大了而且也没时间了。

（赛后发现H就是这么做的...）

总结

怎么这么多暴力+剪枝题啊

Grammy：这场骗Oscar去写了好多题，真爽啊（bushi）

题解

A:

B:

C:

D: 暴力dp加剪枝

E:

F: 分类讨论+模拟

G:

H: 怒斥出题人

I:

J: 每个点其实只有O(1)种状态，可以不dp，O(n)直接做

附加文件