题解 P1014 【Cantor表】
虽然说这道题是考模拟.但是为啥感觉很多人真的都在写模拟....
这道题应该是属于那种给个数据那台计算器都能手打出结论的题哈.
数据小了都不用计算器都能在初中数学范围之内吧。
很明显就是O(1)复杂度(这里忽略系统开根的复杂度)，求出Z形侧过来的三角形的行数
然后O(1)复杂度(又一次忽略系统乘法的复杂度)，算出结果。
以下是公式以及简要的解释
已知数据是第个。
明显Z形画出来的三角，从左上到右下的行数是从1开始公差为1的等差数列。所以利用求和公式，设行数为的话则有：
因此我们 设使得
根据建立起的函数的递增性，可知
所以通过求根公式求出然后向上取整就可以在O(1)的时间复杂度求出行数了。
Which is
接下来，还要求出所在当行的具体位置，这个就很容易了，只需要知道 到那一行总共有多少个：明显个
所以要求的也就是那一行的第个。
接下来是一个对于知道行数+第几个的Cantor形式求法：
对于第a行，中所有个体，都有（“/”左边）+（“/”右边）
同时 ，
结果是： <u>(_第几个_ )/(a+1- _第几个_ )</u>
<u>而剩下的则“/”两边相反即好。</u>
以上就是O(1)（其实应该没比二分快多少，相当于让系统做了二分而已）解决此题的详解。既然是数学推算，代码就不贴了，没啥意思。