2017-Sp211-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
A和I是个人选拔赛原题，cjb出门上D，然后yzc敲了个线段树就过了。然后yzc写J，结论错了一次，期间疯狂开题，口胡了F和B，开出了L，J过了之后sub写K，也一发过了。yzc开始写C，sub推E，cjb准备L，yzc写得很艰辛，后来一起帮忙调，对拍C3y。最后sub rush E，没写完，终榜6题rk8，SJTU 7题rk6，MSU 10题rk1，感觉大家都是做过的啊.....
== 总结 ==
=== chenjb ===
开题开到写不完，居然还有我选的个人选拔赛题....估计来源是JAG2013左右的题目选集吧。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：压缩状态后广搜。

 * B：几何@sub

 * C：如果AB最高位不同，则B可确定，A可二分出来；否则AB差值确定，dfs每一次向下递归，要么这一位的k等于AB的差，要不k=0，分别对应二进制的这一位是1还是0，对于每一位AB不同的情况，B的值可确定，由于差值已知，A也确定，直接check即可。

 * D：树链剖分后线段树维护lmax,rmax,max和标记。

 * E：数学@sub

 * F：将buffer中从一开始到最后状态的每一棵树的大小组成的序列称为A，则A[i]都是由A[i-1]经过(A[i]-1)/(A[i-1]-1)-1次粘贴得到的。考虑最终状态是由T得到的，枚举T的大小k，将原树不断地拆出大小恰为k的树，若所有拆出的部分形状相同，则得到了一个合法的T。枚举约数，计算出所有合法的T大小k放入集合S。则任意一个A[i]的取值都是S中的一个数。因为可塑性的传递性，如果S中两数x,y满足倍数关系，则x一定可以通过变换得到y。集合S的大小为O(约数个数)，再通过dp转移即可得到最少粘贴次数，即f[i]=min(f[j]+(i-1)/(j-1)-1),(i,j∈S且(i-1)/(j-1)==0)。判定时具体实现可以递归，返回时检查子树大小是否恰为k，如果大于k则不合法，等于k的话判定哈希值是否相同并将其置换为单点，小于k则继续向上合并。

 * G：快乐轮廓线@yzc

 * H：tree decomposition dp?? @yzc

 * I：dp[i][j][mask] 表示确定了前 i 行，并且在第 i 行确定了前 j 列，此 时最后 C 个被确定的格子(可能跨行)在 mask 的位置上有字符 时的 dp 值。通过 j 可以确定当前这行用了哪些字符，即将摆放什么字符。另外还可以通过 j 知道 mask 里包含了上面那行的哪些字符。从而知道转移时是 +0 还是 +2 (和左边相同或者和上面相同) 还是 +4 (两边都相同)。注意到关系是双向的所以不是 +1 +2 而是 +2 +4。

 * J：显然一个点的子树间不可能互相穿插，所以子树按大小的顺序排列。

 * K：取出所有交点，对于每条原线段，把它拆成极小线段，并维护端点关系，取出终点所在联通块，把所有塞子塞上，然后再floodfill一次。

 * L：可以理解为一个找负权回路的模板题，有tot=(4*6)*h*w个状态，然后如果被更新了超过tot次就有无限解，否则输出答案，更新时暴力比较字符串大小。

 * M：按题意模拟，注意如果出现flip的字母，所有的字母都需要从右往左Parse。

流水账

A和I是个人选拔赛原题，cjb出门上D，然后yzc敲了个线段树就过了。然后yzc写J，结论错了一次，期间疯狂开题，口胡了F和B，开出了L，J过了之后sub写K，也一发过了。yzc开始写C，sub推E，cjb准备L，yzc写得很艰辛，后来一起帮忙调，对拍C3y。最后sub rush E，没写完，终榜6题rk8，SJTU 7题rk6，MSU 10题rk1，感觉大家都是做过的啊.....

总结

chenjb

开题开到写不完，居然还有我选的个人选拔赛题....估计来源是JAG2013左右的题目选集吧。

oipotato

subconscious

题解

  • A：压缩状态后广搜。
  • B：几何@sub
  • C：如果AB最高位不同，则B可确定，A可二分出来；否则AB差值确定，dfs每一次向下递归，要么这一位的k等于AB的差，要不k=0，分别对应二进制的这一位是1还是0，对于每一位AB不同的情况，B的值可确定，由于差值已知，A也确定，直接check即可。
  • D：树链剖分后线段树维护lmax,rmax,max和标记。
  • E：数学@sub
  • F：将buffer中从一开始到最后状态的每一棵树的大小组成的序列称为A，则A[i]都是由A[i-1]经过(A[i]-1)/(A[i-1]-1)-1次粘贴得到的。考虑最终状态是由T得到的，枚举T的大小k，将原树不断地拆出大小恰为k的树，若所有拆出的部分形状相同，则得到了一个合法的T。枚举约数，计算出所有合法的T大小k放入集合S。则任意一个A[i]的取值都是S中的一个数。因为可塑性的传递性，如果S中两数x,y满足倍数关系，则x一定可以通过变换得到y。集合S的大小为O(约数个数)，再通过dp转移即可得到最少粘贴次数，即f[i]=min(f[j]+(i-1)/(j-1)-1),(i,j∈S且(i-1)/(j-1)==0)。判定时具体实现可以递归，返回时检查子树大小是否恰为k，如果大于k则不合法，等于k的话判定哈希值是否相同并将其置换为单点，小于k则继续向上合并。
  • G：快乐轮廓线@yzc
  • H：tree decomposition dp?? @yzc
  • I：dp[i][j][mask] 表示确定了前 i 行，并且在第 i 行确定了前 j 列，此 时最后 C 个被确定的格子(可能跨行)在 mask 的位置上有字符 时的 dp 值。通过 j 可以确定当前这行用了哪些字符，即将摆放什么字符。另外还可以通过 j 知道 mask 里包含了上面那行的哪些字符。从而知道转移时是 +0 还是 +2 (和左边相同或者和上面相同) 还是 +4 (两边都相同)。注意到关系是双向的所以不是 +1 +2 而是 +2 +4。
  • J：显然一个点的子树间不可能互相穿插，所以子树按大小的顺序排列。
  • K：取出所有交点，对于每条原线段，把它拆成极小线段，并维护端点关系，取出终点所在联通块，把所有塞子塞上，然后再floodfill一次。
  • L：可以理解为一个找负权回路的模板题，有tot=(4*6)*h*w个状态，然后如果被更新了超过tot次就有无限解，否则输出答案，更新时暴力比较字符串大小。
  • M：按题意模拟，注意如果出现flip的字母，所有的字母都需要从右往左Parse。
附加文件