作者: 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;
}

作者: 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;
}

作者: 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;
}

作者: 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)（其实应该没比二分快多少，相当于让系统做了二分而已）解决此题的详解。既然是数学推算，代码就不贴了，没啥意思。

作者: 哦哟筷子 更新时间: 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表里的每一个数都是行数除以列数 所以输出只要这样就好了。。

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

还有有问题的话大佬一定要指出！！（害怕）