usrbin吧 关注:310贴子:45,934
  • 9回复贴,共1

【水】一道题

只看楼主收藏回复

n堆石子,每堆有a[i]个,两人轮流从两端(最左或最右)取石子,没的取的算输,问先手赢还是输? (1<=a[i]<=10^5)
(我知道这是老题了...dagara...博弈神马的最讨厌了没记起怎么做)


1楼2010-12-27 21:31回复
    回复:2楼
    可以从最左或最右的一堆里取若干个石子。两人轮流一直取,最后被取光没得取的那个就是输的


    3楼2010-12-27 23:50
    回复
      2025-10-21 03:15:07
      广告
      不感兴趣
      开通SVIP免广告
      学术贴照例加精


      5楼2010-12-27 23:56
      回复
        回复:4楼
        勘误:
        2)"如果他们竖直方向位置大小关系=x和y大小关系(>,=,<)”=>"a和b"的大小关系
        3)令"令a=y,b=x"=>"令y=a,x=b"


        6楼2010-12-28 00:12
        回复
          3)和2)是递归关系?没看懂..
          c1,c2是↑↓怎么比较大小关系的?
          还有这个P位置的判断是怎么得出的完全


          7楼2010-12-28 11:41
          回复
            8楼2010-12-28 11:49
            回复
              回复:7楼
              3)的情况可以划归到2)(令y=a,x=b)
              后面那个举个例子吧:
              比如S=222345555
              此时a=2,n=3,x=3,b=5,m=4,y=4,S'=空串.d1=1,c1=↑,d2=2,c2=↓,下面这个表:
              ↑↓
              ↓↑
              (d1,c1)在这个表的第1列(用"*"标注),(d2,c2)在这个表第2列(用"&"标注):
              ↑* ↓
              ↓   ↑&
              因此(d1,c1)竖直坐标>(d2,c2),又a<b,两者大小不一致,因此这是个N状态
              证明这儿空白太小写不下你去找找论文吧
              


              9楼2010-12-28 11:53
              回复
                举个例子:
                例如:S=5556784444,此时a=5,n=3,x=6,b=4,m=3,y=8,c1=1,d1=↑,c2=2,d2=↓,|a-b|<=1。(c1,d1),(c2,d2)分别填入下表里的第1,2列(用*和&标注):
                ↑* ↓
                ↓   ↑*
                因此(c1,d1)坐标>(c2,d2),又a>b,因此这是个P状态
                证明太长就不写了,LZ找找论文吧


                10楼2010-12-28 12:26
                回复
                  2025-10-21 03:09:07
                  广告
                  不感兴趣
                  开通SVIP免广告
                  回复:8楼
                  谢了~
                  回复:10楼
                  嗯。orz


                  11楼2010-12-28 14:04
                  回复