Snowdream

I'm awake but my world is half asleep
posts - 398, comments - 234, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2007年5月30日

USACO 1.1.4 Arithmetic Progressions

第一次做是用一张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;
}

posted @ 2007-05-30 22:18 ZelluX 阅读(403) | 评论 (0) | 编辑 收藏

USACO 1.1.4 The Clocks

     摘要: 本来想练习了下deque的使用。用BFS，每个结点都记录了到目前为止转动的情况。结果发现内存消耗很大，就只好用DFS了。 /**//*PROG: clocksID: 06301031LANG: C++*/#include <iostream>#include <fstream>#include <deq...  阅读全文

posted @ 2007-05-30 21:34 ZelluX 阅读(327) | 评论 (0) | 编辑 收藏

C++ 入门笔记(2)

1. 最近用Dev C++写的几个程序中，最容易出错的就是忘记初始化和数组越界。C++（至少在Dev C++编译器中）并没有像Java那样严格的纠错功能，因此要格外小心。

2. C++ Programming Language上的一个样例程序，能看懂，但不能吃透。

 

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <iterator>

using namespace std;

int main() {
    ifstream fin("p61.in");
    istream_iterator<string> ii(fin);
    istream_iterator<string> eos;
 
    vector<string> b(ii, eos);
 
    ostream_iterator<string> oo(cout, "\n");
 
    unique_copy(b.begin(), b.end(), oo);
 
    system("PAUSE");
}

3. 向函数传递二维指针
void f(int a[][4]) 或者 void f(int (*a2)[4])

posted @ 2007-05-30 20:14 ZelluX 阅读(130) | 评论 (0) | 编辑 收藏