付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
水题,枚举 ,只是我在判重的时候用 set<double> 这个在usaco 得出的结果和 本地vs 运行的结果不同。最后改用gcd 判断 分子除以分母是否可约。 

/*
ID:fuxiang2
PROG: frac1
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <set>
#include <cmath>
#include <cstring>
#include <cstdlib>
 
#define REP(i, n) for (int i=0;i<int(n);++i)
#define FOR(i, a, b) for (int i=int(a);i<int(b);++i)
#define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i)
#define REP_1(i, n) for (int i=1;i<=int(n);++i)
#define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i)
#define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i)
#define EACH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)
 
using namespace std;
ofstream fout ("frac1.out");
ifstream fin ("frac1.in");
 
class Node{
public
    int a;//分子
    int b;// 分母
    double val;
    Node() {}
    Node(int _a,int _b ,double _val) :a(_a),b(_b),val(_val){}
 
    bool operator < (const Node & m)const {
        return val < m.val; 
    }
};
set<double> sd;
vector<Node> vn;
int gcd(int a,int b)
{
    if(b == 1)
        return b;
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
void worik(int n)
{
    double ans ;
    FOR_1(i,1,n)
        FOR_1(j,1,n){
            if(i < j)
            {
                ans = i*1.0/j;
                //if(sd.find(ans) == sd.end())
                if(gcd(j,i) == 1)
                {
                    Node  node(i,j,ans);
                    vn.push_back(node);
                    sd.insert(ans);
                }
            }
        }
     
    sort(vn.begin() ,vn.end());
 
    fout<< "0/1" << endl;
    for(vector <Node> ::iterator iter = vn.begin() ; iter != vn.end() ; iter ++){
        fout << (iter)->a << "/" << (iter)->b <<endl;
    }
    fout<<"1/1"<<endl;
 
}
 
int main()
{
    int n;
    fin>>n;
    worik(n);
    return 0;
 
}


原始博客地址: http://www.fuxiang90.com/2012/07/usaco2-1-ordered-fractions/
posted on 2012-07-18 09:54 付翔 阅读(237) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜