这是继虫洞之后又让我为难的一个 剪枝题目，无论如何，做的再快，也只能过6个点，最后三个点也TLE。后来参考了一下标答，大概思路是这样的。
朴素算法就不多说了，枚举a,b然后判断就行，网上说这样优化到位的话，是可能过掉的，但是我一直没有优化出来，所以就放弃了这一做法。。
标答的做法：首先要预处理一下所有的双平方数，我的做法是只用BOOL标记，但是这里还要存一下数的序列。然后，我们知道，我们要找的等差数列中的第一个数一定是这里面的数，那么就利用这一个特点，每次从公差开始枚举，如果序列长度还不够，但是已经超过了限制，或者根本就不是序列中的数，就标记一下，如果这个标记在判断的时候没有被标记过，说明这组解是可行的，就保存下来。。。写到这里才发现这题好水好水。
没有自己A掉这题的根本原因是因为没有深入思考这数的性质，话说一开始我理解这题也是读了上十遍，最后没明白请教的别人题意，最关键的一句话：我们要找的等差数列中的第一个数一定是这个序列里面的数。。。
下面直接代码。
1 #include2 #include 3 #include 4 #include 5 #include 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\n",ans[i].a,ans[i].b);57 }58 else{59 printf("NONE\n");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 else68 return a.b < b.b;69 }
做完这题后，又看了一下下一节的第一题，数字三角形，主要是滚动数组的用法。。
dp[i&1][j] = ....dp[1-(i&1)][j...]乱搞。。。。。