这是继虫洞之后又让我为难的一个 剪枝题目，无论如何，做的再快，也只能过6个点，最后三个点也TLE。后来参考了一下标答，大概思路是这样的。
朴素算法就不多说了，枚举a,b然后判断就行，网上说这样优化到位的话，是可能过掉的，但是我一直没有优化出来，所以就放弃了这一做法。。
标答的做法：首先要预处理一下所有的双平方数，我的做法是只用BOOL标记，但是这里还要存一下数的序列。然后，我们知道，我们要找的等差数列中的第一个数一定是这里面的数，那么就利用这一个特点，每次从公差开始枚举，如果序列长度还不够，但是已经超过了限制，或者根本就不是序列中的数，就标记一下，如果这个标记在判断的时候没有被标记过，说明这组解是可行的，就保存下来。。。写到这里才发现这题好水好水。
没有自己A掉这题的根本原因是因为没有深入思考这数的性质，话说一开始我理解这题也是读了上十遍，最后没明白请教的别人题意，最关键的一句话：我们要找的等差数列中的第一个数一定是这个序列里面的数。。。
下面直接代码。
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cstdio> 5 #include <algorithm> 6 7 using namespace std; 8 9 int N,M; 10 11 int tot = 0,size = 0; 12 bool vi[125001]; 13 int list[125001]; 14 15 int i,j,k; 16 17 struct data{ 18 int a,b; 19 }ans[10000]; 20 21 bool cmp(data,data); 22 23 int main(){ 24 freopen("ariprog.in","r",stdin); 25 freopen("ariprog.out","w",stdout); 26 scanf("%d%d",&N,&M); 27 for(i = 0;i <= M;++ i) 28 for(j = 0;j <= M;++ j){ 29 vi[i*i + j*j] = true; 30 } 31 for(i = 0;i <= 2*M*M;++ i){ 32 if(vi[i]) 33 list[++ tot] = i; 34 } 35 36 for(i = 1;i <= tot;++ i){ 37 for(j = i+1;j <= tot;++ j){ 38 int tp = list[j] - list[i]; 39 bool flag = false; 40 for(k = 2;k < N;++ k){ 41 if(list[i]+tp*k > 2*M*M || !vi[list[i]+tp*k]){ 42 flag = true; 43 break; 44 } 45 } 46 if(!flag){ 47 size ++; 48 ans[size].a = list[i]; 49 ans[size].b = tp; 50 } 51 } 52 } 53 if(size){ 54 sort(ans+1,ans+size+1,cmp); 55 for(i = 1;i <= size;++ i) 56 printf("%d %d ",ans[i].a,ans[i].b); 57 } 58 else{ 59 printf("NONE "); 60 } 61 return 0; 62 } 63 64 bool cmp(data a,data b){ 65 if(a.b == b.b) 66 return a.a < b.a; 67 else 68 return a.b < b.b; 69 }
做完这题后，又看了一下下一节的第一题，数字三角形，主要是滚动数组的用法。。
dp[i&1][j] = ....dp[1-(i&1)][j...]乱搞。。。。。