Snowdream

posts - 403, comments - 310, trackbacks - 0, articles - 7

USACO 1.1.4 Arithmetic Progressions

Posted on 2007-05-30 22:18 ZelluX 閱讀(632) 評論(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;

}

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 函數式編程另類指南[zz] URAL 1011 Sorting Networks URAL 題解 - wiki 《編程之美》上的一道題目的討論求n個32位無符號整數中異或后值最大的兩個數 SICP 習題記錄 (1) 正則表達式的復雜度 Minesweeper is NP-complete Tom Duff on Duff's Device

Snowdream

USACO 1.1.4 Arithmetic Progressions

日歷

常用鏈接

留言簿(21)

隨筆分類(390)

隨筆檔案(389)

文章檔案(7)

相冊

15ers

友情鏈接

收藏夾

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜