Description:


给你一个排列\(p_1,p_2,\dots,p_n\),第\(i\)个元素的权重为\(a_i\)。

你首先要把排列切成两个非空子集,前缀和后缀。

然后移动其中的元素,你可以将前缀中的元素移到后缀中,也可以反过来,移动\(p_i\)需要付出\(a_i\)的代价。

问最少付出多少代价,可以使得前缀中的元素均小于后缀中的元素,或其中一个为空。

\(n\leq 200\ 000, a_i \leq 10^9\)

继续阅读

Description:


无限长的一维坐标轴上有\(n\)个球,每个球的坐标为\(x_i\),速度为\(v_i\),并以\(p_i\)的概率向右运动,\(1-p_i\)的概率向左运动,求第一次碰撞产生时的期望时间。永远不产生碰撞的贡献为0。

\(1\leq n \leq 10^5\)

继续阅读

Description:


一张\(n\)个点\(m\)条边的有向图,每个点有一个博物馆,一个星期有\(d\)天,每个博物馆在一周中某几天固定开放,初始时在\(1\)号点,星期\(1\),如果当天你所在的点的博物馆开放,则可以进入参观,每天结束时,可以沿着有向边进入相邻的点。

问最多可以参观多少个不同的博物馆。

\(n,m\leq 10^5, d\leq 50\)

继续阅读