2018-Reconquista-T52

从 Trac 迁移的文章

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

原文章内容如下：

== Contest Information ==

''' Petrozavodsk Summer 2016 - Moscow IPT Contest '''

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001483 Opentrains]

== 流水账 ==


== 总结 ==

=== lsmll ===
感觉我这场除了写了个签到题D之外就没什么贡献...?虽然我们过了最后只有三个过的B题，但是E和J这两个过的人多的没过，看来还要多学习。A题我们花的时间比较长，过的时候榜上基本都已经过了，感觉我和lzw学长不太擅长这类估价函数乱搞题，还是jsb学长更擅长，但他当时在写B。

=== jsb ===

开场被骗去写看上去傻乎乎的B题，但是因为写错一个细节，靠对拍才过，感觉很难过。

后期的E和J，都感觉快做出来了，但是求和式化简不了或者细节很头疼。哎姿势水平不够啊。

=== lzw ===
感觉有点菜，前期没什么贡献，就最后弄了一个C题出来。E题没搞出来说明数学姿势水平有待提高，I题的物理题一个人始终朝着另一个人移动是经典的模型，之后要去学习一下怎么处理这类问题。


== 补题 ==
E [jsb]

F [lzw]

G []

H []

I []

J [lsmll]


== 题解 ==

[https://wiki.icpc.camp/new-meta/2017/3/2%20Moscow%20IPT%20Contest New Meta][[br]]

[B by JSB]修改操作的and和or是类似的运算，都是强制把log个子树里某些位统一，只是改成0或者1的问题。分开考虑每一位。在线段树节点里，维护每个bit位在子树里是否完全相同。那么修改的时候，如果当前操作修改的那些位在子树里本来都一样，改完后必然也一样，我们可以立即停下来，打个标记并快速维护最小值信息；否则暴力递归下去即可。时间复杂度挺显然的，势能分析一下即可。这样应该是$O(30N\logN)$的。然后可以用bitset的思想，进行一些位运算的骚操作，复杂度降低成$O(N\logN)$。

[C by lzw] F[i][j][k]表示考虑前i个东西，且第i个距离它所在的block尾部还有j个位置（每次可以花B的代价新建一个block），k表示之前的block里面一共还有多少个空位（可能是负数，表示空位欠缺）的最优解。
每次转移考虑第i+1个东西是新建一个block，还是移动到某个block的空位里，还是留在当前的block里，还是移出当前的block来增加一个空位。[[br]]

[F by lzw] 考虑一个连通分量的答案。ai是奇数的边取值显然是任意的，因为可以来回走，每次+2，mod一个奇数ai后bi可以取到任意值，所以可以将奇数边连接的点合并缩点，最后答案乘以所有的奇数ai。然后考虑只有偶数边的一个图。每条边的bi显然也可以不断+2,所以分为两个等价类，bi是偶数一个，bi是奇数一个。所以将答案乘以所有的bi/2, 问题转化为，每条边经过之后就会取反，有多少种情况。 这个问题的答案是(C(N, 2)+1) * POW(2, M - N + 1) N,M是联通点数和边数. M - N + 1表示除掉生成树外，有这么多条多余的边，这些边各自对应DFS树上一个简单环，每个环可以取或者不取，这些环可以组合出图上任意一个简单环。前面(C(N, 2)+1)表示任意先走出一条路的方案数（+1表示一条边不走）。

[E by jsb]
　　我们设$f_L$表示$LCP \leq L$ 时的概率，要求不存在相同的长度为$L+1$的前缀。[[br]]
　　得$f_L=\frac{C_{2^{L+1}}^n*n!}{2^{(L+1)*n}}$。[[br]]
　　^最后答案即为：$\sum_{i=0}^{\infty} i*(f_{i+1}-f_i)$。[[br]]
　　^这个级数不能直接求和。因为要保留最后的分数，加到无穷显然是不现实的，只能改变求和顺序。注意到分子里实际上是一个下降幂，根据第一类斯特林数（有符号）的定义，有[[br]]
　　$x^{\lfloor n \rfloor}=\sum_{k=0}^n S1_{n,k}*x^k$。[[br]]
　　直接套用，并改变求和顺序，即可将无穷级数化为类等比数列。此题$N=10000$，可以直接暴力分治把$S1_{n,i}$求出来。数据再大一点可以分治FFT。[[br]]

Contest Information

Petrozavodsk Summer 2016 - Moscow IPT Contest

Opentrains

流水账

总结

lsmll

感觉我这场除了写了个签到题D之外就没什么贡献...?虽然我们过了最后只有三个过的B题，但是E和J这两个过的人多的没过，看来还要多学习。A题我们花的时间比较长，过的时候榜上基本都已经过了，感觉我和lzw学长不太擅长这类估价函数乱搞题，还是jsb学长更擅长，但他当时在写B。

jsb

开场被骗去写看上去傻乎乎的B题，但是因为写错一个细节，靠对拍才过，感觉很难过。

后期的E和J，都感觉快做出来了，但是求和式化简不了或者细节很头疼。哎姿势水平不够啊。

lzw

感觉有点菜，前期没什么贡献，就最后弄了一个C题出来。E题没搞出来说明数学姿势水平有待提高，I题的物理题一个人始终朝着另一个人移动是经典的模型，之后要去学习一下怎么处理这类问题。

补题

E [jsb]

F [lzw]

G []

H []

I []

J [lsmll]

题解

New Meta[[br]]

[B by JSB]修改操作的and和or是类似的运算，都是强制把log个子树里某些位统一，只是改成0或者1的问题。分开考虑每一位。在线段树节点里，维护每个bit位在子树里是否完全相同。那么修改的时候，如果当前操作修改的那些位在子树里本来都一样，改完后必然也一样，我们可以立即停下来，打个标记并快速维护最小值信息；否则暴力递归下去即可。时间复杂度挺显然的，势能分析一下即可。这样应该是$O(30N\logN)$的。然后可以用bitset的思想，进行一些位运算的骚操作，复杂度降低成$O(N\logN)$。

[C by lzw] F[i][j][k]表示考虑前i个东西，且第i个距离它所在的block尾部还有j个位置（每次可以花B的代价新建一个block），k表示之前的block里面一共还有多少个空位（可能是负数，表示空位欠缺）的最优解。

每次转移考虑第i+1个东西是新建一个block，还是移动到某个block的空位里，还是留在当前的block里，还是移出当前的block来增加一个空位。[[br]]

[F by lzw] 考虑一个连通分量的答案。ai是奇数的边取值显然是任意的，因为可以来回走，每次+2，mod一个奇数ai后bi可以取到任意值，所以可以将奇数边连接的点合并缩点，最后答案乘以所有的奇数ai。然后考虑只有偶数边的一个图。每条边的bi显然也可以不断+2,所以分为两个等价类，bi是偶数一个，bi是奇数一个。所以将答案乘以所有的bi/2, 问题转化为，每条边经过之后就会取反，有多少种情况。 这个问题的答案是(C(N, 2)+1) * POW(2, M - N + 1) N,M是联通点数和边数. M - N + 1表示除掉生成树外，有这么多条多余的边，这些边各自对应DFS树上一个简单环，每个环可以取或者不取，这些环可以组合出图上任意一个简单环。前面(C(N, 2)+1)表示任意先走出一条路的方案数（+1表示一条边不走）。

[E by jsb]

　　我们设$f_L$表示$LCP \leq L$ 时的概率，要求不存在相同的长度为$L+1$的前缀。[[br]]

　　得$f_L=\frac{C_{2^{L+1}}n*n!}{2^{(L+1)*n}}$。[[br]]

　　^{最后答案即为：$\sum_{i=0}}{\infty} i*(f_{i+1}-f_i)$。[[br]]

　　^这个级数不能直接求和。因为要保留最后的分数，加到无穷显然是不现实的，只能改变求和顺序。注意到分子里实际上是一个下降幂，根据第一类斯特林数（有符号）的定义，有[[br]]

　　$x^{{\lfloor n \rfloor}=\sum_{k=0}}n S1_{n,k}*x^k$。[[br]]

　　直接套用，并改变求和顺序，即可将无穷级数化为类等比数列。此题$N=10000$，可以直接暴力分治把$S1_{n,i}$求出来。数据再大一点可以分治FFT。[[br]]