2017-C19-team1

从 Trac 迁移的文章

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

原文章内容如下：

== lsmll ==

流水账：倒着看。一开始看了1012感觉应该不难，后来发现要数据结构之类的维护，而且看了数据范围感觉log有点悬。后来发现可以用单调队列+二分，虽然还是有log但常数比较小，于是就上去写了。然后获得TLE，之后常数优化+读入优化就过了。之后看了1008和shb讨论发现树形DP一下就好，于是shb去写。之后看了1010，由区间的做法猜想是按照LCA由深到浅删除，但是发现不会维护删了之后路径是否联通，于是用了树链剖分。shb表示他比较擅长写树链剖分，于是我写前半部分，后面让他写树链剖分。后来我和shb写的部分各发现了一个bug，修改之后通过了此题。后来我们想出1007的log^2^做法，也是树链剖分，于是shb写，我在看cube等别的题。后来shb写完意料之中地获得TLE，我也没想出别的题做法。

总结：今天我写的两题都有一些小细节错误导致调试了较长时间，且各贡献了一次罚时，以后要尽量避免。

== shb ==

流水账：今天正着看。感觉1001是个傻逼字符串，远程咨询了一下jsb，他表示可以随手艹，就让他写了一下= =。sm肝了一波1012，趁这段时间我切了两个签到。之后写了一下树DP，感觉我每次写树DP都很爆炸，但是感觉今天写的姿势还挺帅的。。但是因为忘记清空边表，结果导致死循环爆栈，而我误以为是辣鸡hdoj的栈太小，于是改了人工栈，结果还是爆。。测了一下多组数据才发现。。我之前看过1006，感觉是个简单根号dp，但是第一次没考虑空间问题，开LL导致MLE，想了想感觉int也行，交上去T了，然后把记忆化搜索改成普通DP，但是因为改LL的时候没改全，WA了一次，喜获三发罚时后终于过了。。之后sm感觉1010是个贪心，不过需要树剖维护，于是他写了贪心，我写了树剖，过了。最后1007又写了个树剖，但是T了。

总结：交题前多测几组数据，特别是multicase的情况，很容易因为没清空等问题而爆炸。交题前要多想想空间、时限等问题，不然各种罚时很伤。


== 补题 ==

1003 [lsmll]

1007 [shb]

1009 []

1011 []

lsmll

流水账：倒着看。一开始看了1012感觉应该不难，后来发现要数据结构之类的维护，而且看了数据范围感觉log有点悬。后来发现可以用单调队列+二分，虽然还是有log但常数比较小，于是就上去写了。然后获得TLE，之后常数优化+读入优化就过了。之后看了1008和shb讨论发现树形DP一下就好，于是shb去写。之后看了1010，由区间的做法猜想是按照LCA由深到浅删除，但是发现不会维护删了之后路径是否联通，于是用了树链剖分。shb表示他比较擅长写树链剖分，于是我写前半部分，后面让他写树链剖分。后来我和shb写的部分各发现了一个bug，修改之后通过了此题。后来我们想出1007的log²做法，也是树链剖分，于是shb写，我在看cube等别的题。后来shb写完意料之中地获得TLE，我也没想出别的题做法。

总结：今天我写的两题都有一些小细节错误导致调试了较长时间，且各贡献了一次罚时，以后要尽量避免。

shb

流水账：今天正着看。感觉1001是个傻逼字符串，远程咨询了一下jsb，他表示可以随手艹，就让他写了一下= =。sm肝了一波1012，趁这段时间我切了两个签到。之后写了一下树DP，感觉我每次写树DP都很爆炸，但是感觉今天写的姿势还挺帅的。。但是因为忘记清空边表，结果导致死循环爆栈，而我误以为是辣鸡hdoj的栈太小，于是改了人工栈，结果还是爆。。测了一下多组数据才发现。。我之前看过1006，感觉是个简单根号dp，但是第一次没考虑空间问题，开LL导致MLE，想了想感觉int也行，交上去T了，然后把记忆化搜索改成普通DP，但是因为改LL的时候没改全，WA了一次，喜获三发罚时后终于过了。。之后sm感觉1010是个贪心，不过需要树剖维护，于是他写了贪心，我写了树剖，过了。最后1007又写了个树剖，但是T了。

总结：交题前多测几组数据，特别是multicase的情况，很容易因为没清空等问题而爆炸。交题前要多想想空间、时限等问题，不然各种罚时很伤。

补题

1003 [lsmll]

1007 [shb]

1009 []

1011 []