2017-Sp97-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
 开场各自看题，cjb和yzc讨论了D，'''D1y15'''。cjb上机敲后缀数组，之后yzc上机后发现和cjb的I做法有问题。sub上机敲C，'''C1y70'''。之后cjb上机敲A的线段树，sub把贡献部分补完，始终wa，找到了好几个bug。之后sub给yzc讲了F，'''F1y162'''。sub上机做L，'''L2y191'''。cjb和yzc终于看出A的问题，'''A5y207'''。之后sub写了E的几何部分，yzc和cjb搞set的部分始终没搞定，就咕咕了。
== 总结 ==
=== chenjb ===
休整.jpg，以后如果线段树要坐标平移，记得要算清楚上下界。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：考虑点在扫描过程中的贡献区间，用线段树维护区间修改和区间max。

 * B：经典例题，有c1个1...cn个n，求排成没有相邻元素的序列数量，用容斥dp即可，本题计算过程中乘上组合数系数即可，注意环的情况。

 * C：路径内按概率从小到大，路径间按期望步数/连通概率排序。

 * D：每次贪心往后匹配尽可能长的子序列。

 * E：线段树维护区间点和对角点最右最左点和区间最近点对的距离，合并显然。修改都是单点修改，非常容易。**几何部分题解@sub

 * F：f[i][mask]以i为根，包含mask的子树贡献，转移f[i][mask]=min(f[i][mask/j/mask']+f[j][j|mask']+dis[i][j]*(size[mask']+1)*(n-size[mask']-1))

 * G：先跑出普通的MST。然后对于每个点，将这个点的所有边都变为边权为0加入MST动态维护，同时将维护过程中加入的边全都记下来。结束之后将这些边全都删掉，再将删掉的边全都加回去。这么做的正确性显然，考虑kruskal算法的过程，显然会先考虑这些边权为0的边，并且这些边不可能构成环，所以这些边一定都在MST上，所以结束之后全都删掉即可。

 * H：sub

 * I：考虑对串建立SAM，则每插入一个字符后的答案为parent树上每个节点代表的子串长度个数*Right集合大小之和，用LCT维护parent树即可。

 * J：对于一个区间[l,r]，若它是单调的，则显然先手必败。若去掉l或者r后变成了单调的，则显然先手必胜。若[l+1,r−1]是单调的，那么同理先手必败。若[l,r−2]是单调的，那么先手若取r会导致后手必胜，后手同理，故两人会一直取l直到出现上面第一种或者第二种情况，可以根据奇偶性判断。同理可以得出是单调的情形的处理方法。除此之外，有[l,r]的答案等于[l+1,r−1]的答案，二分找到最小的k满足[l+k,r−k]可以由上面方法直接判断出胜负即可，另有一条式子win[l,r]=(!win[l+1,r])|(!win[l,r-1])。ps：至于为什么[l,r]=[l+1,r-1]，其实我觉得一点都不显然，问了下Claris和秋少，他们也不懂....咕咕咕 .......然后我画了个图，似乎能prove了。[[BR]]
 [[Image(proof.png,500px)]]

 * K：考虑矩阵维护，发现存在逆矩阵，维护（逆）矩阵前缀和的最后一行（列）即可。

 * L：发现2^i^步操作效果是取间隔为2^i-1^次异或起来，倍增即可。

 * [http://www.cnblogs.com/clrs97/p/8711574.html Claris]
== 补题 ==

流水账

开场各自看题，cjb和yzc讨论了D，D1y15。cjb上机敲后缀数组，之后yzc上机后发现和cjb的I做法有问题。sub上机敲C，C1y70。之后cjb上机敲A的线段树，sub把贡献部分补完，始终wa，找到了好几个bug。之后sub给yzc讲了F，F1y162。sub上机做L，L2y191。cjb和yzc终于看出A的问题，A5y207。之后sub写了E的几何部分，yzc和cjb搞set的部分始终没搞定，就咕咕了。

总结

chenjb

休整.jpg，以后如果线段树要坐标平移，记得要算清楚上下界。

oipotato

subconscious

题解

  • A：考虑点在扫描过程中的贡献区间，用线段树维护区间修改和区间max。
  • B：经典例题，有c1个1...cn个n，求排成没有相邻元素的序列数量，用容斥dp即可，本题计算过程中乘上组合数系数即可，注意环的情况。
  • C：路径内按概率从小到大，路径间按期望步数/连通概率排序。
  • D：每次贪心往后匹配尽可能长的子序列。
  • E：线段树维护区间点和对角点最右最左点和区间最近点对的距离，合并显然。修改都是单点修改，非常容易。**几何部分题解@sub
  • F：f[i][mask]以i为根，包含mask的子树贡献，转移f[i][mask]=min(f[i][mask/j/mask']+f[j][j|mask']+dis[i][j]*(size[mask']+1)*(n-size[mask']-1))
  • G：先跑出普通的MST。然后对于每个点，将这个点的所有边都变为边权为0加入MST动态维护，同时将维护过程中加入的边全都记下来。结束之后将这些边全都删掉，再将删掉的边全都加回去。这么做的正确性显然，考虑kruskal算法的过程，显然会先考虑这些边权为0的边，并且这些边不可能构成环，所以这些边一定都在MST上，所以结束之后全都删掉即可。
  • H：sub
  • I：考虑对串建立SAM，则每插入一个字符后的答案为parent树上每个节点代表的子串长度个数*Right集合大小之和，用LCT维护parent树即可。
  • J：对于一个区间[l,r]，若它是单调的，则显然先手必败。若去掉l或者r后变成了单调的，则显然先手必胜。若[l+1,r−1]是单调的，那么同理先手必败。若[l,r−2]是单调的，那么先手若取r会导致后手必胜，后手同理，故两人会一直取l直到出现上面第一种或者第二种情况，可以根据奇偶性判断。同理可以得出是单调的情形的处理方法。除此之外，有[l,r]的答案等于[l+1,r−1]的答案，二分找到最小的k满足[l+k,r−k]可以由上面方法直接判断出胜负即可，另有一条式子win[l,r]=(!win[l+1,r])|(!win[l,r-1])。ps：至于为什么[l,r]=[l+1,r-1]，其实我觉得一点都不显然，问了下Claris和秋少，他们也不懂....咕咕咕 .......然后我画了个图，似乎能prove了。

  • K：考虑矩阵维护，发现存在逆矩阵，维护（逆）矩阵前缀和的最后一行（列）即可。
  • L：发现2i步操作效果是取间隔为2i-1次异或起来，倍增即可。
  • Claris

补题

附加文件