| 等 级 | |
| 排 名 | 53 |
| 经 验 | 11534 |
| 参赛次数 | 5 |
| 文章发表 | 56 |
| 年 龄 | 24 |
| 在职情况 | 在职 |
| 学 校 | 四川工商学院 |
| 专 业 | 通信工程 |
自我简介：
C语言 蓝桥杯 ACM 新人 欢迎大佬 前来指导 交流 本人 博客https://fivecc.blog.csdn.net/
TA的其他文章
你可能喜欢
C语言程序设计教程（第三版）课后习题6.5 （C语言代码）浏览：770 |
点我有惊喜！你懂得！浏览：4145 |
点我有惊喜！你懂得！浏览：1392 |
C语言程序设计教程（第三版）课后习题8.6 （C语言代码）浏览：564 |
十->二进制转换 （C语言代码）浏览：1330 |
解题思路:
这是一道经典的阶梯Nim博弈问题，想解决这道题 首先要知道Nim博弈（如果知道就直接看代码吧）， Nim博弈就是说，给你几堆小石子 ，让两个玩家分别在这几堆小石子中取出石子（可以将某堆石子全部取出 也可以在某堆中只取一个小石子，当然是不可能不取的，不然还玩撒）。谁取到最后 ，没有石子取就输了。
比如 有 3 堆石子 ，每堆分别为 2 3 4个小石子，如下图所示
玩游戏都想赢 ，所以 如何取尤为重要，方案有很多，想快速知道如果我方先手 是赢 还是输，直接就用Nim 研究过的成果。
Nim 的做法 就是 将 2 3 4 都转化为2进制再 异或 得出结果，如果结果是非0 那么先手必定赢 如果结果为0 那么先手必输（前提，玩游戏的都想赢 且都很聪明）
可以看到异或后得到的结果是非0 则先手必胜， 先手遇到如此局面肯定会想办法 将它 变成0 这里先手在个数为4的一堆中取出3个。这堆就变成1个 整个局面的结果 就变成0，那么后手进行操作的话，无论操作 哪一堆，在哪堆中拿多少个石子，看看下图对不对。 肯定会破坏这种局面，让结果变为非0，比如后手在为3堆一堆取走3，
比如后手在为3堆一堆取走3，如下图
现在又到该先手取石子了，这个时候先手肯定要把 2个石子的一堆取出1个来，还剩1个，如图所示
现在又轮到 后手去取石子，现在一眼就可以看出 先手必赢了吧， 后手根据规则 只能拿走一个，然后轮到先手 拿了最后一个，后手就没得办法取 ，游戏就结束了。
现在回过头来 看阶梯Nim博弈问题。 只需要将 阶梯Nim博弈问题转换为Nim博弈问题即可，做如下转换，每两个和尚之间看做一堆，比如 和尚分别站 1 3 5 8 那么可以转换为3堆，分别为 1 1 2，再取异或 就可以知道 先手是否必赢，具体实现可以看代码。（注意； 如果移动了一个小和尚 除了边界 ，会影响相邻两堆的情况，看代码注释）
注意事项:
参考代码:
#include<iostream>
#define N 102
using namespace std;
int main(){
int a[N],b[N];
int n = 0,i,j,k,sum = 0;
while(cin>>a[n])n++;//存储又有多少个小和尚
for(i=1; i<n; i++)b[i-1] = a[i] - a[i-1] - 1;// 进行Nim博弈的转换
for(i=0; i<n-1; i+=2) sum ^= b[i];//进行异或
if(sum==0)cout<<-1<<endl;//若开始局面为0 则必输
else//若非0 则必赢，因此 需要找到第一步 将局面变为0 的步骤
{
for(i=0; i<n-1; ++i)//枚举移动第i堆 使得剩下的局面异或等于0，
for(j=1; a[i]+j<a[i+1]; ++j) {//枚举可以移动的步数 保证 前项移动j 步后 不会超过后项
b[i] -= j;//拿走 j个 ，这里代表 前一个向上移动j步
if(i!=0)b[i-1] += j;//它的后一堆b[i]向取走了j个，那莫前一堆 b[i-1] 则要增加j个 第一堆除外
sum = 0;
for(k=0; k<n-1; k+=2) sum ^= b[k];//重新计算局面，
if(sum==0) {cout<<a[i]<<" "<<a[i]+j<<endl; break;}//若变成0 则后手必败，先手必赢。跳出即可；
b[i] += j;//回溯 这不是必赢的操作
if(i!=0) b[i-1] -= j;
}
}
return 0;
}0.0分
19 人评分
评论区
你这就不能格式化化吗。。这可读性真的烂
for(i=0; i<n-1; i+=2) sum ^= b[i];//进行异或 for(k=0; k<n-1; k+=2) sum ^= b[k];//重新计算局面 这两行怎么多个第偶数个进行异或 ？不是所有的进行异或吗 怎么这样写是对的
- «
- 1
- »
精彩推荐
WU-整除问题 （C++代码）浏览：648 |
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：701 |
C语言程序设计教程（第三版）课后习题5.4 （C语言代码）浏览：821 |
C语言程序设计教程（第三版）课后习题10.2 （C语言代码）浏览：1483 |
GC的苦恼 （C语言代码）浏览：672 |
排序算法（选择，插入，冒泡）浏览：876 |
半数集问题 （C语言代码）浏览：969 |
C语言程序设计教程（第三版）课后习题6.5 （C语言代码）浏览：714 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）浏览：859 |
母牛的故事 （C语言代码）浏览：511 |
dotcpp0632515 2022-12-19 20:37:49 |
#include<stdio.h> #define N 102 int main() { int a[N],b[N]; int n=0,i,j,k,sum=0; char c; while(1) { scanf("%d%c",&a[n++],&c); if(c==' ') break; }//h和尚个数 for(i=0;i<n-1;i++) { b[i]=a[i+1]-a[i]-1;//进行nim博弈的转换 } b[n-1]=0; for(i=0;i<n-1;i+=2) sum^=b[i]; //进行异或 if(sum==0) printf("-1 "); else//若非零。则必赢，因此，需要找到第一步，将局面变为零 { for(i=0;i<n;i++)//枚举移动第i堆，使得剩下局面=0； { for(j=1;j<=b[i];j++)//枚举可移动步数，保证前一项动J步后不回超过后一项 { b[i]-=j;//拿走j个， if(i>0) b[i-1]+=j;//他的后一堆拿走j个，则前一堆吧b[i-1]j加j,第一堆除外 sum=0; for(k=0;k<n-1;k+=2) { sum^=b[k]; } if(sum==0) { printf("%d %d",a[i],a[i]+j); return 0; } b[i]+=j;//回溯，这不是必赢操作 if(i>0) b[i-1]-=j; } } } return 0; }