hdu2466-Shell Pyramid

先预处理一下层和行所对应的数,然后二分三个答案,注意细节

 
#include<cstdio>

#define inf 0x3f3f3f3f

const int maxn=;

typedef __int64 LL;

using namespace std;

int i;

LL n,s,ans1,ans2,ans3;

LL sum[maxn+];

LL a[maxn+];

void solve(){
int flag=;
LL lb=,ub=maxn,mid=(lb+ub)>>;
while(ub-lb>){
mid=(lb+ub)>>;
if(s>a[mid]) lb=mid;
else if(s<a[mid]) ub=mid;
else if(s==a[mid]) {
flag=;
break;
}
}
if(s<=a[mid]&&s>=a[mid-]&&flag) ans1=mid;
else if(s<=a[lb]&&s>=a[lb-]) ans1=lb;
else if(s<=a[ub]&&s>=a[ub-]) ans1=ub;
s-=(a[ans1-]);
//printf("%I64d\n",s);
//printf("%I64d\n",ans1);
flag=;
lb=,ub=ans1,mid=(lb+mid)>>;
while(ub-lb>){
mid=(lb+ub)>>;
// printf("%d %d\n",mid,sum[3]);
if(s>sum[mid])
lb=mid;
else if(s<sum[mid])
ub=mid;
else if(s==sum[mid]){
flag=;
break;
}
}
//printf("%I64d %I64d %I64d %I64d\n",sum[lb],sum[lb-1],s,lb);
if(s<=sum[mid]&&s>=sum[mid-]&&flag){
// printf("1 %I64d %I64d %I64d %I64d\n",sum[mid],sum[mid-1],s,mid);
ans2=mid;
}
else if(s<=sum[lb]&&s>=sum[lb-]){
// printf("2 %I64d %I64d %I64d %I64d\n",sum[lb],sum[lb-1],s,lb);
ans2=lb;
}
else if(s<=sum[ub]&&s>=sum[ub-]){
//printf("3 %I64d %I64d %I64d %I64d\n",sum[ub],sum[ub-1],s,ub);
ans2=ub;
}
flag=;
lb=,ub=ans2,mid=(lb+ub)>>;
//printf("%d\n",ans2);
while(ub-lb>){
mid=(lb+ub)>>;
if(s>sum[ans2-]+mid) lb=mid;
else if(s<sum[ans2-]+mid) ub=mid;
else if(s==mid+sum[ans2-]) {
flag=;
break;
}
}
if(s==mid+sum[ans2-]&&flag) ans3=mid;
else if(s==lb+sum[ans2-]) ans3=lb;
else if(s==ub+sum[ans2-]) ans3=ub;
printf("%I64d %I64d %I64d\n",ans1,ans2,ans3);
} int main()
{
for(int i=;i<=maxn;i++)
sum[i]=sum[i-]+i;
for(int i=;i<=maxn;i++)
a[i]=sum[i]+a[i-];
scanf("%I64d",&n);
while(n--){
scanf("%I64d",&s);
solve();
}
return ;
}
上一篇:XJOI练习2神奇的供水系统


下一篇:『创意欣赏』20款精致的 iOS7 APP 图标设计