2017-Sp276-team2

从 Trac 迁移的文章

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

原文章内容如下：

== 流水账 ==
本来开场还算顺利，结果yandex炸了，等了一年返回来个RE，换了oj后感觉魂都没了，cjb和sub一年想不出J，sub和yzc的E炸穿了。最后时刻做G，感觉大概还差30min。
=== chenjb ===
这个J让我好自闭啊...不想输啊nmd
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：区间[l,r]shuffle就是平分权值，线段树维护即可。

 * B：

 * C：本质上依然是一个二分的交互题，每次选一行(列)，求得该行(列)最大值，用该值周围8连通更新目前找到的最大值，如果周围找不到比自己大的就是答案，然后只保留靠近当前全局最大值的一半，行列交替做。

 * D：

 * E：首先考虑所有行一起的答案。设f[x]为每一行在x之前的数字都被选走，最后连续k个为x，且其他数字都没有连续出现k次的方案数。只考虑x连续出现k次的方案数是一个简单的组合数式子，考虑去掉别的数字出现k次的方案，不妨设第一次连续出现k次的数字为y，则y对x的贡献也是f[y]和一些组合数的乘积。将所有满足条件的y的贡献都减去即可。为了方便实现，我们在每一行最后加一个数字n+1，则最后的答案就是f[n+1]/k!。这样的单次复杂度是n^2^k的，总复杂度为n^2^k^3^。考虑固定行的起点，枚举行的终点，每次新加入一行，所有的组合数都可以维护，复杂度n^2^k^2^。由于随机的性质，考虑满足条件的数对(x,y)，在只有一行的时候，数量为n^2^/2，然后每多一行，原来的数对继续满足条件的概率都为1/2，所以数量/2，所以对于每个行起点，行终点的移动过程中，满足条件的数对(x,y)的总数为n^2^，所以我们在新加入一行的时候维护每个x合法的y即可，复杂度nk(n+k)。

 * F：考虑DP，L(l,x)表示显示数字为x，区间范围为[l,x)的最小步数，R(x,r)类似。这样的状态数是n^2^。注意到，最多只需要45步，即可完成所有数字的确定。注意到，对于L(l,x)，l变小的过程中，答案不递减，考虑状态FL(c,x)表示，L(l,x)中，步数小于等于c的l的最小值，FR(c,x)类似。定义dist(x,y)为将x变为y的最小步数，对于FL(c,x)，考虑所有的m满足FR(c-dist(x,m)-1,m)>=x-1，取FL(c-dist(x,m)-1,m)的最小值即为FL(c,x)的值。显然，在不考虑dist(x,m)时，x越小，满足条件的m越多，所以我们考虑从大到小计算所有的FL(c,x)，由于dist的取值在1到5之间，我们对于每一个可能的m，直接枚举dist的值d，并插入FR(c-d-1,m)对应的表中，在x递减的过程中，不断的插入合适的m并维护最值。那么对于每一个x，我们就需要每一个(d,m)中满足dist(x,m)=d的贡献，这在x变化过程中不容易维护，于是我们考虑直接枚举m经过d步变化之后是谁，由于一次变化可以将一位变成任何值，所以我们不必在意具体值是多少，可以简单的将其视为一个'?',并把变化后的带'?'的数字视为11进制数字，然后对每个可能的11进制的结果都记录最小值，对于每个m，所有的d的变化方案共2^5^。然后对于每个x，询问时枚举哪几个位置改变，将其改为'?'，然后转化成11进制，取出最小值，方案数也是2^5^。FR类似。经过45次计算之后就得到了所有的结果，对于每个询问l,r，枚举第一步变成哪个数字x,再枚举剩下的步数c，只要FL(c,x)<=l且FR(c,x)>=r就可以更新答案。总复杂度(5*10^5^+32*10^5^+11^5^)*45。

 * G：0:110/011  1:111  2:010  3:101，1表示有木棍，状态3直接将游戏隔成两个独立区域，状态2其实是左右两边的人不能变成状态2，但是再往外走一步就随意了，所以是两个独立的游戏和两个单点的不能变为状态2的游戏，而且状态2、3之上不能再做操作，所以只需要枚举每一位是0还是1，直接dp。

 * H：变种dij，显然不会往回走，决策是将出边目的地从优到劣排序，每次选择最优的走，如果被退回，就决策1是强制取最优，2是尝试次优，这个权值可以维护。

 * I：称(v,r)为一个树上的圆，则显然两个圆的交集还是一个圆，圆心v为树上的点或是边的中点。对于每个询问，设ansv为去掉点v的交集的大小，ans为所有人的交集的大小，则显然答案为sigma(ansv)-(k-1)*ans，剩下的问题就是问到一个点距离为x的点有多少个，这是经典的点分治树问题。

 * J：i+1,j和i,j+1相等的需要出现至少2次，而且是可互达的。

 * K：SAM+LCT。

流水账

本来开场还算顺利，结果yandex炸了，等了一年返回来个RE，换了oj后感觉魂都没了，cjb和sub一年想不出J，sub和yzc的E炸穿了。最后时刻做G，感觉大概还差30min。

chenjb

这个J让我好自闭啊...不想输啊nmd

oipotato

subconscious

题解

A：区间[l,r]shuffle就是平分权值，线段树维护即可。
B：
C：本质上依然是一个二分的交互题，每次选一行(列)，求得该行(列)最大值，用该值周围8连通更新目前找到的最大值，如果周围找不到比自己大的就是答案，然后只保留靠近当前全局最大值的一半，行列交替做。
D：
E：首先考虑所有行一起的答案。设f[x]为每一行在x之前的数字都被选走，最后连续k个为x，且其他数字都没有连续出现k次的方案数。只考虑x连续出现k次的方案数是一个简单的组合数式子，考虑去掉别的数字出现k次的方案，不妨设第一次连续出现k次的数字为y，则y对x的贡献也是f[y]和一些组合数的乘积。将所有满足条件的y的贡献都减去即可。为了方便实现，我们在每一行最后加一个数字n+1，则最后的答案就是f[n+1]/k!。这样的单次复杂度是n²k的，总复杂度为n²k³。考虑固定行的起点，枚举行的终点，每次新加入一行，所有的组合数都可以维护，复杂度n²k²。由于随机的性质，考虑满足条件的数对(x,y)，在只有一行的时候，数量为n²/2，然后每多一行，原来的数对继续满足条件的概率都为1/2，所以数量/2，所以对于每个行起点，行终点的移动过程中，满足条件的数对(x,y)的总数为n²，所以我们在新加入一行的时候维护每个x合法的y即可，复杂度nk(n+k)。
F：考虑DP，L(l,x)表示显示数字为x，区间范围为[l,x)的最小步数，R(x,r)类似。这样的状态数是n²。注意到，最多只需要45步，即可完成所有数字的确定。注意到，对于L(l,x)，l变小的过程中，答案不递减，考虑状态FL(c,x)表示，L(l,x)中，步数小于等于c的l的最小值，FR(c,x)类似。定义dist(x,y)为将x变为y的最小步数，对于FL(c,x)，考虑所有的m满足FR(c-dist(x,m)-1,m)>=x-1，取FL(c-dist(x,m)-1,m)的最小值即为FL(c,x)的值。显然，在不考虑dist(x,m)时，x越小，满足条件的m越多，所以我们考虑从大到小计算所有的FL(c,x)，由于dist的取值在1到5之间，我们对于每一个可能的m，直接枚举dist的值d，并插入FR(c-d-1,m)对应的表中，在x递减的过程中，不断的插入合适的m并维护最值。那么对于每一个x，我们就需要每一个(d,m)中满足dist(x,m)=d的贡献，这在x变化过程中不容易维护，于是我们考虑直接枚举m经过d步变化之后是谁，由于一次变化可以将一位变成任何值，所以我们不必在意具体值是多少，可以简单的将其视为一个'?',并把变化后的带'?'的数字视为11进制数字，然后对每个可能的11进制的结果都记录最小值，对于每个m，所有的d的变化方案共2⁵。然后对于每个x，询问时枚举哪几个位置改变，将其改为'?'，然后转化成11进制，取出最小值，方案数也是2⁵。FR类似。经过45次计算之后就得到了所有的结果，对于每个询问l,r，枚举第一步变成哪个数字x,再枚举剩下的步数c，只要FL(c,x)<=l且FR(c,x)>=r就可以更新答案。总复杂度(5*10⁵+32*10⁵+11⁵)*45。
G：0:110/011 1:111 2:010 3:101，1表示有木棍，状态3直接将游戏隔成两个独立区域，状态2其实是左右两边的人不能变成状态2，但是再往外走一步就随意了，所以是两个独立的游戏和两个单点的不能变为状态2的游戏，而且状态2、3之上不能再做操作，所以只需要枚举每一位是0还是1，直接dp。
H：变种dij，显然不会往回走，决策是将出边目的地从优到劣排序，每次选择最优的走，如果被退回，就决策1是强制取最优，2是尝试次优，这个权值可以维护。
I：称(v,r)为一个树上的圆，则显然两个圆的交集还是一个圆，圆心v为树上的点或是边的中点。对于每个询问，设ansv为去掉点v的交集的大小，ans为所有人的交集的大小，则显然答案为sigma(ansv)-(k-1)*ans，剩下的问题就是问到一个点距离为x的点有多少个，这是经典的点分治树问题。
J：i+1,j和i,j+1相等的需要出现至少2次，而且是可互达的。
K：SAM+LCT。