這個(gè),自己寫(xiě)了一個(gè)代碼,很丑.觀(guān)摩了一些以C++為"母語(yǔ)"的OIer的代碼,學(xué)習(xí)了一些新的寫(xiě)法.直接搜索是可以做的,因此我沒(méi)有更深入地思考過(guò)其他的解法.我發(fā)現(xiàn)我把學(xué)習(xí)C++當(dāng)作自己學(xué)習(xí)目標(biāo)的做法很大程度上淡化了我對(duì)算法的關(guān)注.
學(xué)習(xí)算法,看看《算法導(dǎo)論》之類(lèi)的書(shū)很有好處,學(xué)習(xí)語(yǔ)言,觀(guān)摩別人的代碼是必不可少的,這是我這幾天一來(lái)的體會(huì).
下面的代碼基本上就是按照人家的代碼打了一遍.不過(guò)很好理解,解釋也是多余的.
1 /*
2 ID:31440461
3 PROG:ariprog
4 LANG:C++
5 */
6 #include<iostream>
7 #include<algorithm>
8 using namespace std;
9 const int MAX=250*250*2+10;
10 bool flag[MAX]={};
11 int leg[MAX],size=0,res_cnt=0;
12 struct re
13 {
14 int a,b;
15 bool operator < (const re& x) const
16 {
17 return b<x.b || b==x.b && a<x.a;
18 }
19 }res[10000];
20
21 int main()
22 {
23 freopen("ariprog.in","r",stdin);
24 freopen("ariprog.out","w",stdout);
25 //memset(flag,0,sizeof(flag));
26 int n,m;
27 cin >> n >> m;
28 int max=m*m*2;
29 for (int i=0;i<=m ;++i )
30 for (int j=0;j<=m ;++j )
31 flag[i*i+j*j]=1;
32 for (int i=0;i<=max ;++i ) if (flag[i]) leg[size++]=i;
33
34 for (int i=0;i<size ;++i )
35 for (int j=i+1;j<size ;++j )
36 {
37 int d=leg[j]-leg[i];
38 if (leg[i]+(n-1)*d>max) break;
39 for (int k=2;k<n ;k++ )
40 if (!flag[leg[i]+k*d]) goto L1;
41 res[res_cnt].a=leg[i];
42 res[res_cnt++].b=d;
43 L1:;
44 }
45 sort(res,res+res_cnt);
46 if (!res_cnt) cout << "NONE" << endl;
47 else
48 for (int i=0;i<res_cnt ;i++ ) cout << res[i].a << ' ' << res[i].b << endl;
49 return 0;
50 }
51
52