【NOIP1999 普及组T1】 Cantor 表

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

题目大意

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

一个表格：
$1/1$ , $1/2$ , $1/3$ , $1/4$, $1/5$ …

$2/1$, $2/2$ , $2/3$, $2/4$…

$3/1$ , $3/2$, $3/3$…

$4/1$, $4/2$…

$5/1$…

按照Z字型排列，即：

问第$N$项是什么。

做法

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

$\frac{1}{1}$

$\frac{1}{2},\frac{2}{1}$

$\frac{3}{1},\frac{2}{2},\frac{1}{3}$

$\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1}$

$...$

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

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

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

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

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

可以得到以下的代码：

//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);
    }
}