「题解」 P7813 有趣的数

Table of contents

• 题目
• 分析
• 优化
• 代码

题目

Link

分析

不难发现第 $n$ 行有 $n$ 个数, 第 $n - 1$ 行有 $n - 1$ 个数, 这两行共有 $2n - 1$ 个数.

我们看数据范围: $$1 \le \dfrac {k + 1}{2} \le N \le 10^9$$

也就是说 $$\begin{aligned} k + 1 &\le 2N \\ k &\le 2N - 1 \end{aligned}$$

也就是说, 最多只会取相当于最后两行数量的数. 因为越向下、越向右的数字越大, 且可以从最右方开始遍历最后两行, 我们只需要考虑最后两行就行了.

考虑贪心, 从第 $n$ 行第 $n$ 个数, 也就是第 $n$ 行最大的数开始, 随后选择第 $n - 1$ 行有 $n - 1$ 个数, 也就是第 $n - 1$ 行最大的数, 然后再回到第 $n$ 行, 选择第 $n - 1$ 个数.

也就是说, 我们要在第 $n$ 行和第 $n - 1$ 行反复横跳, 每次都选择这行最大的数, 这样就能使和最大化.

优化

我们以样例一举例, 我们选择了 $13 \rightarrow 9 \rightarrow 14 \rightarrow 10 \rightarrow 15$ 这条路径. 我们可以将其视作在第 $5$ 行选了三个最大的, 在第 $4$ 行选了两个最大的, 完成了选择 $5$ 个数字的目标.

我们推广一下, 任何这种问题都可以视作在第 $N$ 行选 $x$ 个最大的, 在第 $N - 1$ 行选 $y$ 个最大的.

当选择个数为偶数时, 显然 $$x = y = \dfrac {k} {2}$$

当选择个数为奇数时, 因为第 $N$ 行的数字总比第 $N - 1$ 行的数字大, 所以

$$\begin{aligned} x &= \left\lceil \dfrac {k} {2} \right\rceil \\ y &= \left\lfloor \dfrac {k} {2} \right\rfloor \end{aligned}$$

第 $n$ 行第 $n$ 个数的值为: $$\begin{aligned} &\sum_{i = 1}^{n}{i} \\ = &\dfrac{n \left( {n + 1} \right) } {2} \end{aligned}$$

显然第 $n$ 行第 $n - k \left( 0 \le K < n \right)$ 个数的值为:

$$\dfrac{n \left( {n + 1} \right) } {2} - k$$

第 $n$ 行取 $x$ 个最大的数, 它们的和为:

$$\begin{aligned} &x \cdot \dfrac {n \left( {n + 1} \right) } {2} - \left( 0 + 1 + \dots + x - 1 \right) \\ = &x \cdot \dfrac {n \left( {n + 1} \right) } {2} - \dfrac {x \left( x - 1 \right)} {2} \end{aligned}$$

我们只需要分别将第 $n$ 行与第 $n - 1$ 行的情况代入求和就行了.

这里注意 $n ^ 2$ 最大能达到 $10 ^ {18}$, 因此需要使用 long long 存储, 并且运算过程中还要取模. 这也是最后一步没有完全乘开的原因, $a \cdot n ^ 2$ 会爆 long long.

代码

#include <iostream>

using std::cin;
using std::cout;

const long long MOD = 1e9 + 7;
long long T, N, K;

long long getNum(long long n, long long x)
{
    return (x * ((n * (n + 1)) / 2 % MOD) - x * (x - 1) / 2 % MOD);
}

int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    cout.tie(NULL);
    std::ios::sync_with_stdio(false);

    cin >> T;
    while (T--)
    {
        cin >> N >> K;
        cout << getNum(N - 1, K / 2) + getNum(N, (K - (K / 2))) % MOD << '\n';
    }
    return 0;
}