Codeforces Round 871 (Div. 4)——G题讲解

这篇具有很好参考价值的文章主要介绍了Codeforces Round 871 (Div. 4)——G题讲解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蒟蒻来讲题,还望大家喜。若哪有问题,大家尽可提!

Hello, 大家好哇!本初中生蒟蒻讲解一下G. Hits Different!
Codeforces Round 871 (Div. 4)——G题讲解
上绿名喽!

===========================================================================================

G. Hits Different

题目描述

In a carnival game, there is a huge pyramid of cans with 2023 rows, numbered in a regular pattern as shown.

Codeforces Round 871 (Div. 4)——G题讲解

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(1t1000) — 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(1n106) — 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

Codeforces Round 871 (Div. 4)——G题讲解
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.

思路

本题可以想到动态规划,我们可以这样考虑:
Codeforces Round 871 (Div. 4)——G题讲解
假设砸 1 4 2 14^2 142这个点,我们看一下怎么转移:
Codeforces Round 871 (Div. 4)——G题讲解
红色的是 1 4 2 14^2 142左边这个点 7 2 7^2 72这个点所能波及到的点
Codeforces Round 871 (Div. 4)——G题讲解
绿色的是 1 4 2 14^2 142右边的点 8 2 8^2 82所能波及到的点

然后我们看一下他们重复了那些点:
Codeforces Round 871 (Div. 4)——G题讲解
其实就是 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[i1][j]+dp[i1][j1]dp[i2][j1]+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[12023][12023]的值
时间复杂度 O ( n 2 ) O(n^2) O(n2)

题中是输入的 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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 视频讲解Codeforces Round 887 (Div. 2)(A--C)

    视频讲解Codeforces Round 887 (Div. 2)(A–C)

    2024年02月16日
    浏览(48)
  • Codeforces Round 882 (Div. 2)(视频讲解A——D)

    @[TOC](Codeforces Round 882 (Div. 2)(视频讲解A——D)) 讲解在B站:Codeforces Round 882 (Div. 2)(视频讲解A——D)

    2024年02月16日
    浏览(33)
  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律,发现结果与边长n的关系是:res = n * (n + 3) - (n - 2) ①当n为奇数时,除了1其他均无解 ②当n为偶数时,我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(46)
  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足: 任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(54)
  • Codeforces Round 926 (Div. 2)

    类似于倍投法,就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制,不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111,前3把一直输,但是只要第4把赢,就一定可以增加 1

    2024年02月20日
    浏览(43)
  • Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是:前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n],重排b后,令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的,一定能满足

    2024年02月05日
    浏览(36)
  • Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ,使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) , (y) 个 (-1) 时,其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ,直接枚举 (x) 即可。

    2024年02月01日
    浏览(43)
  • Codeforces Round 881 (Div. 3)

    给定一个数组,给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差,每个元素要么对答案有正的贡献,要么有负的贡献,要么无贡献。且正负贡献的个数要相同。 因为要最大值,自然就是想有正贡献的是最

    2024年02月09日
    浏览(41)
  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序,因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1,计算能否时每个数当前位为1

    2024年02月04日
    浏览(43)
  • Codeforces Round 882 (Div. 2)

    目录 A. The Man who became a God  题目分析: B. Hamon Odyssey 题目分析: C. Vampiric Powers, anyone? 题目分析:  n个人分成k组,每一组的力量都是 这样的,那么如果分成k组那么就会有k-1个力量不被统计,将力量总和减去前k-1个最大的力量就是最小的结果   将数组分组,每个组内进行按位与

    2024年02月05日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包