2017-Sp189-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，感觉A很能写，就让yzc上机写A，后发现大家开始过B，cjb上机写B，'''B1y23'''，yzc继续写A，写完后发现内存下不来。之后sub和cjb讨论了C，cjb上机写C，wa了2发感觉看不出错，最后yzc发现n-l其实大于n-r，有点无语，'''C3y81'''。之后sub上机写E，发现假了，有点自闭，三人又让yzc上去撸A的bitset，后来发现又假了。之后sub想E，yzc推G的式子，cjb想J，之后终于'''G1y143'''，'''E1y154'''，'''J2y193'''。之后三人又决定开始搞A，然后yzc想到了怎么缩减内存，上机写A，sub想I，cjb继续想D，然后yzc写完wa了，拍上debug了之后得到了Wall Time-limit Exceeded???非常自闭，各种调整，在32到36的case来回滚动，sub抽空上机写I，'''I1y274'''。之后三人开始疯狂艹A，感觉稳得一比，交了大概16发后，居然得到了一发ok，'''A16y295'''。
== 总结 ==
=== chenjb ===
这个A是什么jb？感觉用交互来强制在线非常愚蠢，差点就没爆过去了，明明算法和常数都很优秀的.....
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：线段树维护bitset，由于所有的bitset中1的个数只有nlogn个，于是线段树每个节点用链表维护存在1的bitset的块。

 * B：1、2...2^p^次个1，位置random放置，随机20次，一定能撞到。

 * C：bfs，用set来存关键点，每次更新后就把关键点从set中erase掉，保证复杂度。

 * D：对S和T建广义后缀自动机得到所有公共子串最早出现位置的右端点，反过来同样做一次，就能得到最晚出现的左端点，剩下就是二维数点问题。

 * E：考察第一类斯特林数，可以构造出类似的序列要求每个环大小至少是2，乘以组合数即可。

 * F：

 * G：从链的一端往回推，会得到相邻两个点答案的差值是一个等差数列，将这个方法推广到子树上之后一个点和他父亲的答案差值是他所有子树和他差值的和加上这个点的度数再加1，可以发现这个值等于这个点子树内的点数*2-1，倍增维护即可。

 * H：

 * I：把一条有方向的边两边分别放a和b，视为同一个等价关系，对于一个节点，这个节点的入度和出度不是同一条边，则他们俩等价，用并查集维护等价关系即可。

 * J：维护A队列，其中相邻两个点连边为A，B队列其中相邻两个点连边为W，A.back()和B.back()连边为A，新加入一个点，通过分类讨论可以维持原来两个队列的性质，最后按要求输出即可。

 * [https://wiki.icpc.camp/twsf/Petrozavodsk%20Summer-2015.%20Moscow%20IPT%20Contest TheWaySoFar]

 * [https://wiki.icpc.camp/dreadnought/Moscow%20IPT%20Contest Dreadnought]

 

流水账

出门各自看题，感觉A很能写，就让yzc上机写A，后发现大家开始过B，cjb上机写B，B1y23，yzc继续写A，写完后发现内存下不来。之后sub和cjb讨论了C，cjb上机写C，wa了2发感觉看不出错，最后yzc发现n-l其实大于n-r，有点无语，C3y81。之后sub上机写E，发现假了，有点自闭，三人又让yzc上去撸A的bitset，后来发现又假了。之后sub想E，yzc推G的式子，cjb想J，之后终于G1y143，E1y154，J2y193。之后三人又决定开始搞A，然后yzc想到了怎么缩减内存，上机写A，sub想I，cjb继续想D，然后yzc写完wa了，拍上debug了之后得到了Wall Time-limit Exceeded???非常自闭，各种调整，在32到36的case来回滚动，sub抽空上机写I，I1y274。之后三人开始疯狂艹A，感觉稳得一比，交了大概16发后，居然得到了一发ok，A16y295。

总结

chenjb

这个A是什么jb？感觉用交互来强制在线非常愚蠢，差点就没爆过去了，明明算法和常数都很优秀的.....

oipotato

subconscious

题解

• A：线段树维护bitset，由于所有的bitset中1的个数只有nlogn个，于是线段树每个节点用链表维护存在1的bitset的块。
• B：1、2...2^p次个1，位置random放置，随机20次，一定能撞到。
• C：bfs，用set来存关键点，每次更新后就把关键点从set中erase掉，保证复杂度。
• D：对S和T建广义后缀自动机得到所有公共子串最早出现位置的右端点，反过来同样做一次，就能得到最晚出现的左端点，剩下就是二维数点问题。
• E：考察第一类斯特林数，可以构造出类似的序列要求每个环大小至少是2，乘以组合数即可。
• F：
• G：从链的一端往回推，会得到相邻两个点答案的差值是一个等差数列，将这个方法推广到子树上之后一个点和他父亲的答案差值是他所有子树和他差值的和加上这个点的度数再加1，可以发现这个值等于这个点子树内的点数*2-1，倍增维护即可。
• H：
• I：把一条有方向的边两边分别放a和b，视为同一个等价关系，对于一个节点，这个节点的入度和出度不是同一条边，则他们俩等价，用并查集维护等价关系即可。
• J：维护A队列，其中相邻两个点连边为A，B队列其中相邻两个点连边为W，A.back()和B.back()连边为A，新加入一个点，通过分类讨论可以维持原来两个队列的性质，最后按要求输出即可。
• TheWaySoFar
• Dreadnought

附加文件

• 1.png by chenjb