2017-6-7
题目描述
求出满足条件的等差数列的首项和公差解答
枚举法代码
/* ID: 18795871 PROG: ariprog LANG: C++ */ #include<iostream> #include<cstdlib> #include<fstream> using namespace std; ifstream fin("ariprog.in"); ofstream fout("ariprog.out"); const int N=125000; bool f[N+1]; struct sl{ int a,b; }x[10001]; int m,n,r=0; int cmp(const void *a,const void *b){ struct sl *k1=(struct sl *)a; struct sl *k2=(struct sl *)b; if (k1->b==k2->b) return k1->a-k2->a; else return k1->b-k2->b; } void init(){ int i,j; for (i=0;i<=m;i++){ for (j=i;j<=m;j++){ f[i*i+j*j]=true; } } } void res(){ int i,j; for (i=0;i<=2*m*m;i++){ if (!f[i]) continue; for (j=1;j<=2*m*m/(n-1);j++){ if (i+j>2*m*m||!f[i+j]) continue; if (i+j*2>2*m*m||!f[i+j*2]) continue; if (i+j*(n-1)>2*m*m||!f[i+j*(n-1)]) continue; int cnt=3; while (cnt<n){ if (!f[i+cnt*j]) break; cnt++; } if (cnt==n){ x[r].a=i; x[r].b=j; r++; } } } } int main(){ fin>>n>>m; init(); res(); if (r==0) fout<<"NONE"<<endl; else{ qsort(x,r,sizeof(x[1]),cmp); for (int i=0;i<r;i++){ fout<<x[i].a<<" "<<x[i].b<<endl; } } return 0; }感觉和今年参加的蓝桥杯的一道填空题有点类似，有几点需要注意的地方： 1.首项，每个元素都要满足p^2+q^2。 2.在给f赋值的时候j，为了避免重复赋值，j要从i开始。 3.一开始写的时候超时，后来对j的范围进行约束即可。
/* ID: 18795871 PROG: ariprog LANG: C++ */ #include<iostream> #include<cstring> #include<fstream> using namespace std; ifstream fin("ariprog.in"); ofstream fout("ariprog.out"); const int N=125000; bool f[N+1]; int n,m; int main(){ int i,j,k,s; bool flag; while (fin>>n>>m){ memset(f,false,sizeof(f)); for (i=0;i<=m;i++){ for (j=i;j<=m;j++){ f[i*i+j*j]=true; } } flag=false; for (i=1;i<=(2*m*m)/(n-1);i++){ for (j=0;j+(n-1)*i<=(2*m*m);j++){ if (!f[j]) continue; s=0; for (k=j;k<=(2*m*m);k+=i){ if (!f[k]) break; else s++; if (s==n){ flag=true; fout<<j<<" "<<i<<endl; break; } } } } if (!flag) fout<<"NONE"<<endl; } return 0; }