讨论 / 我的解法。。
bingshen 2011-09-16 02:29:00
点我顶贴 收藏 删除
先开始没想那么多,以为暴力就可以了,但是算了下数据量,好像不可靠。于是换了个方法

我的思路是这样的:

可以枚举数列的长度,因为长度最多是sqrt(2*m)这里解一下那个上限的方程就可以轻松算出,最多只需要计算2000次左右。

第二步:在枚举了长度l之后。可以枚举起点。因为公差为1,所以知道起点和长度就知道终点的位置。于是可以枚举起点,这里单纯枚举自然很麻烦而且复杂度很高,于是可以用二分枚举。

我的代码:

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

struct node

{

int start;

int end;

};

node ans[5000];

int m;

int cal(int s,int x)

{

return (2*s+x-1)*x;

}

int binary_search(int x)

{

int left,right,mid,tmp;

left=1,right=m/2+1;

while(left<=right)

{

mid=(left+right)>>1;

tmp=cal(mid,x);

if(tmp==2*m)

return mid;

else if(tmp<2*m)

left=mid+1;

else

right=mid-1;

}

return -1;

}

bool cmp(node a,node b)

{

return a.start<b.start;

}

int main()

{

int i,tmp,num;

while(scanf("%d",&m)!=EOF)

{

num=0;

for(i=2;i*i<=2*m+10;i++)

{

tmp=binary_search(i);

if(tmp!=-1)

{

ans[num].start=tmp;

ans[num].end=tmp+i-1;

num++;

}

}

sort(ans,ans+num,cmp);

for(i=0;i<num;i++)

printf("%d %d\n",ans[i].start,ans[i].end);

}

return 0;

}

查看更多回复
提交回复