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\)

继续阅读

Description:


一个矩形方块,有\(n\)行\(m\)列个格子,水平和垂直方向上都可以将它视为首尾相连的(也即从最右边向右移会回到最左边,从最下边向下移会回来最上边,以此类推)。每个格子上有一个数。每一次移动会往相邻的右边、右上、右下的三个格子中选最大数的格子移动(保证存在唯一最大值)。初始位置在左上角 (1, 1)。\(q\)次操作,操作分为两种:

  1. move k移动\(k\)步,输出新位置;
  2. change x y z 修改\((x,y)\)格子中的数为\(z\)。

\(3\leq n, m \leq 2000 , 1 \leq q \leq 5000\)

继续阅读

Description:


在一个网格平面上,有\(n\)个点(牛),其中第\(i\)个点在以\((x_i,y_i)\)为右上角的网格中。有\(m\)次操作,每次给出一个点\((x,y)\)(栅栏),表示从\((x,y)\)开始,向左和向下画线直到与之前画的线或坐标轴相交。这样会划分出以\((x,y)\)为右上角的新区域。你需要对每次操作求出,新区域中点的数量。

\(n,m\leq 3 \times 10^5, 1 \leq x_i,y_i \leq 10^9\)

继续阅读