posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.4 Arithmetic Progressions

Posted on 2007-05-30 22:18 ZelluX 阅读(631) 评论(0)  编辑  收藏 所属分类: Algorithm
第一次做是用一张hash表记录的所有的数是否为所谓的bisquare，然后先枚举公差，再枚举首项，本来想这样做就不用再对结果排序了，没想到效率很低。
改为先枚举首项，再枚举第二项，然后计算公差后，速度提高不少。
另外第一次使用sort方法。
/*
PROG: ariprog
ID: 06301031
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Ans {
    int start;
    int step;
};

bool compareOp(const Ans& ans1, const Ans& ans2);

int main() {
    ifstream fin("ariprog.in");
    ofstream fout("ariprog.out");
    int n, m, i, j, k;
    bool solved = false;
    fin >> n >> m;

    // generate Arithmetic Progressions sequence
    bool seq[250*250*2 + 1];    
    for (i = 0; i <= m * m * 2; i++) {
        seq[i] = false;
    }
    for (i = 0; i <= m; i++) {
        for (int j = 0; j <= i; j++) {
            seq[i*i + j*j] = true;
        }
    }

    vector<Ans> result;
    int step;
    for (i = 0; i <= m * m * 2; i++) {
        if (!seq[i]) {
            continue;
        }
        for (j = i + 1; j <= m * m * 2; j++) {
            if (!seq[j]) {
                continue;
            }
            step = j - i;
            if (i + step * (n - 1) > m * m * 2) {
                break;
            }

            bool flag = true;
            for (k = 1; k < n; k++) {
                if (!seq[i + step * k]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                Ans ans;
                ans.start = i;
                ans.step = step;
                result.push_back(ans);
                solved = true;
            }
        }
    }
    if (!solved) {
        fout << "NONE" << endl;
    }

    sort(result.begin(), result.end(), compareOp);
    vector<Ans>::iterator iter;
    for (iter = result.begin(); iter != result.end(); iter++) {
        fout << iter->start << " " << iter->step << endl;
    }
    fout.close();
    return 0;
}

bool compareOp(const Ans& ans1, const Ans& ans2) {
    return ans1.step < ans2.step;
}

只有注册用户登录后才能发表评论。
网站导航: