P12728 [KOI 2021 Round 2] 直升机着陆场

题目概述

有 $a$ 同红漆，b 桶蓝漆，画若干个同心圆，第 $i$ 个同心圆需消耗 $i$ 桶 [红/蓝] 油漆，求有 $a$ 桶红漆 $b$ 桶蓝漆能画出多少种同心圆。

前置说明

为了方便表示，后文中

#define 红 红漆
#define 蓝 蓝漆
#define n 最多画的同心圆的数量
#define V a和b的值域

初始思路

首先考虑最多画多少个环，即解 $n(n+1) = 10^5$，易得 $n = 446.714$，可以看到非常小，很适合拿来做动态规划，考虑到有多次询问，因此考虑预处理一个 $f$ 数组。

套路化地，定义 $f[i][j][k]$ 表示画 $i$ 个同心圆，刚好使用 $j$ 桶红、 $k$ 桶蓝的方案数，则易得递推式为 :

$$f[i][j][k] = f[i-1][j-i][k] + f[i-1][j][k-i]$$

初始化：

$$f[0][0][0] = 1$$

时间复杂度 $O(nV_2)$，恭喜你顺利水到 20pts。

优化 1

注意到当 $i$ 和 $j$ 确定时 $k$ 也确定了，恭喜你，压掉了一维🎉🎉🎉
现在递推式变为：

$$f[i][j] = f[i-1][j-i]+f[i-1][j]$$

不过需要注意的是由于是刚好使用 $j$ 桶，因此统计答案时需要枚举 $j$ :

$$\sum_{i=1}^{466} \sum_{j=tot-b}^{\max(tot, a)} f[i][j]$$

其中 $tot$ 表示 $\frac{i(i+1)}{2}$ 即 $i$ 个环消耗的桶数。
就这样恭喜你水到了 90 pts！

Code

// Link:https://www.luogu.com.cn/problem/P12728
// By Oscarwang1222
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int read() {
    int aa = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        aa = aa * 10 + ch - '0';
        ch = getchar();
    }
    return aa * f;
}
void write(int aa, char ch = '\n') {
    if (aa < 0)
        putchar('-'), aa = -aa;
    else if (aa == 0) {
        putchar('0');
        putchar(ch);
        return;
    }
    unsigned short st[20], tp = 0;
    while (aa)
        st[tp++] = aa % 10, aa /= 10;
    while (tp)
        putchar(st[--tp] + '0');
    putchar(ch);
}
const int N = 5e4 + 5;
const int inf = 0x3f3f3f3f3f3f3f3fLL;
const int mod = 1e9 + 7;

int dp[500][N + 10]; // 出于个人习惯使用 dp 数组
void init() {
    dp[0][0] = 1;
    for (int i = 1; i <= 456; i++) {
        int tot = i * (i + 1) / 2;
        int range = min(tot, N);
        for (int j = 0; j <= range; j++) {
            if (j >= i)
                dp[i][j] = (dp[i][j] + dp[i - 1][j - i]) % mod;
            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
        }
    }
}
void solve() {
    int a = read(), b = read();
    int sum = a + b;
    int ans = 0;
    for (int i = 1; i <= 456; i++) {
        int tot = i * (i + 1) / 2;
        if (tot > sum)
            break;
        for (int j = max(0LL, tot - b); j <= a; j++) {
            ans = (ans + dp[i][j]) % mod;
        }
    }
    write(ans);
}
signed main() {
    init();
    int T_T = read();
    while (T_T--)
        solve();
    return 0;
}

优化 2

注意到完成优化 1 后时间复杂度的瓶颈主要卡在了每次一查询的过程中，因此考虑优化查询的时间复杂度。
注意到统计答案时对于每个 $i$ 的 $\sum_{j=tot-b}^{\max(tot, a)} f[i][j]$ 是一段连续的和，且查询时不涉及修改，因此可以使用前缀和进行优化，因此查询操作变为了只需枚举 $i$，恭喜你水到了 100 pts！

Code

// Link:https://www.luogu.com.cn/problem/P12728
// By Oscarwang1222
#include <bits/stdc++.h>
#include <random>
#define int long long
#define endl "\n"
using namespace std;
int read() {
    int aa = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        aa = aa * 10 + ch - '0';
        ch = getchar();
    }
    return aa * f;
}
void write(int aa, char ch = '\n') {
    if (aa < 0)
        putchar('-'), aa = -aa;
    else if (aa == 0) {
        putchar('0');
        putchar(ch);
        return;
    }
    unsigned short st[20], tp = 0;
    while (aa)
        st[tp++] = aa % 10, aa /= 10;
    while (tp)
        putchar(st[--tp] + '0');
    putchar(ch);
}
const int N = 5e4 + 5;
const int inf = 0x3f3f3f3f3f3f3f3fLL;
const int mod = 1e9 + 7;

int dp[500][N + 10], s[500][N + 10]; // 出于个人习惯使用 dp 数组
void init() {
    dp[0][0] = 1;
    for (int i = 1; i <= 446; i++) {
        int tot = i * (i + 1) / 2;
        int range = min(tot, N);
        for (int j = 0; j <= range; j++) {
            if (j >= i)
                dp[i][j] = (dp[i][j] + dp[i - 1][j - i]) % mod;
            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
        }
        s[i][0] = dp[i][0];
        for (int j = 1; j <= range; j++)
            s[i][j] = (s[i][j - 1] + dp[i][j]) % mod;
    }
}
void solve() {
    int a = read(), b = read();
    int sum = a + b;
    int ans = 0;
    for (int i = 1; i <= 446; i++) {
        int tot = i * (i + 1) / 2;
        int x = min(a, tot);
        if (tot > sum)
            break;
        if (tot - b <= 0)
            ans = (ans + s[i][x]) % mod;
        else
            ans = (ans + s[i][x] - s[i][tot - b - 1] + mod) % mod;
    }
    write(ans);
}
signed main() {
    init();
    int T_T = read();
    while (T_T--)
        solve();
    return 0;
}

完结🎉

写题解着实不易，如有错漏欢迎指出，会及时修改。
都看到这了还请点个赞再走吧🌹🌹🌹