2024-11-27总结

花园

比赛时想到如果只覆盖一个，可以 \(O(nmk)\) 地计算出每个位置的答案。

然后发现覆盖的情况最多只有 \(2^k\) 种，那么直接把前 \(2^k\) 大拿出来做就好了，\(O(nmk4^k)\)。

upd：其实只会有 \(k^2\) 个有覆盖的位置，所以只考虑这些位置就好了 \(O(nmk^3)\)。

过河卒

策略可以，没有丢分（其实丢了2分，直接变成3进制来做就好了，甚者可以做到70多，用6进制）

就是建一个：

|-|
|-|-|
  |-|-|
    |-|

这种，就是二进制分解。

正解就是看到：

L 在范围内均匀随机生成。

所以考虑随机化，直接随机一个矩阵，然后调整，每次把一个 \(1\) 变成 \(0\) 就好了。

被卡常了qwq：

1. 把f[m][m] - f[i][j] * g[i][j] 拆开计算，尽量不计算减法把求它的min改成求后面的max：7000ms->3000ms
2. 求f和g数组时用v[i][j] * ???的写法：3000ms->700ms
3. 输出优化：好像没有效果
4. 使用unsigned long long 700ms -> 200ms

这是一场豪赌

容易有 \(O(n^4)\) dp，然后发现每次重新计算一次当 \(i,j\) 为中位数的方案是不优的，因为大部分情况下只会改一部分。

这是个背包，每个组有 \(2\) 个元素，那么我们直接处理到某个数时把错误的除以，再乘上正确的就好了。

多项式除法：模拟除法的过程，因为最低位只会由最低位贡献来，所以直接除逆元即可。

航行

失败，考虑列出转移式子之后直接高斯消元，看似 \(O(n^6)\)，实际上发现当速度达到 \(2\sqrt n\) 时一定会出界，所以为 \(O(n^{4.5})\)。

然后发现我们可以直接减少状态：只储存 \(v=0\) 的答案，用 dp 算出 \((i,0)\) 到 \((j,0)\) 的期望和概率，假设 \(i<j\)，发现 \(i\) 一定一直往右走，因为如果出现 \(v<0\)，由于 \(v\) 连续，一定到不了 \((j,0)\)。

这是真的可以做的，设 \(g_{i,j}\) 表示概率，\(f_{i,j}\) 表示期望：

(f[j + k - 1][k - 1] += (f[j][k] + g[j][k]) * p[j] % P) %= P;
(g[j + k - 1][k - 1] += g[j][k] * p[j] % P) %= P;

矩阵就是设 \(x_i\) 表示 \(i\) 出界的期望，那么可以由能到达 \(i\) 的点 \(j\) 贡献来，\(x_i=g_{j\to i} x_j-f_{j\to i}+g_{i\to 0}\)。

直接高斯消元即可，还顺便考前复习了高消板子。