取石子（三）（四）（五）

我就是我 2023-10-11 09:36 1阅读 0赞

[取石子三][Link 1]

题意：

给你n堆石子，你可以从一堆中拿取任意个石子，在拿完之后你还可以（你也可以不做）对你操作过的石子堆再进行一次操作——从中拿取一些石子放到其他有石子数不为0的石子堆上。

题解：

当只有一堆石子的时候那是必胜态N；

两堆石子的时候：如果两堆石子数量一样就是必败态P，因为后手可以跟着前手一样在另一堆石子上面操作，最后一个拿石子的肯定是后手

如果两堆石子数量不一样那就是必胜态N，因为前手可以通过一次操作使两堆石子数量不一样变成一样，就转化成了上面那一种情况

三堆石子的时候也是必胜态，因为前手可以一次操作使它变成两堆石子的第一种情况：

例如：三堆石子数量是x<y<z

我们可以先用z把x补齐到y，然后再把z剩下的石子拿走

如果三堆中有两堆直接相同，那就直接拿走不相同的那一堆就可以了

四堆石子的时候：如果他们两两相同或者都一样的情况下，那么就符合两堆石子的第一种状态，必败态

如果他们都不相同

例如：x<y<z<w

这个时候可以用w将y补齐到z，之后再让w的石子剩下x个就可以了（可能有人会怀疑w可能在某种情况下补齐完y，就刚好等于x，不能再拿石子了。这种情况是不存在的，因为我们这样操作相当与在问你y+w>x+z吗，显然这是成立的，那么你的怀疑也就不攻自破了）

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 using namespace std;
     6 typedef long long ll;
     7 const int maxn=1e2+10;
     8 int v[maxn];
     9 int main()
    10 {
    11     int n;
    12     while(~scanf("%d",&n))
    13     {
    14         if(!n) break;
    15         int q;
    16         memset(v,0,sizeof(v));
    17         for(int i=1;i<=n;++i)
    18         {
    19             scanf("%d",&q);
    20             v[q]++;
    21         }
    22         if(n%2)
    23         {
    24             printf("Win\n");
    25             continue;
    26         }
    27         int flag=0;
    28         for(int i=1;i<=100;++i)
    29             if(v[i]%2)
    30             {
    31                 flag=1;
    32                 break;
    33             }
    34         if(flag) printf("Win\n");
    35         else printf("Lose\n");
    36     }
    37     return 0;
    38 }

[取石子（四）][Link 2]（威佐夫博弈）

[参考链接][Link 3]1

威佐夫博弈问题：

给你两堆石子，你可以在其中一堆中取走任意个，或者在两堆中拿走相同个

结论：

他的失败态是有规律的：从第0个失败态开始(0,0),(1,2),(3,5),(4,7),(6,10),(8,13) （第一个数是第一堆石子剩下的数量，第二个相仿）

它有以下规律：

第i个失败态的两个数的差值为i。  
用a\[i\]表示失败态中的第一个数,b\[i\]表示失败态中的第二个数.(i从0开始)。那么a\[i\]是前面的失败态中没有出现过的最小的整数，b\[i\] = a\[i\]+i;（i >= 0）。  
1.每个数仅包含在一个失败态中。  
2.每个失败态可以转到非失败态。  
3.每个非失败态都可以转到一个失败态。  
每个失败态中两个数的差值 \* 1.618的向下取整就是这个失败态的第一个数。  
给两堆石子，求先手输赢，就可以根据这组数是不是失败态来判断先手是否会赢  
如果还要求假设先手赢，先手第一次怎么取石子，可以分为同时取和在一堆取，主要是取后的石子为失败态。

本题就是模板题，代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<math.h>
     6 using namespace std;
     7 typedef long long ll;
     8 const int maxn=1e2+10;
     9 int main()
    10 {
    11     int a,b;
    12     while(~scanf("%d%d",&a,&b))
    13     {
    14         if(a<b) swap(a,b);
    15         int c=floor((a-b)*(1+sqrt(5))/2);
    16         if(c==b)
    17             printf("0\n");
    18         else printf("1\n");
    19     }
    20     return 0;
    21 }

[取石子（五）][Link 4](斐波那契博弈)

[参考链接][Link 5]1    [参考链接][Link 6]2

题目：

有一堆个数为n的石子，游戏双方轮流取石子，满足：  
1)先手不能在第一次把所有的石子取完；  
2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）

结论：

他的必败态符合斐波那契数，即当石子数量是斐波那契数中的某个时，那么这个时候就是必败态

本题即是模板题，代码：

要注意一点，本题数据是<=2^64,但是斐波那契数没有一个等于2^64，所以这一位不用考虑，开unsigned long long就可以了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1  
     2 
     3 #include<algorithm>
     4 
     5 #include<string.h>
     6 
     7 #include<stdio.h>
     8 
     9 using namespace std;
    10 
    11 unsigned long long A[110];
    12 
    13 int main()
    14 
    15 {
    16 
    17     unsigned long long n;
    18 
    19     A[0]=0,A[1]=1;
    20 
    21     for(int i=2;i<=100;i++)
    22 
    23         A[i]=A[i-1]+A[i-2];
    24 
    25 //    for(int i=2;i<=100;i++)
    26 
    27 //        printf("%d %llu\n",i,A[i]);
    28 
    29     while(~scanf("%llu",&n))
    30 
    31     {
    32 
    33 //        printf("%llu\n",n);
    34 
    35         int p=0;
    36 
    37         for(int i=1;i<=93;i++)
    38 
    39         {
    40 
    41             if(A[i]==n)
    42 
    43             {
    44 
    45                 p=1;
    46 
    47                 break;
    48 
    49             }
    50 
    51         }
    52 
    53         if(p)
    54 
    55             printf("No\n");
    56 
    57         else
    58 
    59             printf("Yes\n");
    60 
    61     }
    62 
    63 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11330502.html

[Link 1]: http://192.168.0.147/problem/137
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[Link 2]: http://192.168.0.147/problem/161
[Link 3]: https://blog.csdn.net/weixin_42172261/article/details/87354895
[Link 4]: http://192.168.0.147/problem/358
[Link 5]: https://blog.csdn.net/acm_cxlove/article/details/7835016
[Link 6]: https://blog.csdn.net/tbl_123/article/details/24033245