Burnling's Blog

题意简述

霓裳子突然在 $0$ 点的数字线上醒来，并拥有 $h$ 点健康值。她想到达 $d$ 点。在一个回合中，她可以做两件事中的一件：

• 在树荫下休息，并将当前健康值增加 $1$ ；
• 从当前位置 $x$ 移动到 $x + 1$ 。

每次移动都会降低霓裳子的生命值；如果是 $j$ /三次连续移动，她的生命值将减少 $j$ 点。如果移动导致霓裳子的生命值下降到 $0$ 或更低，她就无法进行移动。

例如，如果霓裳子最初的生命值为 $7$ 和 $d=4$ ，那么她的移动会如下所示：

1. 从 $0$ 移动到 $1$ ，生命值减少 $1$ 。现在她在 $1$ 点，生命值为 $6$ 。
2. 从 $1$ 移动到 $2$ ，并减少生命值 $2$ 。现在她位于 $2$ 点，生命值为 $4$ 。
3. 从 $2$ 移动到 $3$ ，减少生命值 $3$ 。现在她位于 $3$ 点，生命值为 $1$ 。
4. 休息并恢复 $1$ 点生命值。现在她位于 $3$ 点，拥有 $2$ 点生命值。
5. 从 $3$ 移动到 $4$ ，并减少 $1$ 点生命值。现在她位于 $4$ 点，生命值为 $1$ 。

求她到达点 $d$ 所需的最少回合数。

思路分析

这道题最需要想到的是，假设休息 $m$ 次，最佳策略是均匀分配这 $m$ 次的休息。

一旦想到这个，就可以二分休息次数求出最少休息数了。

下为证明。

假设一个路程长度为 $L$，休息 $m$ 次，每一次在 $k_i$ 点处休息。

为了方便化简，把终点视为最后一个休息点。

那么花费的总生命即为 $\dfrac{k1(k_1-1)}{2} + \sum\limits{i=2}^{m} \dfrac{(ki-k{i-1})(ki-k{i-1}-1)}{2}$

记 $d1=k_1,\ d_i=k_i-k{i-1}\ (i=2,\dots,m)$.

那么总代价就可以化为 $\text{cost}=\dfrac{1}{2}\sum\limits_{i=1}^{m}(d_i(d_i-1))$

展开得 $\text{cost}=\dfrac{1}{2}\sum\limits_{i=1}^m d_i^2-\dfrac{L}{2}$.

因此 $L$ 固定的前提下，最小化 $\text{cost}$ 等价于最小化 $d_i$ 的平方和。

记 $\bar d = \dfrac{L}{m}$.

第一项为平方项，恒非负。第二项恒为 $0$。

则在固定和的约束下，平方和达到最小的条件即为所有 $d_i$ 满足 $d_i=\bar d$。

所以均分所消耗的代价是最小的。

题意简述

爱丽丝有一个大小为 $n \times n$ 的网格。最初，所有单元格都被涂成白色。爱丽丝希望将一些单元格染成黑色，以满足某些属性的要求。

假设 $(x_1, y_1), (x_2, y_2), \ldots, (x_m, y_m)$ 是被涂成黑色的单元格。给你一个大小为 $n$ 的数组 $a$ 。必须满足以下条件：

• 对于每一行 $k$ ( $1 \le k \le n$ )，恰好存在 $a_k$ 索引 $i$ ( $1 \le i \le m$ )，使得 $x_i = k$ .简而言之， $k$ 行中应该有 $a_k$ 个黑格。
• 对于每一个 $k$ （ $1 \le k \le n$ ），恰好存在一个索引 $i$ ，即 $\max(x_i, y_i) = k$ 。
• 对于每个 $k$ ( $1 \le k \le n$ )，恰好存在一个索引 $i$ ，即 $\max(x_i, n + 1 - y_i) = k$ 。

计算可能的网格数。如果其中一个网格中的某个单元格为黑色，而另一个网格中的某个单元格为白色，则 $2$ 个网格被认为是不同的。由于答案可能很大，因此请输出 $998\,244\,353$ 的模数。

思路分析

最重要的就是要把第二和第三个条件分析出来。

这两个条件都对应一组 L 形图案，同一个 L 形区域里面只能有一个黑色格子。

条件 2 对应左上缺口的宽度为 1 的 L，条件 3 对应右上缺口的宽度为 1 的 L。

这两个条件结合起来就是一个倒三角图形，它的每一列只能有一个黑色格子。

大概这样。

所以只需要从最下面一行开始，假设第 $i$ 行有 $c$ 个位置可以填，那么就有 $C_c^{a_i}$ 种方案。

下一行就会有 $c-a_i+2$ 个位置可以填。

总结

感觉真没什么难的。为啥就被硬控了呢，，，