【洛谷 P1014】[NOIP1999 普及组] Cantor 表

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

题目大意

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

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

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

4/14/1, 4/24/2

5/15/1

按照Z字型排列,即:

image.png

问第NN项是什么。

做法

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

11\frac{1}{1}

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

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

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

......

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

那么,我们就要将第NN项所在行找出来:

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

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

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

可以得到以下的代码:

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

完整AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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);
}
}
-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!

欢迎关注我的其它发布渠道