2017-Sp199-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，读了大部分的题目，sub试图上机写C，写了一点之后下机思考，cjb开出了I，上机写I，wa了之后艹了一下发现没有初始化一个数组，修改后'''I2y58'''。sub上机写C，'''C3y93'''。cjb上机写D，sub和yzc推A，之后D做法假了，yzc上机开始写A，'''A2y157'''。之后无题可做，只好让yzc试下E的水，wa了2发之后tle了，之后random_shuffle了一下枚举顺序居然过了，'''E4y191'''。之后cjb终于开出了D，sub确认了做法，cjb让yzc抄了个欧拉回路之后上机，样例炸了之后自闭，sub上机搞了搞发现了小问题，'''D3y254'''。最后时间啥都做不了，sub上机写了个K的暴力t了，最后5题rk9，MIT和MSU神仙打架8题，dls回来打酱油7题，UWr1今天意外地神勇6题，搞笑网友6题，然后jsb 5题凭借良好罚时rk6，sjtu1 rk7，buaa1 rk8。
== 总结 ==
=== chenjb ===
D题把我搞自闭了，今天签完到之后剩下能搞的题都很大，yzc做出做E的决策是正确的，不过我们队依然不具备强艹G的能力，以后努力一下在比赛中争取合理地出这么一个笨重的题。
=== oipotato ===
欲说还休。
=== subconscious  ===
欲言又止。
== 题解 ==
 * A：显然每棵树的值在p进制下都是1后面跟着一堆0或-1。把n拆成p进制，两棵树中较大的那个p进制下最高位的1跟n最高位相同或多1，枚举较小的那个最高位1在哪，减去n之后根据每一位剩下的数字求得方案数。

 * B：

 * C：把n^2^个线段枚举出来，排序，维护所有点到线段距离，均摊复杂度是n^2^的。

 * D：根据2-factor theorem，任何一张度数相同(regular graph)且度数为偶数2k的图，都可以拆成k个边不相交的包含所有节点且度数皆为2的子图。先对原图找到任意一条欧拉回路，之后将节点拆成i和i'，欧拉回路上所有边(i,j)拆成(i,j')，此图存在k个完美匹配，且每个完美匹配对应一组拆分。因此此题只需要跑出欧拉回路之后以相同的建图方式，跑网络流或匈牙利跑出一组匹配即可。

 * E：暴力搜索，注意常数。本队过题时random_shuffle了空位置。

 * F：

 * G：考虑一个4*4的方格，枚举下面3行的2^12^种状态，枚举所有能把最后一行填满，并且填的块至少有一个方格在第一行的方案，得到转移矩阵。显然，答案就是满状态转移n次之后满状态的答案。所以我们只保留从满状态出发能到达，同时能到达满状态的状态，发现只有68种。矩阵乘法加速转移即可。

 * H：

 * I：考虑后缀数组的h数组，将lcs转化为rmq，枚举每个h作为rmq区间的最小值，二分找到两段最远距离，然后再取出最小下标更新答案，注意i和i本身也是n-i+1长度的一个可能的解。

 * J：

 * K：推出式子后用java大整数实现，为了优化运算，需要对式子约分化简，同时在运算时尽量避免高精之间的运算，本地测试时限为3s以下的时候能够在评测机上通过极限数据，原始式子为Σ(-1)^i-k^*C(i,k)*(C(2n-i,i)+C(2n-i-1,i-1))/(2n-i)!!, (2n-i)!!=(2n)!/(n!*2^n^)，附一份代码。

流水账

出门各自看题，读了大部分的题目，sub试图上机写C，写了一点之后下机思考，cjb开出了I，上机写I，wa了之后艹了一下发现没有初始化一个数组，修改后I2y58。sub上机写C，C3y93。cjb上机写D，sub和yzc推A，之后D做法假了，yzc上机开始写A，A2y157。之后无题可做，只好让yzc试下E的水，wa了2发之后tle了，之后random_shuffle了一下枚举顺序居然过了，E4y191。之后cjb终于开出了D，sub确认了做法，cjb让yzc抄了个欧拉回路之后上机，样例炸了之后自闭，sub上机搞了搞发现了小问题，D3y254。最后时间啥都做不了，sub上机写了个K的暴力t了，最后5题rk9，MIT和MSU神仙打架8题，dls回来打酱油7题，UWr1今天意外地神勇6题，搞笑网友6题，然后jsb 5题凭借良好罚时rk6，sjtu1 rk7，buaa1 rk8。

总结

chenjb

D题把我搞自闭了，今天签完到之后剩下能搞的题都很大，yzc做出做E的决策是正确的，不过我们队依然不具备强艹G的能力，以后努力一下在比赛中争取合理地出这么一个笨重的题。

oipotato

欲说还休。

subconscious

欲言又止。

题解

  • A：显然每棵树的值在p进制下都是1后面跟着一堆0或-1。把n拆成p进制，两棵树中较大的那个p进制下最高位的1跟n最高位相同或多1，枚举较小的那个最高位1在哪，减去n之后根据每一位剩下的数字求得方案数。
  • B：
  • C：把n2个线段枚举出来，排序，维护所有点到线段距离，均摊复杂度是n2的。
  • D：根据2-factor theorem，任何一张度数相同(regular graph)且度数为偶数2k的图，都可以拆成k个边不相交的包含所有节点且度数皆为2的子图。先对原图找到任意一条欧拉回路，之后将节点拆成i和i'，欧拉回路上所有边(i,j)拆成(i,j')，此图存在k个完美匹配，且每个完美匹配对应一组拆分。因此此题只需要跑出欧拉回路之后以相同的建图方式，跑网络流或匈牙利跑出一组匹配即可。
  • E：暴力搜索，注意常数。本队过题时random_shuffle了空位置。
  • F：
  • G：考虑一个4*4的方格，枚举下面3行的212种状态，枚举所有能把最后一行填满，并且填的块至少有一个方格在第一行的方案，得到转移矩阵。显然，答案就是满状态转移n次之后满状态的答案。所以我们只保留从满状态出发能到达，同时能到达满状态的状态，发现只有68种。矩阵乘法加速转移即可。
  • H：
  • I：考虑后缀数组的h数组，将lcs转化为rmq，枚举每个h作为rmq区间的最小值，二分找到两段最远距离，然后再取出最小下标更新答案，注意i和i本身也是n-i+1长度的一个可能的解。
  • J：
  • K：推出式子后用java大整数实现，为了优化运算，需要对式子约分化简，同时在运算时尽量避免高精之间的运算，本地测试时限为3s以下的时候能够在评测机上通过极限数据，原始式子为Σ(-1)i-k*C(i,k)*(C(2n-i,i)+C(2n-i-1,i-1))/(2n-i)!!, (2n-i)!!=(2n)!/(n!*2n)，附一份代码。
附加文件