F - A Rational Sequence

题意:
根为1/1,假设某结点是p/q,则其左子树为p/(p+q),右子树为(p+q)/q,按此规律画一棵树,已知第n个结点是p/q,求第n+1个结点。

题解:
当 q=1 时为最顶端或者最左或者最右的子树 下一节点为 1 / p + 1
当 q=2 时为最中间的子树 下一节点为 2 / p
当 pq 时为右子树 下一节点为 q / p + q - 2(p % q)

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

#define lowbit(x) x & (-x)
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1e5+100;


int main()
{
   int t;
   int k;
   ll p,q;
   scanf("%d",&t);
   while(t --)
        {
          scanf("%d %lld/%lld",&k,&p,&q);
          if(q == 1)
            printf("%d 1/%lld\n",k, p + 1);
          else if(q == 2)
            printf("%d 2/%lld\n",k, p);
          else if(p < q)
            printf("%d %lld/%lld\n",k, q, q - p);
          else
            printf("%d %lld/%lld\n",k, q, p + q - 2 * (p % q));
        }
   return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注