2017-Sp150-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,700px)]]
== 流水账 ==
开场各自看题，sub让cjb抄个farmland，然后wa了，sub fix了一下'''K2y61'''。一起讨论起了I，得到做法后wa了两发，发现问题，'''I3y94'''。yzc和cjb讨论B，写了许久'''B1y137'''，在这期间cjb读完了所有题目，刚起了E和H。sub终于会做J，'''J1y144'''。之后三个人以为自己会了E，结果不太行，cjb还在刚H，之后sub用力构造，终于完场前'''F2y289'''，最后rk6。
== 总结 ==
=== chenjb ===
输了输了，想了一辈子的H，想去写个暴力又忍住了，写个暴力应该就能感受到它势能的变化了...还是因为自己对于这类题目的做法不熟悉，不敏感，应该和sub多讨论。今天总体出题偏慢，后期sub推F，E和H也没有很好利用机器，尤其是H，特别在想不清楚H merge操作特性的时候，就应该果断上机。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：

 * B：显然能够留下的二元组一定是几个equal关系两两成立的块。发现两两成立的条件为所有的a小于所有的b，同时由于两个块之间不存在equal关系，于是由a和b取值区间构成的区间两两不交。使用set维护这些区间，插入新的二元组时分类讨论即可确定去留和对set的影响。

 * C：用边界的弧计算面积，式子列出来求偏导，二分lambda使得角度和等于2π，注意超出arcos范围的要强制把角度变成0，得到答案直接计算即可。

 * D：

 * E：考虑按照加边的顺序倒着删边维护，对于一条要删掉的边u->v，显然从当前树的根一直到点v，每个点子树的区间一定都是父亲子树区间的前缀（或都是后缀），于是在边上维护前缀或后缀标记，每次暴力往上走，直到遇到了第一条有标记的边，如果这条边的标记已经延伸进别的子树，则无解，否则一直延伸标记到v。此处要注意如果u->v这条边本来就有标记也是合法的。如果一直到根都没有边有标记，则看根节点出发的边中哪种标记还没出现过，如果都出现过，则无解，否则选一个没出现过的一直延伸到v。删除一条边之后要注意去掉其对u节点所在子树的影响。

 * F：构造一个7*7的反对称，每行列各3个1，任意两行&值均不为0的矩阵，把7n个点按照每组7个分成n组，任意两组之间按照矩阵的1连对应组编号的边，组内大力连对应组编号的边，详见代码。

 * G：

 * H：观察merge函数可以发现，以A[0]<B[0]为例，每一次A[0]及其后面连续的小于A[0]的数字都会被塞进新数组，即每一次都是以一个块的结构为单位进行处理的，而每个块的形式都是一个大的数字后面跟着一堆小的，我们称其为一个块的代表元素。显然，代表元素在任何时候都是递增的。每一次merge操作时，切的一刀会将其中一个块切成两部分，前一部分性质保持，后一部分则会变成一些新的块。模拟merge的过程可以发现，新产生的块每导致前半部分连续几个块塞进新数组一次，它自己这个块或连续几个块就会被塞进数组，当新产生的块都被塞进新数组时，由于原来块的代表元素的递增性质，只需两次即可全部塞进数组。所以每次merge操作实际操作数为O(新增加块数)。显然总块数在过程中是不会减少的，而最大的总块数为N(完全有序之后)，所以总的整段塞进数组的操作数为O(N)级别，使用treap维护数组即可在O((N+M)logN)的时间内解决此题。

 * I：按照1的数量从小到大排序，贪心取即可。

 * J：对每个数取出2的幂次，然后变成p*2^k^的形式，其中p是奇数，可以发现k只有log种取值，每次/3求区间奇数和即可。

 * K：farmland的最小生成树。

流水账

开场各自看题，sub让cjb抄个farmland，然后wa了，sub fix了一下K2y61。一起讨论起了I，得到做法后wa了两发，发现问题，I3y94。yzc和cjb讨论B，写了许久B1y137，在这期间cjb读完了所有题目，刚起了E和H。sub终于会做J，J1y144。之后三个人以为自己会了E，结果不太行，cjb还在刚H，之后sub用力构造，终于完场前F2y289，最后rk6。

总结

chenjb

输了输了，想了一辈子的H，想去写个暴力又忍住了，写个暴力应该就能感受到它势能的变化了...还是因为自己对于这类题目的做法不熟悉，不敏感，应该和sub多讨论。今天总体出题偏慢，后期sub推F，E和H也没有很好利用机器，尤其是H，特别在想不清楚H merge操作特性的时候，就应该果断上机。

oipotato

subconscious

题解

A：
B：显然能够留下的二元组一定是几个equal关系两两成立的块。发现两两成立的条件为所有的a小于所有的b，同时由于两个块之间不存在equal关系，于是由a和b取值区间构成的区间两两不交。使用set维护这些区间，插入新的二元组时分类讨论即可确定去留和对set的影响。
C：用边界的弧计算面积，式子列出来求偏导，二分lambda使得角度和等于2π，注意超出arcos范围的要强制把角度变成0，得到答案直接计算即可。
D：
E：考虑按照加边的顺序倒着删边维护，对于一条要删掉的边u->v，显然从当前树的根一直到点v，每个点子树的区间一定都是父亲子树区间的前缀（或都是后缀），于是在边上维护前缀或后缀标记，每次暴力往上走，直到遇到了第一条有标记的边，如果这条边的标记已经延伸进别的子树，则无解，否则一直延伸标记到v。此处要注意如果u->v这条边本来就有标记也是合法的。如果一直到根都没有边有标记，则看根节点出发的边中哪种标记还没出现过，如果都出现过，则无解，否则选一个没出现过的一直延伸到v。删除一条边之后要注意去掉其对u节点所在子树的影响。
F：构造一个7*7的反对称，每行列各3个1，任意两行&值均不为0的矩阵，把7n个点按照每组7个分成n组，任意两组之间按照矩阵的1连对应组编号的边，组内大力连对应组编号的边，详见代码。
G：
H：观察merge函数可以发现，以A[0]
I：按照1的数量从小到大排序，贪心取即可。
J：对每个数取出2的幂次，然后变成p*2^k的形式，其中p是奇数，可以发现k只有log种取值，每次/3求区间奇数和即可。
K：farmland的最小生成树。

附加文件

1.png by chenjb