※ 引述《pinglunliao (王者：一条孤独的不归路)》之铭言： : 原题目：　http://www.cs.ualberta.ca/~contest/club/020208/00209.html : 某个参考解答　http://www.cs.ualberta.ca/~contest/club/020208/00209code1.html : 我对这个参考解答的底下部分有疑问：「他是怎麽推出公式来的？」 : p[psize].n = pset[i]; : x = sqrt(2*pset[i])-1; : while(1){ : if(x*(x-1)/2 < pset[i] && pset[i] <= x*(x+1)/2) break; : x++; : } : p[psize].x = x; : p[psize].y = pset[i]-x*(x-1)/2; : p[psize].z = x*(x+1)/2+1 - pset[i]; : 版友们对　Triangular Vertices　有别的解法吗？ 我的想法是把点看成这样： 　Ｙ 　↑ 　︴ 　｜＼｜＼｜＼｜＼｜ ４15－20－26－33－41－ 　｜＼｜＼｜＼｜＼｜＼ ３10－14－19－25－32－ 　｜＼｜＼｜＼｜＼｜＼ ２６－９－13－18－24－ 　｜＼｜＼｜＼｜＼｜＼ １３－５－８－12－17－ 　｜＼｜＼｜＼｜＼｜＼ ０１－２－４－７－11－…→Ｘ 　０　１　２　３　４ 然後去找出每个点对应的x,y座标 检查两点是否连线就变成它们的x,y座标X相同或Y相同或X+Y相同 距离则为(X相同时)Y的差或(Y相同时)X的差或(X+Y相同时)X的差 然後因为题目给的点顺序不一定 所以要每对之间都检查 (点最多才6个 所以这一定OK) 确定边之後再检查是否能连成三角形/平行四边形/六边形 距离是否相等 等等 (可以就直接做成一个小graph来检查) 上面的式子 里面的x就是我的X+Y+1 里面的y就是我的Y+1 里面的z就是我的X ＿ 那个√2n-1只是要找出的X+Y+1的值的下界估计而已 (这样while只需要跑个几圈就找到x了 如果不先估计 while可能会跑非常多圈) -- 就我的印象中 92年全国高中资讯能力竞赛决赛的题目之一和这题非常像 当时的题目是直接把图形给成上面那样 (只差没有画出座标轴而已) 然後也没有限定距离要相等 只要求有边连得起来即可 -- **** 说: 不要期望一个精神力差不多已经见底的人阿Orz --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 192.192.197.115