2017-Sp64-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
 * 题目来源：Petrozavodsk Winter Training Camp 2018: Jagiellonian U Contest
 * 现场&Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7354/standings/
== 流水账 ==
开场各自看题，很快看到毛子过了I，cjb上机打I的暴力找到规律，'''I1y14'''。yzc和sub看了看F和B，yzc上机'''F1y17'''。yzc继续写B，wa了一发打印检查，cjb和sub讨论了L，cjb上机写L，很快'''L1y50'''。yzc上机调B，找到了corner case，修改后'''B2y53'''。sub表示会做E，让yzc上机写E，cjb和yzc讨论了C，sub写着感觉不对，下机思考，和sub交流过后，让yzc上机写C的cdq，之后'''C1y89'''。接下来三人一起研究A，得到了一个贪心，yzc上机写A，wa了后写了对拍，之后终于'''A3y129'''。接下来三个人一起研究E和G，sub提出了一个G的贪心，yzc写了获得wa。之后三人决定暴力搜索过E，yzc上机写。期间搜索因为细节问题出现了很多bug，使用了对拍，但是还是wa，最后终于变成了tle。最后半小时，sub终于提出了正确的dp，yzc迅速上机，最后'''E10y293'''。今天表现非常欠佳，一队做了8个题，清北复都12题ak了，交大10题，中大和福大也9题。
== 总结 ==
=== chenjb ===
今天真的非常爆炸了....在这种水题场，E实在是卡得太久而且太伤了....而且确实别的题目都需要机时和讨论时间，不过另一个bug是写E的搜索花了比计划多了n倍的时间，这是很久很久没发生过的，我认为是小概率事件。首先要尽快把所有题都补了，出现一点波动是正常的，但是要引起注意。另外一个自己的问题就是G的做法其实已经想到了prim，但是当时顾着看E，并没有拿出来讨论，后面就顾不上了，这也是一个失误，赛后一讨论就马上想到了，十分可惜。
[[BR]] [[BR]] 呜呜呜，楼下yzc说的真对啊，我感觉我和yzc要提高套路水平啊.....从八月到现在有所好转了但是还是不太够啊QAQ
=== oipotato ===
E题没想出来感觉并不是sub的锅，我和cjb的DP姿势还是太差了，回想一下似乎比较巧妙的DP状态都是sub设计的，我和cjb还是要提高我们的DP姿势。
=== subconscious  ===
爆炸。E题最后才想到，真是太菜了我...
== 题解 ==
 * D：
   * 题意：求一个右上角缺(n-a)*(n-a)的上三角，左下角缺a*a的下三角的匹配数。a<=500,n<=1000000。
   * 题解：考虑大力容斥减掉匹配落入左下角的情况。可以发现落入数量确定时上n-a行贡献确定，最后a行贡献可以直接记录前a+1~a+i行有多少行落入来O(n^2^)dp获得，最后乘上前n-a行的贡献容斥即可。
 * E：
   * 题意：给定n个长度为k的01串，求出最少几步可以将所有01串区分开，每一步区分一个二进制位。
   * 题解：使用三进制DP f[opt]，对于某一位若为0或1，则表示处理的是这一位为0或1的那些串，对于某一位为2，则不设限制。每一次枚举一位2变为0或1转移。边界为当前三进制对应的串的数量<=1。
 * G：
   * 题意：给定m个长度为n的01串，串与串之间的距离定义为两串的海明距离，求最小生成树。
   * 题解：考虑prim算法，关键就在于怎么维护每个点当前与生成树的距离，显然每个点的距离取值在1-20，那么每一次更新使用bfs，一步改变一个bit位，一旦不能更新某个点就不继续扩展。由于每个点最多被更新20次，故复杂度是能保证的。
 * H：
   * 题意：有一条从n*n方格左上角到右下角只向下向右再从右下角到左上角只向上向左的路径，给出每行每列有多少方格被经过，求可能的路径方案数。
   * 题解：方格的染色状况可以直接通过推理得出，维护两个pointer，每次一个pointer把对应行/列的步数走完再跳到下一列/行即可，两个pointer轮流执行，注意特判交叉点的情况。最终方案数等于2^路径上交叉点数^。
 * J：
   * 题意：对于一个大整数x，以分解的形式给出(项数不超过150000），设定m<=150000，询问是否存在0<=k<=n<=m并且满足C(n,k)=x。
   * 题解：考虑枚举k，对于固定的k，C(n,k)是单调的，所以二分n，因为c(n,k)=fac[n]/fac[k]/fac[n-k]，所以log(C(n,k))=log(fac[n])-log(fac[k])-log(fac[n-k])，就可以用log来判定与x的大小了，最后得到一个可能解，检验下C(n',k')与x在模意义下是否相等即可，注意，n和k可以取到0，并且二分之后要上下扰动来防止精度造成的偏差，晃动+-2就足够了。
 * K：
   * 题意：给出一棵树，统计(x,y,z)满足d[x,y]=d[x,z]=d[y,z]，n<=100000。
   * 题解：(by '''只会口胡的cjb''')有一种水法：对于每个点先预处理出其第三深的深度，然后每个点暴力遍历至该深度然后统计答案，又或者直接视作有根树，对于每个点只取遍历时的次深深度，同样也是n次基于次深深度的遍历来统计答案(这些都是能被卡的...但是在yandex上过了)。比较靠谱的做法是我们考虑点分治的思想，对于一个分治的根，有两种情况：1.三个点位于三个不同的子树，即该分治根为三元组路径的交叉点；   2.两个点位于子树A，另一个点位于子树B，即三元组路径交叉点实际上是子树A中两点的lca；分成这两种情况后，实际上就不需要考虑点分治根的上传问题。对于第一种情况，点分治可以很方便的统计，对于第二种情况，在时间和空间上都比较麻烦，初步想法是考虑在dfs的时候就将其对答案的贡献算出来，而不是在分治点的地方进行统计，dfs的时候子树合并要注意将size小的子树合并到size大的子树，对于一个分叉，我们实际上只需要保存其对于分叉点向上到分治根路径长度的需求即可。注意到这样分析实际上可以不用点分治，而是直接对于整棵树进行启发式合并来完成统计。
   * '''真·题解'''：(by '''从nightfall学到新姿势的yzc''')我们设f[I][j]表示点I的子树中有多少和i距离为j的点，g[i][j]表示点i的子树中有多少点对只需要i再往外走j步就能构成符合题意的三元组了。容易得到转移方程(其中y为x的儿子):f[x][i]=sigma(f[y][i-1]),g[x][i]=sigma(g[y][i+1]+f[x][i]*f[y][i-1])。直接转移复杂度为n^2^，考虑对树进行长链剖分，每一次将重儿子链直接继承给父亲，其他儿子合并进去，复杂度为O(n)。                   

 [[BR]] [[BR]]* [https://wiki-nightfall.icpc-camp.org/Day3 Solution by Nightfall]

== 补题 ==
 * ~~D~~ by sub
 * ~~G~~ by yzc
 * ~~H~~ by sub
 * ~~J~~ by cjb
 * ~~K~~ by yzc

题目来源：Petrozavodsk Winter Training Camp 2018: Jagiellonian U Contest
现场&Camp排名：https://official.contest.yandex.com/itmo2018china/contest/7354/standings/

流水账

开场各自看题，很快看到毛子过了I，cjb上机打I的暴力找到规律，I1y14。yzc和sub看了看F和B，yzc上机F1y17。yzc继续写B，wa了一发打印检查，cjb和sub讨论了L，cjb上机写L，很快L1y50。yzc上机调B，找到了corner case，修改后B2y53。sub表示会做E，让yzc上机写E，cjb和yzc讨论了C，sub写着感觉不对，下机思考，和sub交流过后，让yzc上机写C的cdq，之后C1y89。接下来三人一起研究A，得到了一个贪心，yzc上机写A，wa了后写了对拍，之后终于A3y129。接下来三个人一起研究E和G，sub提出了一个G的贪心，yzc写了获得wa。之后三人决定暴力搜索过E，yzc上机写。期间搜索因为细节问题出现了很多bug，使用了对拍，但是还是wa，最后终于变成了tle。最后半小时，sub终于提出了正确的dp，yzc迅速上机，最后E10y293。今天表现非常欠佳，一队做了8个题，清北复都12题ak了，交大10题，中大和福大也9题。

总结

chenjb

今天真的非常爆炸了....在这种水题场，E实在是卡得太久而且太伤了....而且确实别的题目都需要机时和讨论时间，不过另一个bug是写E的搜索花了比计划多了n倍的时间，这是很久很久没发生过的，我认为是小概率事件。首先要尽快把所有题都补了，出现一点波动是正常的，但是要引起注意。另外一个自己的问题就是G的做法其实已经想到了prim，但是当时顾着看E，并没有拿出来讨论，后面就顾不上了，这也是一个失误，赛后一讨论就马上想到了，十分可惜。

呜呜呜，楼下yzc说的真对啊，我感觉我和yzc要提高套路水平啊.....从八月到现在有所好转了但是还是不太够啊QAQ

oipotato

E题没想出来感觉并不是sub的锅，我和cjb的DP姿势还是太差了，回想一下似乎比较巧妙的DP状态都是sub设计的，我和cjb还是要提高我们的DP姿势。

subconscious

爆炸。E题最后才想到，真是太菜了我...

题解

D：
- 题意：求一个右上角缺(n-a)*(n-a)的上三角，左下角缺a*a的下三角的匹配数。a<=500,n<=1000000。
- 题解：考虑大力容斥减掉匹配落入左下角的情况。可以发现落入数量确定时上n-a行贡献确定，最后a行贡献可以直接记录前a+1~a+i行有多少行落入来O(n²)dp获得，最后乘上前n-a行的贡献容斥即可。
E：
- 题意：给定n个长度为k的01串，求出最少几步可以将所有01串区分开，每一步区分一个二进制位。
- 题解：使用三进制DP f[opt]，对于某一位若为0或1，则表示处理的是这一位为0或1的那些串，对于某一位为2，则不设限制。每一次枚举一位2变为0或1转移。边界为当前三进制对应的串的数量<=1。
G：
- 题意：给定m个长度为n的01串，串与串之间的距离定义为两串的海明距离，求最小生成树。
- 题解：考虑prim算法，关键就在于怎么维护每个点当前与生成树的距离，显然每个点的距离取值在1-20，那么每一次更新使用bfs，一步改变一个bit位，一旦不能更新某个点就不继续扩展。由于每个点最多被更新20次，故复杂度是能保证的。
H：
- 题意：有一条从n*n方格左上角到右下角只向下向右再从右下角到左上角只向上向左的路径，给出每行每列有多少方格被经过，求可能的路径方案数。
- 题解：方格的染色状况可以直接通过推理得出，维护两个pointer，每次一个pointer把对应行/列的步数走完再跳到下一列/行即可，两个pointer轮流执行，注意特判交叉点的情况。最终方案数等于2^{路径上交叉点数}。
J：
- 题意：对于一个大整数x，以分解的形式给出(项数不超过150000），设定m<=150000，询问是否存在0<=k<=n<=m并且满足C(n,k)=x。
- 题解：考虑枚举k，对于固定的k，C(n,k)是单调的，所以二分n，因为c(n,k)=fac[n]/fac[k]/fac[n-k]，所以log(C(n,k))=log(fac[n])-log(fac[k])-log(fac[n-k])，就可以用log来判定与x的大小了，最后得到一个可能解，检验下C(n',k')与x在模意义下是否相等即可，注意，n和k可以取到0，并且二分之后要上下扰动来防止精度造成的偏差，晃动+-2就足够了。
K：
- 题意：给出一棵树，统计(x,y,z)满足d[x,y]=d[x,z]=d[y,z]，n<=100000。
- 题解：(by 只会口胡的cjb)有一种水法：对于每个点先预处理出其第三深的深度，然后每个点暴力遍历至该深度然后统计答案，又或者直接视作有根树，对于每个点只取遍历时的次深深度，同样也是n次基于次深深度的遍历来统计答案(这些都是能被卡的...但是在yandex上过了)。比较靠谱的做法是我们考虑点分治的思想，对于一个分治的根，有两种情况：1.三个点位于三个不同的子树，即该分治根为三元组路径的交叉点； 2.两个点位于子树A，另一个点位于子树B，即三元组路径交叉点实际上是子树A中两点的lca；分成这两种情况后，实际上就不需要考虑点分治根的上传问题。对于第一种情况，点分治可以很方便的统计，对于第二种情况，在时间和空间上都比较麻烦，初步想法是考虑在dfs的时候就将其对答案的贡献算出来，而不是在分治点的地方进行统计，dfs的时候子树合并要注意将size小的子树合并到size大的子树，对于一个分叉，我们实际上只需要保存其对于分叉点向上到分治根路径长度的需求即可。注意到这样分析实际上可以不用点分治，而是直接对于整棵树进行启发式合并来完成统计。
- 真·题解：(by 从nightfall学到新姿势的yzc)我们设f[I][j]表示点I的子树中有多少和i距离为j的点，g[i][j]表示点i的子树中有多少点对只需要i再往外走j步就能构成符合题意的三元组了。容易得到转移方程(其中y为x的儿子):f[x][i]=sigma(f[y][i-1]),g[x][i]=sigma(g[y][i+1]+f[x][i]*f[y][i-1])。直接转移复杂度为n²，考虑对树进行长链剖分，每一次将重儿子链直接继承给父亲，其他儿子合并进去，复杂度为O(n)。

* Solution by Nightfall

补题

D by sub
G by yzc
H by sub
J by cjb
K by yzc

附加文件

1.png by chenjb
180201chn.en.pdf by oipotato