P1014 [NOIP1999 普及组] Cantor 表

这道题需要我们按照Z形，给出第N项的值。按照Z形对表进行观察，我们可以对表中的数据进行一个分组

如图，发现第一层有一个数，第二层有两个数，第三层有三个数，第n层有n个数，且奇数层的分母是从层数p开始数到1，也就是p,p-1,p-2,p-3........，分子是1数到p，偶像层与奇数层相反。那么知道这个规律后，我们就需要根据要求的是第几项来对这一项的分子分母进行表示。

例如题目中给的N  = 7，第7项是第四层中的第一个数，偶数层分子是从1数到p，

也就是(n-(sum-p))，其中sum是上一层有几个元素，分母是p-这一项是这一层中第一个元素+1也就是p-(n-(sum-p))+1,这里可以进行化简。得到分母分子如何进行表示之后，我们只需要判断这一层是奇数层还是偶数层即可。

#include <iostream>
#include <vector>

using namespace std;
int main() {
	int n; cin >> n;
	int p = 0, sum = 0; 
	while (n>sum) {
		p++;
		sum += p;
	}
	//分母分子位置交换
	if (p % 2 == 1) {
		cout << sum - n + 1 << "/" << n - (sum - p);
	}
	else if(p%2==0) {
		cout << n - (sum - p) << "/" << sum - n + 1;
	}
	return 0;
}//p-(n-(sum-p))+1->p-n+(sum-p)+1->p-n+sum-p+1->sum-n+1

其中寻找所求项在第几层的时候，可以维护一个sum对当前有多少个元素保存，与n进行比较，如果sum>n,则所在元素在这一层