蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提!
Hello, 大家好哇!本初中生蒟蒻讲解一下G. Hits Different!
上绿名喽!
===========================================================================================
G. Hits Different
题目描述
In a carnival game, there is a huge pyramid of cans with 2023 rows, numbered in a regular pattern as shown.
If can 9 2 9^2 92 is hit initially, then all cans colored red in the picture above would fall.
You throw a ball at the pyramid, and it hits a single can with number n 2 n^2 n2. This causes all cans that are stacked on top of this can to fall (that is, can n 2 n^2 n2 falls, then the cans directly above n 2 n^2 n2 fall, then the cans directly above those cans, and so on). For example, the picture above shows the cans that would fall if can 9 2 9^2 92 is hit.
What is the sum of the numbers on all cans that fall? Recall that n 2 = n × n n^2=n×n n2=n×n.
Input
The first line contains an integer t ( 1 ≤ t ≤ 1000 ) t (1≤t≤1000) t(1≤t≤1000) — the number of test cases.
The only line of each test case contains a single integer n ( 1 ≤ n ≤ 1 0 6 ) n (1≤n≤10^6) n(1≤n≤106) — it means that the can you hit has label n 2 n^2 n2.
Output
For each test case, output a single integer — the sum of the numbers on all cans that fall.
Please note, that the answer for some test cases won’t fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++). For all valid inputs, the answer will always fit into 64-bit integer type.
Example
Note
The first test case is pictured in the statement. The sum of the numbers that fall is
1
2
+
2
2
+
3
2
+
5
2
+
6
2
+
9
2
=
1
+
4
+
9
+
25
+
36
+
81
=
156.
1^2+2^2+3^2+5^2+6^2+9^2=1+4+9+25+36+81=156.
12+22+32+52+62+92=1+4+9+25+36+81=156.
In the second test case, only the can labeled
1
2
1^2
12 falls, so the answer is
1
2
=
1
1^2=1
12=1.
In the third test case, the cans labeled
1
2
1^2
12 and
2
2
2^2
22 fall, so the answer is
1
2
+
2
2
=
1
+
4
=
5
1^2+2^2=1+4=5
12+22=1+4=5.
In the fourth test case, the cans labeled
1
2
1^2
12 and
3
2
3^2
32 fall, so the answer is
1
2
+
3
2
=
1
+
9
=
10
1^2+3^2=1+9=10
12+32=1+9=10.
In the fifth test case, the cans labeled
1
2
,
2
2
1^2, 2^2
12,22, and
4
2
4^2
42 fall, so the answer is
1
2
+
2
2
+
4
2
=
1
+
4
+
16
=
21.
1^2+2^2+4^2=1+4+16=21.
12+22+42=1+4+16=21.
思路
本题可以想到动态规划,我们可以这样考虑:
假设砸
1
4
2
14^2
142这个点,我们看一下怎么转移:
红色的是
1
4
2
14^2
142左边这个点
7
2
7^2
72这个点所能波及到的点
绿色的是
1
4
2
14^2
142右边的点
8
2
8^2
82所能波及到的点
然后我们看一下他们重复了那些点:
其实就是
1
4
2
14^2
142上一行的上一行的左边的点
4
2
4^2
42所能波及到的点
故此,砸 1 4 2 14^2 142的值应该是砸 7 2 7^2 72的值+砸 8 2 8^2 82的值-砸 4 2 4^2 42的值+ 1 4 2 14^2 142
可以推导出状态转移方程:(
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示砸图中第i行第j列的点的答案)
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
+
d
p
[
i
−
1
]
[
j
−
1
]
−
d
p
[
i
−
2
]
[
j
−
1
]
+
n
u
m
[
i
]
[
j
]
dp[i][j] = dp[i -1][j]+dp[i-1][j-1]-dp[i-2][j-1]+num[i][j]
dp[i][j]=dp[i−1][j]+dp[i−1][j−1]−dp[i−2][j−1]+num[i][j]
其中, n u m [ i ] [ j ] num[i][j] num[i][j]表示图中第i行第j列的数字
本题就是求
d
p
[
1
−
2023
]
[
1
−
2023
]
dp[1-2023][1-2023]
dp[1−2023][1−2023]的值
时间复杂度
O
(
n
2
)
O(n^2)
O(n2)文章来源:https://www.toymoban.com/news/detail-435971.html
题中是输入的 n n n我们找到他是第几行,第几列即可!文章来源地址https://www.toymoban.com/news/detail-435971.html
代码
#include <iostream>
#define int long long
using namespace std;
const int N = 2024;
int dt;
int n;
int dp[N][N];
int num[N][N];
int sum[N];
signed main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t = 1;
for (int i = 1; i <= 2023; i ++)
for (int j = 1; j <= i; j ++)
num[i][j] = t * t, t ++;
sum[1] = 1;
for (int i = 2; i <= 2023; i ++)
sum[i] = sum[i - 1] + i - 1;
dp[1][1] = 1;
for (int i = 2; i <= 2023; i ++)
for (int j = 1; j <= i; j ++)
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] - dp[i - 2][j - 1] + num[i][j];
cin >> dt;
while (dt --)
{
cin >> n;
int h;
for (int i = 1; i <= 2023; i ++)
if (n < sum[i])
{
h = i - 1;
break;
}
cout << dp[h][n - sum[h] + 1] << endl;
}
return 0;
}
到了这里,关于Codeforces Round 871 (Div. 4)——G题讲解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!