![洛谷 P1014 [NOIP 1999 普及组] Cantor 表](http://pic.xiahunao.cn/yaotu/洛谷 P1014 [NOIP 1999 普及组] Cantor 表)
本文由Jzwalliser原创发布在CSDN平台上遵循CC 4.0 BY-NC-SA协议。因此若需转载/引用本文请注明作者并附原文链接不得用于商业用途。违者必究谢谢配合。个人主页blog.csdn.net/jzwalliser题目洛谷 P1014 [NOIP 1999 普及组] Cantor 表P1014 [NOIP 1999 普及组] Cantor 表题目描述现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的我们以 Z 字形给上表的每一项编号。第一项是1 / 1 1/11/1然后是1 / 2 1/21/22 / 1 2/12/13 / 1 3/13/12 / 2 2/22/2……。输入格式输入一个整数N NN1 ≤ N ≤ 10 7 1 \le N \le 10^71≤N≤107。输出格式输出表中的第N NN项。输入输出样例 #1输入 #17输出 #11/4说明/提示对于全部测试数据1 ≤ N ≤ 10 7 1 \le N \le 10^71≤N≤107。2024-11-18 0:30 数据中加入了样例放在不计分的子任务 2 中。想法首先我们可以把整个表翻转个45度让它变成类似“宝塔”的形状接着规律就会好找许多第1行有1个第2行2个第3行3个……以此类推。做个求和不难发现行数n nn、本行结束所有数字个数总和S n S_nSn的关系是S n 1 2 n 2 1 2 n S_n\dfrac12n^2\dfrac12nSn21n221n那么就可以计算出第m mm项所在的行n nnm 1 2 n 2 1 2 n m\dfrac12n^2\dfrac12nm21n221n把n nn看作未知数解一元二次方程就得到n − 1 − 1 8 m 2 n\dfrac{-1\sqrt{-18m}}{2}n2−1−18m不过这里注意算出小数说明这个数字已经到下一行了。例如m 2 m2m2你就能算出来n − 1 1 8 × 2 2 1.561 ⋯ n\dfrac{-1\sqrt{18\times2}}{2}1.561\cdotsn2−118×21.561⋯说明这个数字出现在第2行。因此为了方便表示需要加上向上取整符号最终应该得到n ⌈ − 1 1 8 m 2 ⌉ n\left\lceil\dfrac{-1\sqrt{18m}}{2}\right\rceiln⌈2−118m⌉。这样我们就能算出某一项在第几行了。下一步我们需要计算这一项在当前行的第几个才能精确定位到它。这个更简单我们只需要拿当前位置减去前几行中的数字个数。举个例m 5 m5m5时我们可以通过公式算出来n 3 n3n3。再通过前面的求和公式可以知道第2行填完后一共有S n − 1 3 S_{n-1}3Sn−13个数字。所以说5 − 3 2 5-325−32得到它在第3行的第2个。严谨归纳成公式它在当前列的位置k m − S n − 1 m − 1 2 n 2 1 2 n km-S_{n-1}m-\dfrac12n^2\dfrac12nkm−Sn−1m−21n221n。接着再观察Cantor表注意到每一行中分子x xx和分母y yy相加都等于行号n nn加一即x y n 1 xyn1xyn1这要注意不到就注意力涣散了嗷。最后就是确定分子分母了。由于这个表实在复杂各行从上到下一会儿正着来一会儿反过来呈蛇形排布……所以我们直接把它们统一成分子从左到右递增变成这样最后再判断奇偶性如果发现是奇数行就把分子分母反过来输出就行了。实现通过序号m mm算出所在行号n nn。通过所在行号n nn与序号m mm算出本行所在位置$k$。通过n nn和k kk算出分子、分母之和。接着通过奇偶性得到本行的增减性从而算出分子、分母。最后别忘记输出啊。题解C#includebits/stdc.husingnamespacestd;intmain(){intm;cinm;//输入intnceil((-1sqrt(-18*m))/2);//计算行intkm-n*n/2n/2;//计算在该行中所在位置intxk;//计算分子intyn1-x;//计算分母if(n%2){//奇数行couty/x;}else{//偶数行coutx/y;}return0;}Pythonimportmath mint(input())#输入nmath.ceil((-1(-18*m)**0.5)/2)#计算行kint(m-n**2/2n/2)#计算在该行中所在位置xk#计算分子yn1-x#计算分母ifn%2:#奇数行print(y,x,sep/)else:#偶数行print(x,y,sep/)难度难度★★☆☆☆这道题主要是推公式有点费解。公式推出来之后题目迎刃而解而且代码简洁。结尾你是怎么想的欢迎留言啊我们下期再见(˵¯͒〰¯͒˵)
