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

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

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

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

作者: 八个月想一等 更新时间: 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

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

令人窒息的投稿