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 zoujing1978 at 2019-09-03 21:36:58 on Problem 2633 and last updated at 2019-09-03 22:31:11
As with all turn-based, two-player, finite, deterministic games, the goal is to categorize the positions as winning or losing
 (a position is losing if no winning position can be reached fromit). 
Dynamic programming ormemoization is often used to achieve sufficient speed, as such a technique normally reduces the amount of work per game position to near constant. 
In this case a game position would be the size of the planet. 
The trouble is that the number of reachable positions is really large, being exponential in the parameter X. 
The crucial observation is that one can calculate with winning and losing size intervals, instead of singular values. 
The key is identifying the points that separate winning from losing intervals. 
This can be done bottom-up, starting with the value 1. 
Given that v is a separation point, the values v / F1, v / F2, ..., v / Fk must be checked to see if they are separation points. 
Once all candidate separation points below X have been investigated,the winning and losing intervals are determined and one only has to see which interval X belongs to.

与所有回合制、两人制、有限性、确定性的游戏一样,目标是将状态划分为赢或输(如果一个状态不能达到胜利的状态,这个状态就是必败的)。动态规划记忆通常用来达到足够的速度,因为这样的技术通常会将每个游戏状态的工作量减少到接近常数。
在这种情况下,游戏的状态将是行星的大小。麻烦的是,可到达的状态的数量非常大,在参数X中呈指数增长(这里的参数X是什么我没看懂)。关键的观察结果是,我们可以用赢和输的大小间隔来计算,而不是用singular值(singular值这是什么意思我不知道)。关键是找出区分胜负区间的点。这可以自底向上完成,从值1开始。
假设给定分离点X,必须检查v / F1, v / F2, ..., v / Fk这些值是不是分离点。
一旦找到了X以下的所有候选分离点,就确定了胜负区间,只需要看X属于哪个区间。

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