专栏首页饶文津的专栏【USACO 2.1】Ordered Fractions

【USACO 2.1】Ordered Fractions

TASK: 直接枚举,约分,排序,去重

#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int nu,deno;
    double v;
}a[40000];
int n,cnt;
int cmp(node a,node b){
    return a.v<b.v;
}
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    freopen("frac1.in","r",stdin);
    freopen("frac1.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        for(int j=max(i,1);j<=n;j++){
            int g=gcd(i,j);
            a[cnt++]=(node){i/g,j/g,i*1.0/j};
        }
    sort(a,a+cnt,cmp);
    for(int i=0;i<cnt;i++){
        if(i==0||a[i].v-a[i-1].v>1e-6||a[i].v-a[i-1].v<-1e-6)
        printf("%d/%d\n",a[i].nu,a[i].deno);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【POJ 3321】Apple Tree

    有n个节点以1为根节点的树,给你树的边关系u-v,一开始每个节点都有一个苹果,接下来有两种操作,C x改变节点x的苹果状态,Q x查询x为根的树的所有苹果个数。

    饶文津
  • 【HDU 5438】Ponds

    存边的时候,要头尾都存这个边。用dfs或者队列删点,再用并查集或者dfs确定联通块,然后统计联通块的点数,最后累加。

    饶文津
  • 「AtCoder Grand018B」Sports Festival(暴力)

    饶文津
  • 【2020HBU天梯赛训练】7-30 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    韩旭051
  • 2017icpc beijing-I题-Colored Nodes

    题意:给出n个点m条边 然后每个时间点,与这个位置相连的所有点就会变成这个点的颜色 比如时间1的时候就是以这个位置相连的点2 变成1的颜色同理如下,通过2个循环...

    逐梦的青春
  • hdu 1598 find the most comfortable road(枚举+卡鲁斯卡尔最小生成树)

    find the most comfortable road Time Limit: 1000/1000 MS (Java/Others)    Memory ...

    Gxjun
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • 洛谷P2763 试题库问题(最大流)

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-4 使用函数求素数和

    其中函数prime当用户传入参数p为素数时返回1,否则返回0;函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券