2016-E33-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Time||Problem||Result||
||04:59:08||C||Wrong Answer !#2||
||04:56:48||C||Wrong Answer !#2||
||02:55:02||F||Accepted||
||01:39:21||G||Accepted||
||01:12:45||H||Accepted||
||01:09:31||H||Time Limit Exceeded !#10||
比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day3.htm
start at 10:00
== 流水账 ==
== 总结 ==
== 题解 ==
=== A. Random Numbers [JTJL, sfiction] ===
首先在一个可能的范围内枚举m。
Sol1：解同余方程nk=Sa-Sb(mod m)，有gcd(n,m)个解。然后枚举A中的数用map检查即可，如果不符会快速退出。
Sol2：计算A/B中两两差平方和Sa和Sb，(Sa-Sb)%m=0。可以判掉绝大多数非法的m。确定k可以对A/B取模并排序，然后取循环差分序列做kmp（A加倍）求解（或者最小表示法）。
=== C. Eulerian Orientation [sfiction] ===
设有R个基本环，共有2^R^种方案。x^2^之和即为同时出现在一个方案中的边对(u,v)总数。(u,u)共出现2^R-1^次。对于(u,v)，设u所在环为A个，v所在环为B个，公共环为C个。若A>C&&B>C。则共2^C+A-C-1+B-C-1+rest^=2^n-2^。A>B=C时同样是2^n-2^。但当A=B=C时为2^n-1^。因此要特别处理所在环集合相同的边对数。这可以通过对边集合hash来完成。给每个环random一个seed，返祖边只在一个基本环上，其他边则DFS一遍计算，因为需要可逆性质，可以对seed求和或者异或和。注意R=0和R=1的情况。O(nlogn)。
=== D. Tube Master II [JTJL] ===
只有唯一解，可以递推。对于格点(x,y)，根据其左侧和上方、(x,y+1)的上方三条边的状态，再加上(x,y)右下的格子的数字，可以唯一确定(x,y)下方和右侧的边的状态。外部边均不存在，不需要枚举边界。O(nm)。
=== F. Median on Binary Tree [JTJL, sfiction] ===
在一个有序序列中，将不小于x的数标为1，小于x的数标为-1，则序列和s>=1则表示中位数>=x。因此在树上按此标号之后，有和>=1的子树即表示有解。加入a的偏移之后，相当于增加头部的-1，因此限制为s>=a+1。树上最大和连通块只需树形DP求每个点为根的最大子树（可能不是极大子树）即可。于是只要将树上所有点设为-1。初始中位数为n，从小到大枚举a，当不存在满足要求的子树时则将中位数-1并更新子树，由于深度只有logn，暴力沿上升路径更新即可。O(nlogn)。
=== G. Card Shuffling [JTJL, sficiton] ===
首先发现[1,2,...,k-1,k,x,...]可以快速模拟（？？？？）。而对于1位于位置x的情况，可以发现消耗步数f(x)<=f(x-1)+f(x-2)。
=== H. Independent Events [JTJL, Akalm] ===
ln(1-x)泰勒展开前数项，用线段树维护。O(n+qlogn)。
=== I. Territory Game [sfiction] ===
分类讨论。若k<2d，则双方无法互达，答案为0。若k=2t，如果相对走，并且k为奇数，A会因为先手会损失一个点，结果为-1。如果，A不能进入B的可达范围，因此断开一条边，如果A出发的最长链>=t，则可以使结果为0。若k=2t+1，则B会面临类似情况，也断开边求从B最长链。某点出发最长链必定结束于直径其中一端。可以用树形DP求出断开任意边两侧子树的直径。DP为O(n)，距离计算和断边位置需要LCA。O(nlogn)。
树形DP可以down+up，叉姐的方法只需要down。首先求出整棵树的直径，然后以两个端点为根分别down。如果断在直径上，则两侧子树会分别计算其一侧。如果不断在直径上，则一侧会被计算两次，另一侧则显然保留原直径。| Time | Problem | Result |
| 04:59:08 | C | Wrong Answer !#2 |
| 04:56:48 | C | Wrong Answer !#2 |
| 02:55:02 | F | Accepted |
| 01:39:21 | G | Accepted |
| 01:12:45 | H | Accepted |
| 01:09:31 | H | Time Limit Exceeded !#10 |
比赛链接: http://10.71.10.90/sfiction/ranklist/ICPCCamp2017/ICPCCamp2017-Day3.htm
start at 10:00
流水账
总结
题解
A. Random Numbers [JTJL, sfiction]
首先在一个可能的范围内枚举m。
Sol1：解同余方程nk=Sa-Sb(mod m)，有gcd(n,m)个解。然后枚举A中的数用map检查即可，如果不符会快速退出。
Sol2：计算A/B中两两差平方和Sa和Sb，(Sa-Sb)%m=0。可以判掉绝大多数非法的m。确定k可以对A/B取模并排序，然后取循环差分序列做kmp（A加倍）求解（或者最小表示法）。
C. Eulerian Orientation [sfiction]
设有R个基本环，共有2R种方案。x2之和即为同时出现在一个方案中的边对(u,v)总数。(u,u)共出现2R-1次。对于(u,v)，设u所在环为A个，v所在环为B个，公共环为C个。若A>C&&B>C。则共2C+A-C-1+B-C-1+rest=2n-2。A>B=C时同样是2n-2。但当A=B=C时为2n-1。因此要特别处理所在环集合相同的边对数。这可以通过对边集合hash来完成。给每个环random一个seed，返祖边只在一个基本环上，其他边则DFS一遍计算，因为需要可逆性质，可以对seed求和或者异或和。注意R=0和R=1的情况。O(nlogn)。
D. Tube Master II [JTJL]
只有唯一解，可以递推。对于格点(x,y)，根据其左侧和上方、(x,y+1)的上方三条边的状态，再加上(x,y)右下的格子的数字，可以唯一确定(x,y)下方和右侧的边的状态。外部边均不存在，不需要枚举边界。O(nm)。
F. Median on Binary Tree [JTJL, sfiction]
在一个有序序列中，将不小于x的数标为1，小于x的数标为-1，则序列和s>=1则表示中位数>=x。因此在树上按此标号之后，有和>=1的子树即表示有解。加入a的偏移之后，相当于增加头部的-1，因此限制为s>=a+1。树上最大和连通块只需树形DP求每个点为根的最大子树（可能不是极大子树）即可。于是只要将树上所有点设为-1。初始中位数为n，从小到大枚举a，当不存在满足要求的子树时则将中位数-1并更新子树，由于深度只有logn，暴力沿上升路径更新即可。O(nlogn)。
G. Card Shuffling [JTJL, sficiton]
首先发现[1,2,...,k-1,k,x,...]可以快速模拟（？？？？）。而对于1位于位置x的情况，可以发现消耗步数f(x)<=f(x-1)+f(x-2)。
H. Independent Events [JTJL, Akalm]
ln(1-x)泰勒展开前数项，用线段树维护。O(n+qlogn)。
I. Territory Game [sfiction]
分类讨论。若k<2d，则双方无法互达，答案为0。若k=2t，如果相对走，并且k为奇数，A会因为先手会损失一个点，结果为-1。如果，A不能进入B的可达范围，因此断开一条边，如果A出发的最长链>=t，则可以使结果为0。若k=2t+1，则B会面临类似情况，也断开边求从B最长链。某点出发最长链必定结束于直径其中一端。可以用树形DP求出断开任意边两侧子树的直径。DP为O(n)，距离计算和断边位置需要LCA。O(nlogn)。
树形DP可以down+up，叉姐的方法只需要down。首先求出整棵树的直径，然后以两个端点为根分别down。如果断在直径上，则两侧子树会分别计算其一侧。如果不断在直径上，则一侧会被计算两次，另一侧则显然保留原直径。