2018-Reconquista-T24

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

''' 2015 MIPT Workshop Open - AMPPZ-2015 '''

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006275 Opentrains]

== 流水账 ==


== 总结 ==

=== lsmll ===
感觉B和L题都有失误，B题实际上是以一个简单的拓扑排序，我和jsb一开始想到了错误的方向去，导致卡了很久，后来经过lzw提醒才发现正解。L题我们没有发现比较显然的子树走的顺序无关，导致我写了很复杂的树形DP，所幸1A了居然。然后我们今天还是没有贯彻读完题的方针，后期一直在搞过的人多的K题，而G题其实蒋学长之前做过类似的题，会做，一直没有发现导致最后40min才开始写，没有调出来，如果早点发现可能能过。


=== jsb ===

前期有点小卡B，现在还感觉有点玄学。

中途的H题卡了炒鸡久。上次训练也遇到过类似的裸N^3^DP，需要套路优化的题。所以这次一直往单调性上想，试了很多单调性都无果。

最后我在暴力打决策表示，发现O(2000^3^)的暴力只跑了10+秒（时限9s，但上面比底下慢很多）。我加了一个二分，把N^3^转移的max优化掉了，卡到了4.7s，交一发还是T。然后加了个数组寻址优化底下卡到1.6s>_<。

事实上，这题在拆开之后，只要用裸线段树优化就行了……竟然没有往那一方向去想……

后来偷偷吃了个饭，就来不及写最后的G题了。莽了30+min WA17，感觉好亏。

G补题感想：360°极角排序时，如果采用y轴上下特判+叉积，最好先手动判掉y=0的情况，特别萎。


=== lzw ===
K题这种比较有思维的题目还是要多做做，提高一下智商。 今后比赛也要敢于开新的题，至少要把所有题目都读完，那些过的队伍很少的题目也许恰好是以前记过的模型，或者比较擅长的类型，不要因为过的人很少就不敢去尝试。


== Solution ==
See attachment.

== 补题 ==
C []

E []

G [jsb]http://www.cnblogs.com/jiangshibiao/p/8601690.html 3.21处

J [lsmll]

K [lzw] 考虑按照从n到1的顺序放。 先放好n， 对于接下来的高度，如果放在之前所有柱子的左边，那么从左边能看到的柱子数+1（情况1）， 如果放在所有柱子的右边，那么从右边能看的柱子数（情况2）。 如果放在中间， 那么没有影响，并且放高度为i的时候，有n-1-i种方案（情况3）。  对于情况1，记为L操作，对于情况2，记为R操作，对于情况3，记下n-1-i这个数。  那么放置的方案就对应了这样的一个序列。  一个序列对应的方案数是里面所有数的乘积。  f【i】【j】表示长度为i-1的序列放j个L或者R（这里先不区分是L还是R，记为X）的总贡献，f[i][j] = f[i - 1][j - 1](最后一个是X) + (i - 1) * f[i - 1][j]（最后一个是i-1）.  那么答案就是Comb（a + b - 2, a - 1） * f[n][a + b - 2].

Contest Information

2015 MIPT Workshop Open - AMPPZ-2015

Opentrains

流水账

总结

lsmll

感觉B和L题都有失误，B题实际上是以一个简单的拓扑排序，我和jsb一开始想到了错误的方向去，导致卡了很久，后来经过lzw提醒才发现正解。L题我们没有发现比较显然的子树走的顺序无关，导致我写了很复杂的树形DP，所幸1A了居然。然后我们今天还是没有贯彻读完题的方针，后期一直在搞过的人多的K题，而G题其实蒋学长之前做过类似的题，会做，一直没有发现导致最后40min才开始写，没有调出来，如果早点发现可能能过。

jsb

前期有点小卡B，现在还感觉有点玄学。

中途的H题卡了炒鸡久。上次训练也遇到过类似的裸N3DP，需要套路优化的题。所以这次一直往单调性上想，试了很多单调性都无果。

最后我在暴力打决策表示，发现O(20003)的暴力只跑了10+秒（时限9s，但上面比底下慢很多）。我加了一个二分，把N3转移的max优化掉了，卡到了4.7s，交一发还是T。然后加了个数组寻址优化底下卡到1.6s>_<。

事实上，这题在拆开之后，只要用裸线段树优化就行了……竟然没有往那一方向去想……

后来偷偷吃了个饭，就来不及写最后的G题了。莽了30+min WA17，感觉好亏。

G补题感想：360°极角排序时，如果采用y轴上下特判+叉积，最好先手动判掉y=0的情况，特别萎。

lzw

K题这种比较有思维的题目还是要多做做，提高一下智商。 今后比赛也要敢于开新的题，至少要把所有题目都读完，那些过的队伍很少的题目也许恰好是以前记过的模型，或者比较擅长的类型，不要因为过的人很少就不敢去尝试。

Solution

See attachment.

补题

C []

E []

G [jsb]http://www.cnblogs.com/jiangshibiao/p/8601690.html 3.21处

J [lsmll]

K [lzw] 考虑按照从n到1的顺序放。 先放好n， 对于接下来的高度，如果放在之前所有柱子的左边，那么从左边能看到的柱子数+1（情况1）， 如果放在所有柱子的右边，那么从右边能看的柱子数（情况2）。 如果放在中间， 那么没有影响，并且放高度为i的时候，有n-1-i种方案（情况3）。 对于情况1，记为L操作，对于情况2，记为R操作，对于情况3，记下n-1-i这个数。 那么放置的方案就对应了这样的一个序列。 一个序列对应的方案数是里面所有数的乘积。 f【i】【j】表示长度为i-1的序列放j个L或者R（这里先不区分是L还是R，记为X）的总贡献，f[i][j] = f[i - 1][j - 1](最后一个是X) + (i - 1) * f[i - 1][j]（最后一个是i-1）. 那么答案就是Comb（a + b - 2, a - 1） * f[n][a + b - 2].

附加文件