2017-Sp191-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==

== 总结 ==
=== chenjb ===
窒息，两星期没训练，三个人状态都不太行。图论题卡的有点自闭，读题也读错，最后的常数不知道在哪...C是经典的hackenbush graph，又加深了理解。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：

 * B：1到n左到右右到左交替连起来，然后左右两侧分别判没有区间交，有就冲突。

 * C：[https://blog.csdn.net/acm_cxlove/article/details/7854532 Hackenbush Graph]  先做一次dfs确定每个子树SG值，然后再dfs一次，在每个点维护根节点SG值需要是0，其他子树不变的前提下，这棵子树SG值需要是多少。判断每个孩子能不能使得这棵子树做到，统计答案即可。

 * D：sub的线性做法：f[0/1][0/1][0/1]代表x有没有贴到上限 y有没有贴到x  x二进制包含y/不包含，DP内部记录方案数 x1y0数量和 最后一个x1y0后x1+y0数量和，DP即可。

 * E：设全集为U，显然如果|U|=k可行，则|U|=k+1也可行。二分答案，考虑如何判定当前的|U|是否合法。如果不存在条件l0,仅需要满足l1，l2... ln-1，则判定十分简单。为了满足l0，我们的最终目标是最小化Sn-1和S0相同的部分。显然，Si和S0相同的部分的大小是一个区间，我们从前往后贪心的推，得到Sn-1和S0相同部分的大小的范围，取最小值，满足|U-相同部分|>=l0即可。

 * F：

 * G：

 * H：预处理任意两点间不通过加速点的最短路径，然后只维护加速点之间的转移，迭代300次统计答案，注意常数。注意题目中限制了路径上若相邻两加速点为同一点则只加速一次，于是不用管各种自环。注意要用float128硬艹。

 * I：

 * J：考虑点分治统计以每个点为lca的路径。对于一条路径，考虑将其定向，并从终点向起点连一条有向边构成有向环，则题目要求条件等价为环上每条有向边起点和终点的大小关系中，大于号或小于号中的一个至多出现一次。维护每个点的两种符号出现次数，按照权值排序之后即确定最后一条边的符号，通过之前维护好的信息计算贡献。在维护每一种符号出现次数的信息时可以将多余两次的记为两次，即状态0，1，2表示没出现过，出现过一次，出现多于一次，这样即可用一个[3][3]的数组维护每种符号出现次数的状态，统计即可。

 * [https://blog.csdn.net/skywalkert/article/details/85342177 tls]

流水账

总结

chenjb

窒息，两星期没训练，三个人状态都不太行。图论题卡的有点自闭，读题也读错，最后的常数不知道在哪...C是经典的hackenbush graph，又加深了理解。

oipotato

subconscious

题解

A：
B：1到n左到右右到左交替连起来，然后左右两侧分别判没有区间交，有就冲突。
C：Hackenbush Graph 先做一次dfs确定每个子树SG值，然后再dfs一次，在每个点维护根节点SG值需要是0，其他子树不变的前提下，这棵子树SG值需要是多少。判断每个孩子能不能使得这棵子树做到，统计答案即可。
D：sub的线性做法：f[0/1][0/1][0/1]代表x有没有贴到上限 y有没有贴到x x二进制包含y/不包含，DP内部记录方案数 x1y0数量和最后一个x1y0后x1+y0数量和，DP即可。
E：设全集为U，显然如果|U|=k可行，则|U|=k+1也可行。二分答案，考虑如何判定当前的|U|是否合法。如果不存在条件l0,仅需要满足l1，l2... ln-1，则判定十分简单。为了满足l0，我们的最终目标是最小化Sn-1和S0相同的部分。显然，Si和S0相同的部分的大小是一个区间，我们从前往后贪心的推，得到Sn-1和S0相同部分的大小的范围，取最小值，满足|U-相同部分|>=l0即可。
F：
G：
H：预处理任意两点间不通过加速点的最短路径，然后只维护加速点之间的转移，迭代300次统计答案，注意常数。注意题目中限制了路径上若相邻两加速点为同一点则只加速一次，于是不用管各种自环。注意要用float128硬艹。
I：
J：考虑点分治统计以每个点为lca的路径。对于一条路径，考虑将其定向，并从终点向起点连一条有向边构成有向环，则题目要求条件等价为环上每条有向边起点和终点的大小关系中，大于号或小于号中的一个至多出现一次。维护每个点的两种符号出现次数，按照权值排序之后即确定最后一条边的符号，通过之前维护好的信息计算贡献。在维护每一种符号出现次数的信息时可以将多余两次的记为两次，即状态0，1，2表示没出现过，出现过一次，出现多于一次，这样即可用一个[3][3]的数组维护每种符号出现次数的状态，统计即可。
tls