2017-Sp232-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，有人过F之后，cjb和yzc讨论了F，cjb开出来之后丢给了yzc上机，wa了。sub和yzc上机写D，re了。之后'''F2y69'''，'''D4y74'''。sub上机写B，'''B1y83'''。cjb和yzc搞I，wa了，sub上机搞E，'''E1y126'''，之后'''I3y135'''。sub上机写H，'''H2y157'''。C在oeis上找到了，'''C1y190'''。最后sub写A，'''A1y254'''。
== 总结 ==
=== chenjb ===
没什么感觉...感觉出门dirt有点高。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：每个方向上取最远4个点，一共16个点，暴力三种情况：四个点都顶到四边；两个点顶到两边，一个点顶一角；两个点顶两个角，用三分计算。

 * B：发现一段没有交点的路的答案可以判是否撞到两边，直接计算，直接dp即可。

 * C：生成函数，A代表n个点的树的数量，B代表n个点森林的数量，可以形成交替的生成函数，可以用60^3^*高精度打表，实际上是[https://oeis.org/A035052 OEIS]。

 * D：每4个一组，若4个都为字母或数字则计数器加1，根据计数器值从大到小排序，较大n/2是block。

 * E：每次每条毛毛虫，枚举是头还是尾，新增的点连到头上，新的头变成两个点其中的一个，保证只有一组相同，另一个不同即可。

 * F：f[i][j]表示前i个切j刀，考虑a[i]不是众数，则从f[i-1][j]转移，否则直接维护与a[i]相关最大值。

 * G：'''口胡by yzc：'''要么平行两刀，要么横竖各一刀，前者2种情况，后者4种情况，再加上颜色的阶层枚举，总共36种情况，通过坐标变换可以只求两种。第一种直接记录S[x][0]-S[x][1]的最大值即可，第二种情况每新插入一个点，都会对一段后缀的最大值产生+-1的影响，线段树维护即可。

 * H：每次取u+v最大的里面u最大的，找到与它对应即(u-1,v+1)，合并。输出方案。

 * I：先把所有区间删掉，所有人的时间戳对应向前移动，然后按准备时间从小到大，贪心地取，然后用数据结构维护可行性。

 * J：

流水账

出门各自看题，有人过F之后，cjb和yzc讨论了F，cjb开出来之后丢给了yzc上机，wa了。sub和yzc上机写D，re了。之后F2y69，D4y74。sub上机写B，B1y83。cjb和yzc搞I，wa了，sub上机搞E，E1y126，之后I3y135。sub上机写H，H2y157。C在oeis上找到了，C1y190。最后sub写A，A1y254。

总结

chenjb

没什么感觉...感觉出门dirt有点高。

oipotato

subconscious

题解

• A：每个方向上取最远4个点，一共16个点，暴力三种情况：四个点都顶到四边；两个点顶到两边，一个点顶一角；两个点顶两个角，用三分计算。
• B：发现一段没有交点的路的答案可以判是否撞到两边，直接计算，直接dp即可。
• C：生成函数，A代表n个点的树的数量，B代表n个点森林的数量，可以形成交替的生成函数，可以用60³*高精度打表，实际上是OEIS。
• D：每4个一组，若4个都为字母或数字则计数器加1，根据计数器值从大到小排序，较大n/2是block。
• E：每次每条毛毛虫，枚举是头还是尾，新增的点连到头上，新的头变成两个点其中的一个，保证只有一组相同，另一个不同即可。
• F：f[i][j]表示前i个切j刀，考虑a[i]不是众数，则从f[i-1][j]转移，否则直接维护与a[i]相关最大值。
• G：口胡by yzc：要么平行两刀，要么横竖各一刀，前者2种情况，后者4种情况，再加上颜色的阶层枚举，总共36种情况，通过坐标变换可以只求两种。第一种直接记录S[x][0]-S[x][1]的最大值即可，第二种情况每新插入一个点，都会对一段后缀的最大值产生+-1的影响，线段树维护即可。
• H：每次取u+v最大的里面u最大的，找到与它对应即(u-1,v+1)，合并。输出方案。
• I：先把所有区间删掉，所有人的时间戳对应向前移动，然后按准备时间从小到大，贪心地取，然后用数据结构维护可行性。
• J：

附加文件

• 1.png by chenjb