題目

題目描述

一個等差數列是一個能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的數列。

在這個問題中a是一個非負的整數，b是正整數。寫一個程序來找出在雙平方數集合(雙平方數集合是所有能表示成p的平方 + q的平方的數的集合,其中p和q為非負整數)S中長度為n的等差數列。

輸入輸出格式

輸入格式：

?

第一行: N(3<= N<=25),要找的等差數列的長度。

第二行: M(1<= M<=250),搜索雙平方數的上界0 <= p,q <= M。

?

輸出格式：

?

如果沒有找到數列,輸出`NONE'。

如果找到了，輸出一行或多行, 每行由二個整數組成:a,b。

這些行應該先按b排序再按a排序。

所求的等差數列將不會多于10,000個。

?

輸入輸出樣例

輸入樣例#1：?
5 7 輸出樣例#1：?
1 4 37 4 2 8 29 8 1 12 5 12 13 12 17 12 5 20 2 24

題目大意

??題目剛開始我也看不懂

? ?后來懂了。。。

? ?其實就是在一個數列里找到長度為n的等差數列

? ?這個數列是（0到m）平方加上 （0到m）平方形成的所有的數

? ?輸出第一個數的數值和公差即可

分析

? ??首先，當然是構建數列啦

? ?然后我們就要找等差數列啦

? ?等差數列從何入手呢？

? ?等差數列顧名思義是有一個公差的

? ?我們只需要枚舉公差就好了

? ?于是我們通過枚舉前兩的在等差數列的數得到公差后

? ?向后查找其他數

? ?最后如果所有數存在就可以算一種了

? ?排序 就可以輸出啦

? ??

? ?還有一個要注意的：

? ?一個很重要的優化點

? ?當數很多，公差很大時

? ?顯然超時

? ?所以我們在查找前要加判斷

? ?當? 第一個數+（n-2）*公差>最大值時 break

? ?因為是有序的，當出現第一個大于最大值時，后面都不行

? ?

代碼

?

??

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int a[62500000],b[62500000]; 5 struct sb 6 { 7 int shu,cha; 8 }ans[600000]; 9 bool cmp(sb a,sb b) 10 { 11 if (a.cha<b.cha) return true; 12 if (a.cha==b.cha) 13 if (a.shu<b.shu) return true; 14 return false; 15 } 16 int main () 17 { 18 int n,m; 19 cin>>n>>m; 20 int k=1; 21 for (int i=0;i<=m;i++) // 得到數列 22 for (int j=i;j<=m;j++) 23 { 24 a[i*i+j*j]=1; 25 b[k++]=i*i+j*j; 26 } 27 sort(b+1,b+1+k); //排序 28 int wz=unique(b+1,b+1+k)-b; //因為會有重復，所以去重 29 k=1; 30 for (int i=1;i<=wz;i++) 31 { 32 for (int j=i+1;j<=wz;j++) 33 { 34 int ca=b[j]-b[i],bj=0; 35 if (ca<=0) continue; 36 if (b[j]+(n-2)*ca>2*m*m) break; //優化 37 for (int ii=1;ii<=n-2;ii++) 38 { 39 if (a[b[j]+ii*ca]!=1) 40 { 41 bj=1; 42 break; 43 } 44 } 45 if (bj==0) { 46 ans[k].shu=b[i]; 47 ans[k].cha=ca; 48 k++; 49 } 50 } 51 } 52 sort(ans+1,ans+1+k,cmp); //排序輸出 53 if (k<2) cout<<"NONE"; 54 for (int i=2;i<=k;i++) 55 cout<<ans[i].shu<<" "<<ans[i].cha<<endl; 56 }

?

轉載于:https://www.cnblogs.com/zjzjzj/p/10085450.html

總結

以上是生活随笔為你收集整理的[USACO1.4]等差数列 Arithmetic Progressions的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。