首页 > 代码库 > 【二分】 HDU 2446 Shell Pyramid
【二分】 HDU 2446 Shell Pyramid
题意:很多球组成一个金字塔
第x层有 x*(x+1)/ 2 个球
给你一个S 表示金字塔一层一层数下来的第S个球
它在哪一层 这层中的第几行 第几列
公式 1 : x*(x+1)*(x+2)/ 6
公式 2 :x*(x+1)/ 2
公式1为公式2 的前n项和
#include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <cmath> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <time.h>; #define cler(arr, val) memset(arr, val, sizeof(arr)) #define FOR(i,a,b) for(int i=a;i<=b;i++) #define IN freopen ("in.txt" , "r" , stdin); #define OUT freopen ("out.txt" , "w" , stdout); typedef long long LL; const int MAXN = 10323; const int MAXM = 201; const int INF = 0x3f3f3f3f; const int mod = 1000000007; LL getnum1(LL num) { LL x=num; LL y=num+1; LL z=num+2; if(x%2==0) x/=2; else if(y%2==0) y/=2; else if(z%2==0) z/=2; if(x%3==0) x/=3; else if(y%3==0) y/=3; else if(z%3==0) z/=3; return x*y*z; } LL getnum2(LL num) { return num*(num+1)/2; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int t; LL n; scanf("%d",&t); while(t--) { cin>>n; LL l=0,r=3810776;//r表示极限了。。 while(l<=r)//求第几层 { LL mid=(l+r)>>1;//getnum1(3810776) if(getnum1(mid)>=n) r=mid-1; else l=mid+1; } LL ans1=l; n-=getnum1(l-1); l=0,r=3810776; while(l<=r)//求第几行 { LL mid=(l+r)>>1; if(getnum2(mid)>=n) r=mid-1; else l=mid+1; } n-=getnum2(l-1); LL ans2=l; printf("%I64d %I64d %I64d\n",ans1,ans2,n); } }
【二分】 HDU 2446 Shell Pyramid
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。