本文最后更新于:2020年8月24日 下午

关于Stern-Brocot tree网上的资料较少(后记:实际上并不少,只是竞赛中讨论的不多),能够找到的资源有Wikipedia以及《具体数学》上的介绍,这里大概总结一下这个树形结构的性质。

Stern-Brocot tree:

Stern-Brocot tree构成了一个无限的二叉排序树,可以将所有的正有理数从小到大列举出来。

构造方法可以理解为:先在左边写上01\frac{0}{1},右边写上10\frac{1}{0},代表零和正无穷,然后分子、分母分别相加,得到11\frac{1}{1},写在中间,之后每次把当前层复制到下一层,然后对于下一层相邻两个有理数之间还是分子分母分别相加,得到新的有理数,写在两者中间,重复这个操作就可以无限的写下去,进而得到所有的有理数。树形结构的获得见上图。

记树中的一个节点yx\frac{y}{x},它是由LmLn,RmRn\frac{L_m}{L_n},\frac{R_m}{R_n}这两个数产生的,那么可以发现:

1.LmLn\frac{L_m}{L_n}是位于左上方且离它最近的祖先,RmRn\frac{R_m}{R_n}是位于右上方且离它最近的祖先。

2.gcd(x,y)=1gcd(x,y)=1

3.RmLnLmRn=1R_mL_n-L_mR_n=1

4.以yx\frac{y}{x}为根的子树中的所有数都落在区间(LmLn,RmRn)(\frac{L_m}{L_n},\frac{R_m}{R_n})

找一个数ba\frac{b}{a}在树中的位置可以通过在树上二分,但如果一步一步走的话,时间复杂度关于a,b是线性的,比如找1109\frac{1}{10^9},需要从根一直往左走109110^9-1步。但是可以证明,在树上“拐弯”的次数是 O(log)O(log) 的 ,可以与辗转相除法联系起来,详见这个视频。这样每次直走的步数我们可以列不等式O(1)O(1)求出,拐弯的过程递归下去就好了。也可以用具体数学书上的结论。

题目列表:

1.Alice, Bob, Oranges and Apples

题意:懒得叙述了,总之把在Stern-Brocot tree上走的过程抽象了一下,简化的题意就是给一个分数,输出从根到该点的路径。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll x,y;
    while(scanf("%lld%lld",&x,&y)!=EOF){
        if(__gcd(x,y)>1){
            puts("Impossible");
            continue;
        }
        while(x!=y){
            if(x<y) {
                ll t=(y-1)/x;
                y-=t*x;
                printf("%lldB",t);
            } else {
                ll t=(x-1)/y;
                x-=t*y;
                printf("%lldA",t);
            }
        }
        puts("");
    }
}

2. 2017 CCPC 哈尔滨 Cow`s Segment

题意:给两个高精度浮点数a,ba,b,求最小的正整数xx使得区间[ax,bx)[ax,bx)包含整数(注,原题面有误,真实的数据是左闭右开的)。

思路:设axy<bxax\le y<bx,即ayx<ba\le \frac{y}{x}<b,就按上面说的,在Stern-Brocot tree上二分,直到找到第一个符合条件的点,同时就是x的最小值。

(Java写起来太长了

import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    final static BigInteger one=BigInteger.ONE;
    final static BigInteger zero=BigInteger.ZERO;
    final static BigInteger base=BigInteger.valueOf(10);
    final static int LEN=300;
    static BigInteger ans;
    public static BigInteger trans(String s){
        int len=s.length();
        int num=LEN,flag=0;
        BigInteger ans=BigInteger.valueOf(0);
        for(int i=0;i<len;++i)
        {
            if(s.charAt(i)=='.') flag=1;
            else 
            {
                num-=flag;
                int now=s.charAt(i)-'0';
                ans=ans.multiply(base).add(BigInteger.valueOf(now));
            }
        }
        for(int i=1;i<=num;++i)
            ans=ans.multiply(base);
        return ans;
    }
    public static void dfs(BigInteger a,BigInteger b,BigInteger c,BigInteger d,
    		BigInteger la,BigInteger lb,BigInteger ra,BigInteger rb,
    		BigInteger x,BigInteger y)
    {
        BigInteger le=b.multiply(x).subtract(a.multiply(y));
        BigInteger ri=d.multiply(x).subtract(c.multiply(y));
        if(le.compareTo(zero)<=0 && ri.compareTo(zero)>0)
        {
            ans=x;
            return ;
        }
        BigInteger k,tem;
        if(le.compareTo(zero)>0)
        {
            tem=a.multiply(rb).subtract(b.multiply(ra));
            k=le.add(tem.subtract(one)).divide(tem);
            dfs(a,b,c,d,
            x.add(k.subtract(one).multiply(ra)),y.add(k.subtract(one).multiply(rb)),
            ra,rb,
            x.add(k.multiply(ra)),y.add(k.multiply(rb)));
        }
        else
        {
            ri=ri.negate();
            tem=d.multiply(la).subtract(c.multiply(lb));
            k=ri.divide(tem).add(one);
            dfs(a,b,c,d,
            la,lb,
            x.add(k.subtract(one).multiply(la)),y.add(k.subtract(one).multiply(lb)),
            x.add(k.multiply(la)),y.add(k.multiply(lb)));
        }
    }
    public static void main(String[] args)
    {
        Scanner cin=new Scanner(System.in);
        BigInteger pow=base.pow(LEN);
        BigInteger a,b;
        int T=cin.nextInt();
        for(int cas=1;cas<=T;++cas)
        {
            String s=cin.next(),t=cin.next();
            a=trans(s);
            b=trans(t);
            dfs(pow,a,pow,b,one,zero,zero,one,one,one);
            System.out.println(ans);
        }
    }
}

3.Petrozavodsk Winter-2018. AtCoder Contest C Construct Point

题意:二维平面上给整点三角形的三个顶点坐标,判断三角形内部(不含边界)是否存在整点,如果有输出任意一个。

思路:先考虑这么一个子问题,在直线y=baxy=\frac{b}{a}xy=dcxy=\frac{d}{c}x之间找一个整点,范围0<xD0<x\le D,那么还是bax<y<dcx\frac{b}{a}x < y<\frac{d}{c}x,得到ba<yx<dc\frac{b}{a}<\frac{y}{x}<\frac{d}{c},找到最小的x和D比较即可。对于任意三角形的话,通过分割,平移,对称的变换就能规约成上述子问题啦。

代码略。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

Knapsack and Queries 上一篇
线段树合并 下一篇