题解 P1014 【Cantor表】

哦哟筷子

2018-12-16 22:40:48

Solution

### 现在是扯淡时间: 这是本蒟蒻第一次发题解,那么我这么垃圾为什么还要发题解呢 ~~其实是我看这道题实在是太简单了,居然出现在BOSS区~~ 其实是因为我看题解里的**大佬**实在是太**大佬**了,想找一个简单的办法解决这个问题 $update$ : 我写这篇题解也差不多快一年了,中间有很多评论我都没有回复,现在统一更新一下。首先声明一下,我写这篇题解的时候,刚入门,以为$AK$新手村已经很不错了,所以这话说的特别蠢(逃),而且似乎试炼场会被在不久的将来撤下,那这个话的起源都不知道去哪里了$233$. ------------ ### 好了,扯淡扯完了 可以恢复正题了(我觉得我这个程序应该是题解里最短的了(小声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$字型编号是正序(类似第二行)还是倒序(类似第三行)然后用最开始的结论输出原表中的行号除以列号就行了 最后,我只想表达一下自己那么蒟蒻在这里发题解的愧意 还有有问题的话大佬一定要指出!!(害怕)