日记

窝补药军训啊啊啊啊啊啊啊啊啊

Flip Row or Col 2# Link to

总之就是非常神奇。

总共分 $3$ 步：

• 先把第 $1$ 行全变成 $0$。
• 对于第 $2 \sim n$ 行，如果这行超过了 $\frac{n}{2}$，又有 $r_i \le \frac{n}{4}$，所以我们必须要把第 $i$ 行取反。
• 对于第 $1 \sim n$ 列同理。

最后判断一下是否行的和和列的和符合题意就是了。

Gellyfish and Eternal Violet# Link to

先把 $a_i$ 全部 $-1$。

我们发现，对于一个群攻，在 $\min > 0$ 的时候是会执行的。对于一个单攻，一定是对 $\max$ 操作的。于是我们有 $O(nmh^2)$ dp：设 $dp_{i,j,k}$ 表示还剩 $i$ 次操作，当前的 $\min = k$，$\sum_{i = 1}^n a_i - k = j$。转移如下：

• 对于一个单攻，给最大的执行。$dp_{i,j,k} \leftarrow dp_{i - 1,j - 1,k} \times (1 - p)$。特别的，对于 $j = 0$，有 $dp_{i,0,k} \leftarrow dp_{i - 1,n - 1,k - 1} \times (1 - p)$，表示最小值变成了 $k - 1$，当然也可以选择不操作。
• 对于一个群攻，在 $k > 0$ 时一定执行，$dp_{i,j,k} \leftarrow dp_{i - 1,j,k - 1} \times p$，反之不执行，$dp_{i,j,k} \leftarrow dp_{i - 1,j,k} \times p$。

但是我们发现 $O(nmh^2)$ 显然跑不过，于是我们需要优化。

我们发现，在 $j > n$ 时候，一定会操作单攻。于是我们设 $dp1_{i,j}$ 表示在前 $i$ 次攻击里有 $j$ 次单攻的概率。转移是平凡的。

最后把两种 dp 合并起来就是了。

后日谈 # Link to 后日谈

我似乎是一事无成的。

那又如何？