首页 > 代码库 > 【USACO 1.4.3】等差数列
【USACO 1.4.3】等差数列
【题目描述】
一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。
在这个问题中a是一个非负的整数,b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方 + q的平方的数的集合)S中长度为n的等差数列。
【格式】
TIME LIMIT: 5 秒
INPUT FORMAT:
(file ariprog.in)
第一行: N(3<= N<=25),要找的等差数列的长度。
第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。
OUTPUT FORMAT:
(file ariprog.out)
如果没有找到数列,输出`NONE‘。
如果找到了,输出一行或多行, 每行由二个整数组成:a,b。
这些行应该先按b排序再按a排序。
所求的等差数列将不会多于10,000个。
【分析】
注意到时间限制是5秒,考虑用枚举。
我们能够很自然的想到把S中的数全部预处理出来,存在S数组中,然后再排一下序。
做一个两重循环来枚举数列的第一项和第二项,以两项之差找等差数列,最后查看是否有n个。
但是遗憾的是,即便是这样的方法还是会超时。
原因在哪里呢?
没错,就在于循环上,可以打表查看的是,当M上界一大了以后,S中的元素往往会有上千个。
但是在枚举的过程中,有一些枚举是完全可以舍弃掉的。
if (S[i]+(S[j]-S[i])*(n-1)>S[point-1]) continue;(这个便是最重要的剪枝)
把它加上去就能AC了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 const int maxs=250*250+10; 7 using namespace std; 8 struct Ans 9 {10 int a,d;//首项与公差 11 bool operator <(const Ans&b)const12 {13 if (b.d==d) return a<b.a;14 return d<b.d;15 } 16 }ans[10005*3];17 int S[maxs],n,m,point=0,ans_point=0;18 bool vis[maxs*2];19 int main()20 {21 int i,j,k;22 //文件操作 23 freopen("ariprog.in","r",stdin);24 freopen("ariprog.out","w",stdout);25 memset(vis,0,sizeof(vis));26 27 scanf("%d%d",&n,&m);28 for (i=0;i<=m;i++)29 for (j=0;j<=m;j++)30 if (vis[i*i+j*j]==0)31 {32 S[point++]=i*i+j*j;33 vis[i*i+j*j]=1;34 }35 sort(S,S+point);//排序 36 37 for (i=0;i<point;i++)38 for (j=i+1;j<point;j++)39 {40 if (S[i]+(S[j]-S[i])*(n-1)>S[point-1]) continue;41 int last=S[j],d=S[j]-S[i],cnt=2;42 while (vis[last+d] && last+d<=S[point-1] && cnt<n) {cnt++;last=last+d;}43 if (cnt==n)44 {45 ans[ans_point].a=S[i];46 ans[ans_point++].d=d;47 }48 }49 //排序后输出 50 sort(ans,ans+ans_point);51 if (ans_point==0) printf("NONE\n");52 else 53 {54 for (i=0;i<ans_point;i++)55 printf("%d %d\n",ans[i].a,ans[i].d);56 }57 return 0;58 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。