题解 P1458 【顺序的分数 Ordered Fractions】

开挂老司机 · 2018-10-31 21:33:57 · 题解

没人用二分做吗？

来一发二分答案：

#include<cstdio>
using namespace std;
int n;
void binary(int l1,int l2,int r1,int r2)
{
    int sum1=l1+r1,sum2=l2+r2;
    if(sum2>n)//如果大于n就停
      return ;
    binary(l1,l2,sum1,sum2);//递归左路
    printf("%d/%d\n",sum1,sum2);//输出
    binary(sum1,sum2,r1,r2);//递归右路
}
int main()
{
    scanf("%d",&n);
    puts("0/1");
    binary(0,1,1,1);//二分答案
    puts("1/1");//先输出最小的和最大的
    return 0;
}