P1014 Cantor表 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • _UKE自动机_
    666
  • youyou2007
    厉害
  • Chevalier
    优美
  • Chevalier
    哦对了您算法三的第二个式子是不是打错了?
  • 洛谷小助手
    好样的!
  • cplusplus
    还可以用sqrt做到接近常数
  • にしき
    666
  • 愉快最厉害
  • 2017BeiJiang
    太牛了
  • team046
    6666666666
作者: cplusplus 更新时间: 2017-12-10 11:13  在Ta的博客查看    68  

算法1:模拟,按题意一个个枚举

时间复杂度O(n),可以通过本题n≤10^7

算法2:发现Z字形的每条斜线可以快速枚举,即枚举

1/1 , 1/2 , 3/1 , 1/4 , 5/1 , 1/6……找到要求的第n项所在斜线,再一个个枚举或计算得出答案

时间复杂度O(√n),可以通过n≤10^14

算法2.5:枚举第n项在哪一行,计算得出答案,比算法2好写,

时间复杂度同算法2

算法3:发现第i条斜线(即分子分母之和=i+1的所有项)中包含i*(i-1)/2+1至i*(i+1)中的每一项,所以可以二分分子分母之和,再根据分子分母之和的奇偶性直接计算第n项

时间复杂度O(㏒₂n),可以通过n≤10^18,加上高精可通过n≤10^1000

二分参考代码:

    #include<iostream>
    #include<cmath>
    using namespace std;
    int main(){
        long long l=1,r,mid,n,a;
        cin>>n;
        r=n;
        while(l<r){
            mid=(l+r)/2;
            if(mid*(mid+1)/2<n)l=mid+1;
            else r=mid;
        }
        a=n-l*(l-1)/2;
        if(l%2==0)cout<<a<<'/'<<l+1-a;
        else cout<<l+1-a<<'/'<<a;
        return 0;
}

评论

  • 星烁晶熠辉
    Excel中输入分数不是 (输入) 0 1/2 -> (显示) 1/2 吗?用'输入的话这个分数无法被用于计算
  • char32_t
    @星烁晶熠辉 因为这道题不需要计算所以哪种方法都无所谓的吧QAQ
  • xhx0809
    没错
  • 愉快最厉害
    呵呵
  • 蒙奇_D_mr
    orz
  • deadpool123
    Orz
  • qieqiemin
    Orz
  • lhaoyuan_renjie
    Orz
  • huyang2007
    orz
  • 北辰yama
    Orz大佬
作者: char32_t 更新时间: 2017-12-13 15:55  在Ta的博客查看    36  

P1014 【Cantor表】


模拟题

建议在Excel上打出Cantor表,再找规律(还有一个好处是可以用来测试)

如图 如表:

1/1 1/2 1/3 1/4 1/5 1/6 1/7 1/8 1/9

2/1 2/2 2/3 2/4 2/5 2/6 2/7 2/8

3/1 3/2 3/3 3/4 3/5 3/6 3/7

4/1 4/2 4/3 4/4 4/5 4/6

5/1 5/2 5/3 5/4 5/5

6/1 6/2 6/3 6/4

7/1 7/2 7/3

8/1 8/2

9/1

(普及)在单元格中输入分数前先输入一个单引号,避免被判断为日期

    #include<cstdio>
    int main() {
        int n, i=0, j=0;//前i条斜线一共j个数
        scanf("%d", &n);
        while(n>j) {//找到最小的i使得j>=n
            i++;
            j+=i;
        }
        if(i%2==1)
            printf("%d/%d",j-n+1,i+n-j);//i的奇偶决定着斜线上数的顺序,n是第i条斜线上倒数第j-n+1个数
        else
            printf("%d/%d",i+n-j,j-n+1);//若i是偶数,第i条斜线上倒数第i个元素是(i+1-i)/i
        return 0;
}

评论

  • MissKingchen
    这个规律找的好
  • huyang2007
    yyy
  • 夜刀神十香ღ
    这个规律找的好
  • PeterBrown
    66666
  • 初音Miku
    这个规律找的好
  • 树链剖分
    这个规律找的好
  • AstoriaG
    这个规律找的好
  • Steve_braveman
    这个规律找的好
  • 周元
    哈哈
  • 严川茗
    这个规律找的好(人的本质)
作者: royzhu 更新时间: 2017-11-30 13:33  在Ta的博客查看    21  

/* 找规律

第1层1/1

第2层1/2 2/1

第3层3/1 2/2 1/3

第4层1/4 2/3 3/2 4/1

第5层5/1 4/2 3/3 2/4 1/5

*/

#include<cstdio>
int main()
{
    int n;scanf("%d",&n);
    int t=1,ans=0;//t是表示下一次跳到下一次的距离,ans是表示第几层
    while(1)
    {
        if(n>t){n-=t;ans++;t++;}//printf("%d\n",ans);
        else if(n==t&&ans%2==0){printf("1/%d",ans+1);break;}
        //如果在n==t,并且为偶数层,就在第一行 第ans+1个 
        else if(n==t&&ans%2!=0){printf("%d/1",ans+1);break;}
        //如果在n==t,并且为奇数层,就在第ans+1行 第一个
        else if(n<t&&ans%2!=0){printf("%d/%d",ans+n-t+1,t-n+1);break;}
        //如果在n<t,并且为奇数层,t-n+1表示该层最后一个往后走n-1步,ans+n-t+1示该层最后一个往上走t-1步 
        else if(n<t&&ans%2==0){printf("%d/%d",t-n+1,ans+n-t+1);break;}
        // 如果在n<t,并且为偶数层,t-n+1表示该层最后一个往上走n-1步,ans+n-t+1示该层最后一个往后走t-1步 
    }
    return 0;
}

评论

  • rmxlinux
    %%%
  • 龙啸空
    6666
  • San_Francisco
    太强啦
  • cplusplus
    orz
  • 望道缘君
  • qdlisijia
    。。。
  • _DRJ_
    %%%%%%
  • 烂、白
    666
  • Ex10si0n
    %%%%
  • hsp20071016
    %%%%
作者: wmxwmx 更新时间: 2018-01-23 23:44  在Ta的博客查看    15  

虽然说这道题是考模拟.但是为啥感觉很多人真的都在写模拟....

这道题应该是属于那种给个数据那台计算器都能手打出结论的题哈.

数据小了都不用计算器都能在初中数学范围之内吧。

很明显就是O(1)复杂度(这里忽略系统开根的复杂度),求出Z形侧过来的三角形的行数

然后O(1)复杂度(又一次忽略系统乘法的复杂度),算出结果。

以下是公式以及简要的解释

已知数据是第个。

明显Z形画出来的三角,从左上到右下的行数是从1开始公差为1的等差数列。所以利用求和公式,设行数的话则有:

因此我们 设使得

根据建立起的函数的递增性,可知

所以通过求根公式求出然后向上取整就可以在O(1)的时间复杂度求出行数了。

Which is

接下来,还要求出所在当行的具体位置,这个就很容易了,只需要知道 到那一行总共有多少个:明显

所以要求的也就是那一行的第个。

接下来是一个对于知道行数+第几个的Cantor形式求法:

对于第a行,中所有个体,都有(“/”左边)+(“/”右边)

同时

结果是: <u>(_第几个_ )/(a+1- _第几个_ )</u>

<u>而剩下的则“/”两边相反即好。</u>

以上就是O(1)(其实应该没比二分快多少,相当于让系统做了二分而已)解决此题的详解。既然是数学推算,代码就不贴了,没啥意思。

评论

  • MaverickDan
    写下你的评论. . .
  • MaverickDan
    orz
  • 傲视天地
    %orz
  • 傲视天地
    %orz
  • Legends_Never_Die
    66666666666666666666666
  • Legends_Never_Die
    小老弟不错哦
  • Legends_Never_Die
    orz
  • Legends_Never_Die
    有我的风范
  • MaverickDan
    小睿睿 迪奥兄弟
  • MaverickDan
    tw亲友团
作者: 八个月想一等 更新时间: 2018-11-17 15:34  在Ta的博客查看    7  

蒟蒻首发

这个题卡了我三天,用了各种脑残方法最后在@八重樱飞(十分感谢)的帮助下做了出来

这个方法真的简单

先是找规律

1/1(第一行)

1/2 2/1(第二行)

3/1 2/2 1/3(第三行)

1/4 2/3 3/2 4/1(第四行)

......

顺着看下来就是规律

注意一下每行的第一个数与层数是有关系的

上代码

#include<iostream>
using namespace std;
int main(){
    int x,y,h=1,N,k;
    //x是分子,y是分母,h是行数,N是个数,k是 第N个数 与##~~~~ 对应行的第一个数 的距离(别卡在这,先往后看) 
    cin>>N;
    while(N>h){//用循环来算出行数 
        N=N-h;
        h++;
    }//很巧的是循环完后 N的值就是 第N个数对应行 的第几个(敲黑板)
    k=N-1;// 第N个数 与对应行的第一个数 的距离
    if(h%2==0)x=1+k,y=h-k;//判断行数是奇数还是偶数
    // (奇数:分子减k分母加k,偶数反之) 
    else x=h-k,y=1+k;
    cout<<x<<"/"<<y;//然后就算出来了 
    return 0;
}

祝各位早日AC

为什么我打一下回车显示出来只有一个空格

令人窒息的投稿