Codeforces Round #362 (Div. 1)

A – Lorenzo Von Matterhorn

给出n个点的树(n <=1e18),i只会和2 * i、2 * i + 1右边,接下来两种操作:1.某条路径的边权全部加w;2.计算某条路径的边权和。
根据边的定义容易发现每个点的深度是Log级别的,所以路径的长度也是log级别的,所以用map距离边的全职,然后暴力找LCA即可。

B – Puzzles

给出一个dfs遍历的方案,一开始时间是0,没到一个点时间就+1,对于当前点u到某个孩子的概率是相等的。求每个点被走到时间的期望。
分两种情况:1.v孩子是第一个被访问的,那么直接从父亲转移,dp[v] += (dp[u] + 1) * 0.5;2.v至少在第二个才被访问,那么先在他之前访问的全排列概率是0.5,dp[v] += dp[u] * 0.5 + (sz[u] – sz[v]) * 0.5

C – PLEASE

开始有三个杯子,钥匙在中间的杯子里,每轮将中间的杯子随机的和两边的杯子交换。求n轮后中间杯子有钥匙的概率。
不妨dp[i][0/1/2]表示钥匙在左边、中间、右边的概率。随便腿一下方程,最后发现可以合并dp[i]表示中间有钥匙的概率,于是dp[i] = (1 – dp[i]) * 0.5。因为n很大无法递推,但是迭代下会发现是一个关于2的幂次的分数,快速幂即可。

D – Legen…

给出n个字符串,每个字符串有一个权值,构造一个长度是l的字符串是的包含的权值最大。显然可以dp,dp[i][j]表示构造了i长度的字符串,现在自动机的j点上,l非常大显然不能递推,那么我们可以构造矩阵乘法来搞,是的用矩阵乘法去搞最大值问题,这个的正确性先不说,我们来看另外一种解法:dp[i][j][k]表示在自动机上i点经过2^j步走到自动机k的构成的最大权值,这个状态显然是对,转移时就去枚举左右区间合并,那么我们回归矩阵乘法的方案,显然矩阵乘法也是拆分二进制分治的过程,和这个是有异曲同工之妙的!

E – …Wait for it…

给出一棵树,两种操作:1.输出u-v路径之前没输出过的前k大数字;2.将v子树全部加k;
开始很懵逼,如何处理链条和子树的更新,但是有一个有趣的地方,如果按照树链剖分求重链的顺序去搞出dfs序,那么更新某个子树时一定会把树链都遍历到。于是就可以无脑更新了。

 

A:

 

B:

 

C:

 

D:

 

E:

 

LEAVE A COMMENT