【NOIP1999 普及组T1】 Cantor 表

一道水模拟，可以直接算。但菜鸡不会……

题目大意

原题导航：https://www.luogu.com.cn/problem/P1014

一个表格： 1/11/11/1 , 1/21/21/2 , 1/31/31/3 , 1/41/41/4, 1/51/51/5 …

2/12/12/1, 2/22/22/2 , 2/32/32/3, 2/42/42/4…

3/13/13/1 , 3/23/23/2, 3/33/33/3…

4/14/14/1, 4/24/24/2…

5/15/15/1…

按照Z字型排列，即：

image.png

问第NNN项是什么。

做法

这样的表格比较难看，我们先把它转换一下：

11\frac{1}{1}11​

12,21\frac{1}{2},\frac{2}{1}21​,12​

31,22,13\frac{3}{1},\frac{2}{2},\frac{1}{3}13​,22​,31​

14,23,32,41\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1}41​,32​,23​,14​

.........

这样将每一行都分离了出来，可以发现，每行的数的数量形成了等差数列。第一行有111个数，第二行有222个数……

那么，我们就要将第NNN项所在行找出来：

int add=1;
while(n>add){
    n-=add;//倒数第几个
    add++;//第几行，也表示当前行有几个
}

当然，这个可以直接算出来，没有必要暴力枚举，但数据太水了，依旧可以过。

知道它是第几行的，我们就要看他是什么了。不难发现，当add是奇数的时候，add行分母依次为从111递增到add的数列，分子为从add递减至111的数列；而当add是偶数的时候，add行分子依次为从111递增到add的数列，分母为从add递减至111的数列。

可以得到以下的代码：

//add为当前行数的数量，n是倒数第几个，最后别忘了+1
//可以自己算算看看
if(add%2==1){
    printf("%d/%d",add-n+1,n);
}else{
    printf("%d/%d",n,add-n+1);
}

完整AC代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int add=1;
    while(n>add){
        n-=add;
        add++;
    }
    if(add%2==1){
        printf("%d/%d",add-n+1,n);
    }else{
        printf("%d/%d",n,add-n+1);
    }
}