USACO Arithmetic Progressions (ariprog) 题解

这道题目学到的是，如果是bool类型的判断，亲你还是用数组，加上初始化来得容易一些啊，然后判断是否是Bisquare的时候脑子抽筋，没有直接根据index去判断，导致一开始总是超时。但是值得鼓励的是自己的思路还是正确的，昨天关于数组的想法并没有及时记录或者实现。

下面是最终代码：

/*
ID: bbsunch2
PROG: ariprog
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
#include<fstream>
using namespace std;
const long M_MAX=250;
int N,M;
bool bNumIsBisquare[(M_MAX)*(M_MAX)*2+1];

int calculate_bisquares(const int upperBound){
    for(int i = 0; i <= M; i++){
        for(int j = 0; j <= M; j++){
            bNumIsBisquare[i*i+j*j] = true;
        }
    }
}

bool arithmetic_progression(const int i, const int j){
    for(int k =0; k < N; k++){
        if(!bNumIsBisquare[i+k*j]) return false;
    }
    return true;
}

int main(){
    ofstream fout("ariprog.out");
    ifstream fin("ariprog.in");
    fin >> N;
    fin >> M;
    int squareM = M*M;
    int upperBound = 2* squareM+1;
    bool found = false;
    memset(bNumIsBisquare, false, sizeof(bNumIsBisquare));
    calculate_bisquares(upperBound);
    map<int, vector<int> > difference__firstNumbers;
    for(int i = 0; i < upperBound; i++){
        for(int j = 1; j < upperBound; j++){
            if (i + (N-1)*j > upperBound) break;
            if( arithmetic_progression(i,j)){
                found = true;
                if(difference__firstNumbers.find(j) == difference__firstNumbers.end()){
                    vector<int> tempVector;
                    tempVector.push_back(i);
                    difference__firstNumbers.insert(pair<int, vector<int> > (j, tempVector));
                }else{
                    difference__firstNumbers[j].push_back(i);
                }
            }
        }
    }
    if(!found){
        fout << "NONE" << endl;
        return 0;
    }
    for(map<int, vector<int> >::iterator it = difference__firstNumbers.begin(); it != difference__firstNumbers.end(); it++){
        int difference = it->first;
        vector<int> firstNumbers = it->second;
        sort(firstNumbers.begin(), firstNumbers.end());
        for(int i = 0; i < firstNumbers.size(); i++){
            cout << firstNumbers[i] << " " << difference << endl;
            fout << firstNumbers[i] << " " << difference << endl;
        }
    }

    return 0;
}

?

?

USACO Arithmetic Progressions (ariprog) 题解

原文：http://bbsunchen.iteye.com/blog/2163401