hdu 2446 Shell Pyramid

前端之家收集整理的这篇文章主要介绍了hdu 2446 Shell Pyramid前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。


点击打开链接



题意:

题意很迷,看了很久才看懂。

他要堆炮弹,怎么堆呢,

递增的三角形的堆,例如

1 2 5 11 .。。。

3 4 6 7

8 9 10

然后给你一个炮弹编号, 问你在第几个三角形中,并且在该三角形的几行几列。


题解:

两种做法,

第一种二分,最省事。

打表求出前n堆的和and前n行的和。 二百多万的数组就差不多了。

二分堆,在二分行。

第二种推公式。

卧槽,,,推了俩小时!!!!。

前n行的公式很好求, n(n+1)/2;

前n堆麻烦点,

首先 1 2 3 4 5 6

1 4 10 20 35 56

1*1+0 2*2+0 3*3+1 4*4+3 5*5+10 6*6+20


于是发现 前n堆的和为 1-n 所有 和n同奇同偶的数的平方和 例 n=5; Sn=1*1+3*3+5*5;

这样还是不好总结公式。因为不连续,

那么把它变成连续的直接就有1^2+2^2+3^2+……+n^2=n(n+1)(2n+1)/6 。

那么可得 n*n->(n+1)*(n+1) 可得 吧 =Sn-1->Sn

Sn=(1*1+2*2+.....+n*n+1+2+......+n)/2;

Sn-1=(n*n*n-n)/6;

这样可以求出在第几个三角形,再求出在第几行,第几个即可。


#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int t;
    ll x,y,z,n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        ll x=(ll)pow(n*6.0,1.0/3.0)+1;
        while(x*x*x-x>=n*6) x--;
        n-=(x*x*x-x)/6;
        y=(ll)sqrt(2.0*n)+1;
        while(y*(y+1)>=n*2) y--;
        z=n-y*(y+1)/2;
        printf("%lld %lld %lld\n",x,y+1,z);
    }
    return 0;
}
原文链接:https://www.f2er.com/bash/392276.html

猜你在找的Bash相关文章