题目

题目描述

现在给你一个数集，里面的数字都是由p^2+q^2这种形式构成的0 <= p,q <= M，我现在需要你在其中找出一个长为N的等差数列，数列中的第一个数字为a，公差为b，当你找到多个这样的数列时，输出数列的a b值，输出顺序按照b的值从小到大排序，当b的值一样的时候，按照a的值从小到大排序输出。

数据范围

(3 <= N <= 25)

(1 <= M <= 250)

样例输入

5

7

样例输出

1 4

37 4

2 8

29 8

1 12

5 12

13 12

17 12

5 20

2 24

解题思路

数据量比较小，所以还是可以暴力的，开始的时候为了方便直接用set进行保存数据，之后遍历set。结果果然超时了。然后换了一种写法，用数组来保存O(1)的查找时间，最终顺利AC。之后我加了一个剪枝，发现时间可以缩短0.4秒，最终以0.2秒多跑完所有样例。

解题代码

/*

ID: yinzong2

PROG: ariprog

LANG: C++11

*/

#define MARK

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXN = 125000+10;

bool exist[MAXN];

int num[MAXN];

struct Num {

    int a,b;

}ans[MAXN];

int N, M;

bool check(int a, int b) {

    for(int i = 0; i < N; i++) {

        int temp = a+i*b;

        if(!exist[temp]) {

            return false;

        }

    }

    return true;

}

bool cmp(Num A, Num B) {

    if(A.b < B.b) return true;

    else if(A.b == B.b) {

        return A.a < B.a;

    }

    else return false;

}

int main() {

#ifdef MARK

    freopen("ariprog.in", "r", stdin);

    freopen("ariprog.out", "w", stdout);

#endif // MARK

    while(~scanf("%d%d", &N, &M)) {

        memset(exist, false, sizeof(exist));

        int cnt = 0;

        for(int i = 0; i <= M; i++) {

            for(int j = 0; j <= M; j++) {

                int temp = i*i+j*j;

                if(!exist[temp]) {

                    exist[temp] = true;

                    num[cnt++] = temp;

                }

            }

        }

        sort(num, num+cnt);

        bool flag = false;

        int id = 0;

        for(int i = 0; i < cnt; i++) {

            int a = num[i];

            for(int j = i+1; j < cnt; j++) {

                int b = num[j] - a;

                if(a+(N-1)*b > M*M*2) break;

                if(check(a,b)) {

                    ans[id].a = a;

                    ans[id].b = b;

                    id++;

                    flag = true;

                }

            }

        }

        if(flag) {

            sort(ans, ans+id, cmp);

            for(int i = 0; i < id; i++) {

                printf("%d %d\n", ans[i].a, ans[i].b);

            }

        }else {

            printf("NONE\n");

        }

    }

    return 0;

}