[USACO1.4]等差数列 Arithmetic Progressions
发布时间
阅读量：
阅读量
题目：
一种称为能够表示为a,\ a+b,\ a+2b,\ldots,\ a+nb\ （其中n=0, 1, 2, 3,\ldots）的一种序列。
在题目中a是非负整数值而b是正整数值。
开发一个程序以识别在集合S中的长度为n且具有特定特征的所有等差序列。
双平方数组合是由所有满足形式p^2 + q^2\ （其中p\ 和q\ 均为非负值）的数量所构成的一个集合。
输入格式：
第一行: N(3<= N<=25),要找的等差数列的长度。
第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。
输出格式：
若无法确定数列，则应输出`NONE’。
一旦发现有多个解，则需依次列出所有解的坐标点，并以有序对的形式表示为(a_i,b_i)。
为了确保结果的一致性与规范性，在排序时应当首先按照b值进行升序排列，在相同b值的情况下再按照a值进行降序排列。
该等差数列的最大数量限制为10,000项。
样例：
输入
5
7
输出
1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24
思路：
为了降低计算复杂度，在预处理阶段我们需要确定第i个元素是否能表示为p^{2} + q^{2}的形式。
进一步确定在序列中排在第l位的元素是否符合该条件。
ans[i]代表第i个元素是否满足条件，则其值可取1或0。
在枚举可能的长度和起点时，需对结果进行优化处理以提高效率。
最后对所有候选方案进行验证以确保其合法性。
代码:
# include<cstdio>
# include<cstdlib>
# include<iostream>
# include<algorithm>
using namespace std;
int ans[1000100],f[1000000];
int main(){
int n,m,p,q,i,l=0,j,k,d1=0;
scanf("%d%d",&n,&m);//输入
for(p=0;p<=m;p++)
for(q=p;q<=m;q++){
ans[p*p+q*q]=1;//将可以表示为q*q+p*p的数标记为一
}
l=0;
for(i=0;i<=m*m+m*m;i++) {
l+=ans[i];
if(ans[i]){f[l]=i;}//求出第l个
}
for(j=1;j<=m*m*2/(n-1);j++){//枚举长度
for(i=1;i<=l;i++){//枚举起点
if(f[i]+j*(n-1)>m*m*2)break;//如果已大于最大值就退出
int c=1,d=f[i];
for(k=1;k<=n-1;k++){
d=d+j;//枚举每一项
if(!ans[d]){//如果不是就退出
c=0;
break;
}
}
if(c){d1=1;printf("%d %d\n",f[i],j);}//判断输出
}
}
if(d1==0)printf("NONE\n");//如果没有合法序列输出NONE
return 0;
}
AI写代码全部评论 (0)
还没有任何评论哟~