日记

日记

Thu May 08 2025
5 分钟
1000 字

任重而道远啊。

Tournament Link to

建议降红。

Bomb Game 2 Link to

也是终于在提示下做出来了。

我们发现正着做十分的难,考虑正难则反。我们管最后剩下的叫“原初”。设 dpi,jdp_{i,j} 表示在还剩 ii 个人的情况下原初在 jj 的概率。那么初始化就是 dp1,1=1dp_{1,1} = 1,每个点的答案就是 dpn,idp_{n,i}

考虑如何转移。我们分类讨论:

  • i1i \neq 1
    显然它会有两种情况:一种是前面的死了,从 dpi1,j1dp_{i - 1,j - 1} 转移来,一种是前面的活了,从 dpi,j1dp_{i,j - 1} 转移来。那么 dpi,j=dpi1,j1+dpi,j12dp_{i,j} = \frac{dp_{i - 1,j - 1} + dp_{i,j - 1}}{2}
  • i=1i = 1
    显然它也会有两种情况,但是其中一种是它死了,那么它就不可能成为原初,不用转移。剩下的就只有它活了这一种情况。dpi,j=dpi,j2dp_{i,j} = \frac{dp_{i,j}}{2}

然后就是喜闻乐见的手解 30003000 元方程组了。我们可以设 dpi,1=xdp_{i,1} = x,然后再把 dpi,1dp_{i,1} 表示成 ax+bax + b。解出 xx 之后就可以转移了。

Double Sum 3 Link to

致敬传奇手模王。我手模死活模不过,把代码写出来过了?

我们发现一个 aia_i 会在区间 [l,r][l,r] 之内做出贡献当且仅当 ai1a_i - 1 没在 [l,r][l,r] 内出现。于是我们对于每个 aia_i 分别计算贡献。我们设 L=ai1上次出现的位置,R=ai1下次出现的位置L = a_i - 1 \, \text{上次出现的位置},R = a_i - 1 \, \text{下次出现的位置}。那么 aia_i 就会对 l(L,i],r[i,R)l \in (L,i],r \in [i,R) 的区间造成贡献。

然后兴致勃勃的打代码测样例,发现过不了。究其原因是如果区间内有多个一样的 aia_i,只能计算一次贡献。我们只需要把 RRai下次出现的位置a_i \, \text{下次出现的位置}min\min 就行。

Laminate Link to

我们发现,如果要更改 hih_i,一定是把 hih_i 改的和 hi1h_{i - 1} 一样。这样做的效果相当于删除了一个 hih_i。要我们在删 kk 个数之后最小化 i=1nmax(0,hihi1)\sum\limits_{i = 1}^{n}\max(0,h_i - h_{i - 1})

我们设 dpi,jdp_{i,j} 表示 [1,i][1,i] 里保留了 jj 个数。那么转移就是 dpi,j=min{dpk,j1+max(0,hihk)}dp_{i,j} = \min\{dp_{k,j - 1} + \max(0,h_i - h_k)\}。复杂度 O(n3)O(n^3),可以通过。

Fuel Round Trip Link to

我们设 dpi,j,kdp_{i,j,k} 表示从 1ini1 \to i \to n \to i,第一次到 ii 时有 jj 的油,第二次到 iikk 的油。那么转移是:

{dpi1,j,kdpi,j,k这里不买dpi1,j,k+pidpi,j+fi,k第一次来时买dpi1,j,k+pidpi,j,kfi第二次来时买\begin{cases} dp_{i - 1,j,k} \to dp_{i,j,k} & \text{这里不买} \\ dp_{i - 1,j,k} + p_i \to dp_{i,j + f_i,k} & \text{第一次来时买} \\ dp_{i - 1,j,k} + p_i \to dp_{i,j,k - f_i} & \text{第二次来时买} \end{cases}

注意 j+fij + f_i 要对 hhmin\minkfik - f_i 要对 00max\max

Manhattan Cafe Link to

我们设 dpi,j,kdp_{i,j,k} 表示已经匹配了前 ii 维,离 pp 的距离已经有 jj,离 qq 的距离已经有 kk 的方案数。转移时枚举当前的位置 (r,r)(r,r)dpi,j,k=dpi1,jpir,kqirdp_{i,j,k} = \sum dp_{i - 1,j - |p_i - r|,k - |q_i - r|}。我么发现,如果把能转移到 i,ji,ji,ji',j' 画在平面直角坐标系中时,是一条 k=1k = 1 的直线 + 一条 k=1k = -1 的线段 + 一条 k=1k = 1 的线段。

就像这样:

x=piqix = |p_i - q_i|,那么两个拐点的坐标分别是 (jx,k),(j,kx)(j - x,k),(j,k - x)。用一个 sumsum 维护一个 k=1k = 1 线段上的前缀和,prepre 维护一个 k=1k = -1 线段上的前缀和即可。枚举状态 O(nd2)O(nd^2),转移 O(1)O(1),总复杂度 O(nd2)O(nd^2)

后日谈 Link to 后日谈

成功驯服 Godot,这周末开始做 BattleSweel。