AC. 梦想

frank_c1

Codeforces Round #362 (Div. 1)

发布于2016年07月16日 | 暂无评论 | 960阅读 | 比赛经历,生涯框架

第一次打Div. 1,有点好奇也有点期待。最后结果还不错,至少都没有FST。

A. Lorenzo Von Matterhorn

有若干个点,点i和点2i, 2i + 1有边相连,要求支持两种操作:

1. 将所有点u,v最短路径上的边的权值增加w

2. 询问点u,v的最短路径。

1 \le q \le 1000, 1 \le u,v \le 10 ^ {18}, 1 \le w \le 10 ^ 9

首先可以发现这是一棵树。于是我们用map维护边权,set求LCA即可。

时间复杂度O(q \log ^ 2 n)

B. Puzzles

考虑一棵树的DFS过程,我们记录s_u为第一次访问点u的时间。现在DFS选取儿子时我们等概率随机选取。求对于所有i \in [1,n]s_u的期望。误差不得超过10 ^ {-6}

1 \le n \le 10 ^ 5

这题一开始想的很复杂,要作许多数学推导。

后来发现有许多人过了,于是开始弃疗找规律,乱猜了个结论就A了?不知所措……

于是DFS一遍即可。时间复杂度O(n)

C. PLEASE

有三个杯子,一开始中间的杯子里有个小球。

每一轮将中间的杯子随机和其他两个杯子中的一个交换位置。

n轮后小球在中间杯子中的期望。设答案为p/q,要求pq互质,输出p,q10 ^ 9 + 7取模的值。nk个整数a_i乘积的形式给出。

1 \le k \le 10 ^ 5, 1 \le a_i \le 10 ^ {18}

考虑DP,设f(i)i轮球在中间杯子的概率,g(i)为第i轮球分别在两边杯子的概率,则有

f(i) = g(i-1), g(i) = \frac{1} {2} (f(i-1) + g(i-1))

初始条件f(0) = 1, g(0) = 0。我们发现分母部分是2 ^ n,分子部分通过OEIS可以得知是一个数列,且通项是(2 ^ n - (-1) ^ n)/3。于是费马小定理降幂后快速幂即可。

时间复杂度O(k \log w)

每道题都没有1A。于是排名就很惨了,257。幸亏没有掉rating…… 争取下次前两题能1A吧。