问一道L家的题# JobHunting - 待字闺中
l*a
1 楼
http://www.careercup.com/question?id=5116481574535168
为什么不是简单的每个player选可选的最大的数。。。
谢谢！！！
为什么不是简单的每个player选可选的最大的数。。。
谢谢！！！
w*a
2 楼
我理解的是，题目要求是running total，也就是两个人取数字的和超过一个数。
假设池子里还有三个数，1,2,3。要求达到的目标为5，两个玩家。
现在轮到玩家1取数字，如果贪心的取最大数字，则取3，total=3，那么玩家2随后取2
就能胜利。
如果玩家1不取3而是取1，total=1，玩家2无论从剩下的2和3里面取哪个数，他都必输。
假设池子里还有三个数，1,2,3。要求达到的目标为5，两个玩家。
现在轮到玩家1取数字，如果贪心的取最大数字，则取3，total=3，那么玩家2随后取2
就能胜利。
如果玩家1不取3而是取1，total=1，玩家2无论从剩下的2和3里面取哪个数，他都必输。
l*a
3 楼
明白了！非常感谢！！
s*n
4 楼
如果可以重复选数字，那么如果 target % (maxChoosable + 1) == 0 那么玩家2必胜
，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。
如果不可以重复选数字，有一个初步的想法，可以把这个问题转化成一个有2^
maxChoosable 个节点的图，开始在sum = 0的节点上，玩家1和2轮流walk，走到某些节
点时候会获胜。比如1 2 3 4, target = 10，玩家2的winning state是 1 2 3 4，玩家
1没有所以玩家2必胜；如果target = 9 玩家2的winning state是1 2 3 4，玩家1是2 3
4，所以玩家2只要拿到1就胜了，也是必胜；如果target = 8 玩家1多了1 3 4是
winning state，这时玩家1只要取4然后玩家2无论怎么取都会输。
但是感觉这个code实现起来太麻烦了，坐等楼下大神给出答案。
，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。
如果不可以重复选数字，有一个初步的想法，可以把这个问题转化成一个有2^
maxChoosable 个节点的图，开始在sum = 0的节点上，玩家1和2轮流walk，走到某些节
点时候会获胜。比如1 2 3 4, target = 10，玩家2的winning state是 1 2 3 4，玩家
1没有所以玩家2必胜；如果target = 9 玩家2的winning state是1 2 3 4，玩家1是2 3
4，所以玩家2只要拿到1就胜了，也是必胜；如果target = 8 玩家1多了1 3 4是
winning state，这时玩家1只要取4然后玩家2无论怎么取都会输。
但是感觉这个code实现起来太麻烦了，坐等楼下大神给出答案。
l*a
5 楼
嗯 同意你说的那个可选重复数字的那段。
不可选重复数字的我搜到了一个答案自己理解了下， 你看看？
http://blog.csdn.net/lsdtc1225/article/details/40342473
3
【在 s****n 的大作中提到】
: 如果可以重复选数字，那么如果 target % (maxChoosable + 1) == 0 那么玩家2必胜
: ，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
: 的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。
: 如果不可以重复选数字，有一个初步的想法，可以把这个问题转化成一个有2^
: maxChoosable 个节点的图，开始在sum = 0的节点上，玩家1和2轮流walk，走到某些节
: 点时候会获胜。比如1 2 3 4, target = 10，玩家2的winning state是 1 2 3 4，玩家
: 1没有所以玩家2必胜；如果target = 9 玩家2的winning state是1 2 3 4，玩家1是2 3
: 4，所以玩家2只要拿到1就胜了，也是必胜；如果target = 8 玩家1多了1 3 4是
: winning state，这时玩家1只要取4然后玩家2无论怎么取都会输。
: 但是感觉这个code实现起来太麻烦了，坐等楼下大神给出答案。
不可选重复数字的我搜到了一个答案自己理解了下， 你看看？
http://blog.csdn.net/lsdtc1225/article/details/40342473
3
【在 s****n 的大作中提到】
: 如果可以重复选数字，那么如果 target % (maxChoosable + 1) == 0 那么玩家2必胜
: ，如果不是0那么玩家1第一步先拿到target % (maxChoosable + 1)，然后对应玩家2拿
: 的数字来拿 maxChoosable + 1 - player2Num，最后就刚好抢到target。
: 如果不可以重复选数字，有一个初步的想法，可以把这个问题转化成一个有2^
: maxChoosable 个节点的图，开始在sum = 0的节点上，玩家1和2轮流walk，走到某些节
: 点时候会获胜。比如1 2 3 4, target = 10，玩家2的winning state是 1 2 3 4，玩家
: 1没有所以玩家2必胜；如果target = 9 玩家2的winning state是1 2 3 4，玩家1是2 3
: 4，所以玩家2只要拿到1就胜了，也是必胜；如果target = 8 玩家1多了1 3 4是
: winning state，这时玩家1只要取4然后玩家2无论怎么取都会输。
: 但是感觉这个code实现起来太麻烦了，坐等楼下大神给出答案。
w*a
6 楼
不能重复选的话，naive的做法就是求全排列然后一个一个试，O(n!)。
不知道有没有啥剪枝的办法。
不知道有没有啥剪枝的办法。
相关阅读
有没有申Amazon全职的最后糊里糊涂给了intern的offerHR干什么去了最近接触的一个小公司，很有意思请问有没有GE的面经?一言难尽印度人 zz (转载)求工作refer人生第一个onsite就被默拒的感觉太差了对于不报销路费的单位应该什么态度？明天a家onsite刚电面完，要写thank you letter吗？4月1号申请H-1BH1B Pending期间用F1回国签证可以吗？请指教急问：post-completion OPT的开始时间可以在degree completion date前么？Amazon InternWhy I left google (James Whittaker)onsite 快两周了还没消息最近化学类工作市场怎么样careercup 150题 4th edition, 可运行代码哪里下载?如果说需要用online white board是否意味着要考当场coding?Job at NVIDIA