P1014 Cantor表 题解


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

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

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

评论

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

算法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;
}

评论

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

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的博客查看    29  

/* 找规律

第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
    %%%%
  • hansp
    %%%%
作者: wmxwmx 更新时间: 2018-01-23 23:44  在Ta的博客查看    22  

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

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

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

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

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

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

已知数据是第个。

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

因此我们 设使得

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

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

Which is

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

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

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

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

同时

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

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

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

评论

  • gzn7264
    666
  • _风休住_
    orz
  • _风休住_
    %%%%%%%%%
  • shadow_fire
    %%%
  • 胡家睿
    %%%%%%%%%%
  • 胡家睿
    大佬tql
  • 我是真的的皮
    $tql$
  • 渊亭无迹
    确实很短,然而并不是最短的,在您的基础上哈可以再缩短俩行
作者: 哦哟筷子 更新时间: 2018-12-16 22:40  在Ta的博客查看    11  

现在是扯淡时间:

这是本蒟蒻第一次发题解,那么我这么垃圾为什么还要发题解呢

其实是我看这道题实在是太简单了,居然出现在BOSS区

其实是因为我看题解里的大佬实在是太大佬了,想找一个简单的办法解决这个问题


好了,扯淡扯完了

可以恢复正题了(我觉得我这个程序应该是题解里最短的了(小声BB))

废话不多说,先上标程

#include <bits/stdc++.h>
using namespace std; 
int main() {
    int n,k=1;
    cin>>n;
    while (n>k) {
        n=n-k;
        k++;
    }
    if(k%2==0) cout<<n<<"/"<<(k+1-n);
    else cout<<k+1-n<<"/"<<n;
    return 0;
} 

这里考虑到一个三角形数的问题

1
2 3
4 5 6
7 8 9 10

以此类推, 这道题其实就是歪过来的遍历(把头向左偏45度), 但是要考虑到奇偶行是相反的, 所以要判断奇偶。

另外就是很容易发现Cantor表里的每一个数都是行数除以列数 所以输出只要这样就好了。。

最后,我只想表达一下自己那么垃圾在这里发题解的愧意

还有有问题的话大佬一定要指出!!(害怕)