题解 P1014 【Cantor表】
哦哟筷子
·
·
题解
现在是扯淡时间：
这是本蒟蒻第一次发题解，那么我这么垃圾为什么还要发题解呢
其实是我看这道题实在是太简单了，居然出现在BOSS区
其实是因为我看题解里的大佬实在是太大佬了，想找一个简单的办法解决这个问题
------------
### 好了，扯淡扯完了
可以恢复正题了（我觉得我这个程序应该是题解里最短的了（小声BB））
$update$:显然这样的程序并不是最短的，评论已经有很多的$dalao$指出了，而且时间复杂度也并不优秀，但是当时就会有一种~~莫名的自信~~ 至于怎么压行，评论区也说得比较明白了，所以评论不用再提供压行思路了
废话不多说，先上代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,k=1;
cin>>n;
while (n>k) {
n=n-k;
k++;
}
if(k%2==0) cout<<n<<"/"<<(k+1-n);
else cout<<k+1-n<<"/"<<n;
return 0;
}
```
（从这一行往下全是$update$）
$update$: 首先我们观察到第$i$行，第$j$列的数就是$i/j$,这是第一个要发现的。
因为题目中要求是以$Z$字型编号
我们看题目中的表是：
$1/1,1/2,1/3$ ……
$2/1,2/2,2/3$ ……
$Z$字型编号以后（把头向左偏45度）：
第一行：$1/1$ ($1$号)
第二行：$1/2$ ($2$号) $2/1$($3$号)
第三行：$1/3$ **($6$号)** $2/2$ **($5$号)** $3/1$ **($4$号)**
$\uparrow$ 观察法易得每一行比上一行多1
代码里那个$while$循环，就是为了通过循环枚举，判断它在编号之后的第几行，第几个位置。
------------
（这个优化有没有都可以$AC$本题，但是评论指出我的时间复杂度不够优秀，因此提一提这个优化，不愿意看的可以直接略过看下一个分割线以后的内容。）
但其实可以直接出结论优化时间复杂度从$O(n)$ 优化到$O(1)$，这样就要考虑到等差数列求和
公式：$S=\frac{n(a_n+a_1)}{2}
所以，很显然Z字型排序之后，第k行的数编号n满足：
\frac{k(k-1)}{2} < n \le \frac{k(k+1)}{2}
这样就可以把那个循环优化掉。代码就不贴了 （因为懒，还怕出错）
但当时我才刚学，没想到上面的这个优化（罪恶之源：我太蒻了），只好写了个丑陋的模拟233。
代码当中k用来记Z字型编号之后的行数，显然第k行有k个数，因此每次n要减去k。
最后用k判断奇偶，是判断这一行Z字型编号是正序（类似第二行）还是倒序（类似第三行）然后用最开始的结论输出原表中的行号除以列号就行了
最后，我只想表达一下自己那么蒟蒻在这里发题解的愧意
还有有问题的话大佬一定要指出！！（害怕）