Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

一个笨办法

Posted by aoxboxcox at 2020-11-05 11:29:45 on Problem 1792
看图,最中心是1个,然后往外第1圈6个,往外第2圈12个,往外第3圈18个……
这样列个方程就能算出每个id对应的六边形在第几圈上: 3n(n+1) >= id-1
并且还能算出它是该圈的第几个: id-1-3(n-1)n

令六边形的边长为2,1号六边形的中心坐标(0,0)
这样往6个方向每走一格六边形中心坐标的偏移量分别是: (-3,√3) (0,2√3) (3,√3) ...
于是可以算出始末两个六边形的中心坐标了

考虑到整张图平移和翻折对结果没有影响,起末点坐标可以做差后再取绝对值
这样起点坐标定在(0,0),终点坐标定在(右)(上)方,于是最近路程会有两大类走法:
先右上x步,再向上y步 (x,y>=0)
先右上x步,再右下y步 (x,y>=0)

根据终点坐标和每个方向走一格的坐标差,不难算出是那类走法以及对应的x,y值
所以最近走法的数量 C(x+y, x),最近路程 x+y

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator