wmxwmx 的博客

wmxwmx 的博客

题解 P1014 【Cantor表】

posted on 2018-01-23 23:44:37 | under 题解 |

虽然说这道题是考模拟.但是为啥感觉很多人真的都在写模拟....

这道题应该是属于那种给个数据那台计算器都能手打出结论的题哈.

数据小了都不用计算器都能在初中数学范围之内吧。

很明显就是O(1)复杂度(这里忽略系统开根的复杂度),求出Z形侧过来的三角形的行数

然后O(1)复杂度(又一次忽略系统乘法的复杂度),算出结果。

以下是公式以及简要的解释

已知数据是第个。

明显Z形画出来的三角,从左上到右下的行数是从1开始公差为1的等差数列。所以利用求和公式,设行数的话则有:

因此我们 设使得

根据建立起的函数的递增性,可知

所以通过求根公式求出然后向上取整就可以在O(1)的时间复杂度求出行数了。

Which is

接下来,还要求出所在当行的具体位置,这个就很容易了,只需要知道 到那一行总共有多少个:明显

所以要求的也就是那一行的第个。

接下来是一个对于知道行数+第几个的Cantor形式求法:

对于第a行,中所有个体,都有(“/”左边)+(“/”右边)

同时

结果是: <u>(_第几个_ )/(a+1- _第几个_ )</u>

<u>而剩下的则“/”两边相反即好。</u>

以上就是O(1)(其实应该没比二分快多少,相当于让系统做了二分而已)解决此题的详解。既然是数学推算,代码就不贴了,没啥意思。