G. Hits Different - 题解
比赛与标签
比赛: Codeforces Round 871 (Div. 4) 标签: data structures, dp, implementation, math 难度: *1600
喵呜~ 题目到底在说什么呀？
主人你好呀！这道题是一个非常可爱的打罐子游戏呐~ 想象一下，有一个超级大的金字塔，由好多好多的罐子堆成。
- 金字塔的样子：第一行有1个罐子，第二行有2个，第三行有3个……以此类推。罐子们从上到下，从左到右被依次编号为 1, 2, 3, 4, 5, 6, ...
- 打罐子的规则：我们用球击中一个编号为
n的罐子。这个罐子会掉下来，并且，所有在它“正上方”支撑着它的罐子也会跟着掉下来，形成一个连锁反应，就像图里画的那样，会掉下来一个倒三角形区域的罐子。 - 我们的任务：计算所有掉下来的罐子的编号的平方和。比如说，如果打中了9号罐子，掉下来的是1, 2, 3, 5, 6, 9号罐子，那我们就要计算
1*1 + 2*2 + 3*3 + 5*5 + 6*6 + 9*9的值。
输入会给我们很多个 n，我们对每个 n 都要快速给出答案。要注意，答案可能会很大，需要用 long long 来存哦！
本喵的解题思路！
一看到这种“多组查询”而且“查询之间互不影响”的题目，本喵的直觉就告诉我——预处理大法好！喵~ 我们可以先把所有可能的答案都算出来，存起来。之后每次查询，直接拿出答案就好啦，这样就能跑得飞快！
那么问题来了，怎么预处理呢？这就要用到我们聪明的动态规划 (DP) 思想啦！
1. 状态定义
我们把金字塔看成一个二维坐标系，dp[r][c] 表示击中第 r 行第 c 列的罐子时，所有掉落罐子的编号平方和。
2. 状态转移方程
当一个罐子 (r, c) 被击中时，总分由两部分组成：
- 它自己的分：
Num(r, c) * Num(r, c)，其中Num(r, c)是这个位置罐子的编号。 - 它上面所有掉落罐子的总分。
它上面的罐子是怎么掉的呢？其实是 (r-1, c-1) 和 (r-1, c) 这两个罐子所引发的连锁反应。所以，上面掉落罐子的总分，就是 dp[r-1][c-1] 和 dp[r-1][c] 的总和吗？
不完全是哦！dp[r-1][c-1] 和 dp[r-1][c] 它们自己引发的连锁反应中，有一个重叠的部分，就是以 (r-2, c-1) 为顶点的那个更小的金字塔。根据容斥原理，这部分被加了两次，所以我们要减掉一次！
于是，我们得到了超级酷炫的状态转移方程： dp[r][c] = Num(r, c)^2 + dp[r-1][c-1] + dp[r-1][c] - dp[r-2][c-1]
3. 怎么计算罐子编号？
第 r 行第 c 列的罐子编号 Num(r, c) 也很好算。前 r-1 行总共有 1 + 2 + ... + (r-1) = (r-1)*r/2 个罐子。所以，Num(r, c) = (r-1)*r/2 + c。
4. 空间优化
主人请看，计算第 r 行的状态，我们只需要第 r-1 行和第 r-2 行的信息。所以我们不需要一个完整的二维 dp 数组，可以用滚动数组来优化空间！我们只需要三个一维数组，分别代表 r-2 行 (F0)，r-1 行 (F1) 和当前计算的 r 行 (F2) 就够啦。
总结一下预处理步骤：
- 创建一个大大的
res数组，res[i]用来存击中i号罐子的答案。 - 创建三个滚动数组
F0,F1,F2。 - 从第一行开始，一行一行地计算金字塔。
- 对于每一行的每一个罐子
(i, j)：- 计算它的编号
base_num。 - 用我们的DP方程计算出
dp[i][j]的值，存到F2[j]。 - 把结果存起来：
res[base_num] = F2[j]。
- 计算它的编号
- 一行计算完后，更新滚动数组：
F0 = F1,F1 = F2，然后继续计算下一行。 - 全部算完后，
res数组里就装着所有我们想要的答案啦！
本喵的代码实现喵~
#include <iostream>
#include <vector>
using namespace std;
// 金字塔的最大行数，题目说是2023，我们就设这么大~
const int R_max = 2023;
// 计算出最大行数下，罐子的最大编号是多少
const long long max_base = (long long)R_max * (R_max + 1) / 2;
int main() {
// 预处理的结果都放在这里喵~ res[i] 就是打中罐子 i 时得到的总分！
vector<long long> res(max_base + 10, 0);
// 这是我们的滚动数组，用来优化空间的说。
// F2 是当前行(i)，F1 是上一行(i-1)，F0 是上上行(i-2)~
vector<long long> F0(R_max + 10, 0);
vector<long long> F1(R_max + 10, 0);
vector<long long> F2(R_max + 10, 0);
// 开始预处理，一行一行地构建我们的答案
for (int i = 1; i <= R_max; ++i) { // i 是当前行号
for (int j = 1; j <= i; ++j) { // j 是当前列号
// 计算当前罐子 (i, j) 的编号，就是前 i-1 行的罐子总数 + j 嘛
long long base_num = (long long)i * (i - 1) / 2 + j;
// DP 的第一步，先把当前罐子自己的分值平方加上~
F2[j] = base_num * base_num;
// 如果不是第一行，就需要加上面罐子的影响
if (i >= 2) {
// 加上左上方 (i-1, j-1) 罐子引发的连锁反应总分
if (j - 1 >= 1) {
F2[j] += F1[j - 1];
}
// 加上右上方 (i-1, j) 罐子引发的连锁反应总分
if (j <= i - 1) {
F2[j] += F1[j];
}
// 如果不是前两行，就需要处理重叠部分
if (i >= 3) {
// 根据容斥原理，减去重叠的部分，也就是更上面 (i-2, j-1) 罐子引发的总分
if (j - 1 >= 1 && j - 1 <= i - 2) {
F2[j] -= F0[j - 1];
}
}
}
// 把算好的结果存到我们的最终答案数组里
if (base_num <= max_base) {
res[base_num] = F2[j];
}
}
// 更新滚动数组，为下一行的计算做准备！
F0 = F1;
F1 = F2;
}
// 处理 t 组查询
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
// 直接从预处理好的数组里 O(1) 取出答案，超快的说！
cout << res[n] << '\n';
}
return 0;
}复杂度分析时间！
- 时间复杂度: O(R_max^2) 的说。 我们的主要开销在预处理部分。我们需要遍历金字塔里的大部分罐子来计算答案。金字塔的总罐子数大约是
1 + 2 + ... + R_max，也就是R_max * (R_max + 1) / 2，所以总的计算量是O(R_max^2)。之后的每次查询都是O(1)，可以忽略不计啦。 - 空间复杂度: O(R_max^2) 的说。 空间开销主要来自
res数组，它的大小取决于金字塔里罐子的总数，也就是O(R_max^2)。我们用来做DP的滚动数组F0, F1, F2的大小都只是O(R_max)，相比之下就小多啦。
知识点与总结喵~
这道题真是太棒了，让本喵学到了好多东西！
核心思想：预处理 + 动态规划 (DP) 对于这种多组查询且输入范围固定的题目，预处理是yyds（永远的神）！一次计算，终身受益，喵~
DP 设计：容斥原理 这道题的 DP 状态转移设计非常巧妙，利用了容斥原理来处理重叠子问题。这是 DP 问题中一个很常见的技巧哦，主人一定要记住！
空间优化：滚动数组 用滚动数组把依赖前几行的DP问题的空间复杂度大大降低，虽然这题的空间瓶颈在结果数组上，但这个技巧在其他题目里可能会起到决定性作用，一定要掌握喵！
注意事项：数据类型 最后再叮嘱一下，记得开
long long呐！数字的平方和会变得非常非常大，一不小心就会溢出，让本喵的努力白费啦！
好啦，这次的题解就到这里啦！希望对主人有帮助喵~ 下次也要一起加油解题哦！(ฅ'ω'ฅ)