intellij idea安装 Shell脚本 另类堆栈 typora sqlite qt iis grails paypal 3d tinymce 后台管理系统模板 nodejs教程视频 git视频教程 oracle删除表字段 maya曲线建模 oracle可视化工具 安装python python集合 python平方函数 python自学教材 java中的抽象类 java写入文件 javarandom java重载和重写的区别 java接口的使用 java创建目录 java的多线程 pushstate 怪物猎人ol捏脸数据 忧思华光玉攻略 vbs编程教学 maxtoc4d max电池容量 js图片上传 图片轮播代码 小米手环充电多久 vue路由跳转 原创检测工具 小度音箱app
当前位置: 首页 > 学习教程  > 编程语言

Leetcode刷题笔记 1025. 除数博弈

2020/7/24 9:29:04 文章标签:

1025. 除数博弈


时间:2020年7月24日
知识点:找规律
题目链接:https://leetcode-cn.com/problems/divisor-game/

题目
爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。

最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:

  1. 选出任一 x,满足 0 < x < N 且 N % x == 0 。
  2. 用 N - x 替换黑板上的数字 N 。

如果玩家无法执行这些操作,就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两个玩家都以最佳状态参与游戏

示例1
输入
2
输出
true

说明:
爱丽丝选择 1,鲍勃无法进行操作。

示例2
输入
3
输出
false

说明:
爱丽丝选择 1,鲍勃也选择 1,然后爱丽丝无法进行操作。

解法
A代表爱丽丝 B代表鲍勃

  1. 情况一. 当n = 1时,A无法选出x,A败B胜。先选的输
  2. 情况二. 当n = 2时,A先执行,选择x=1,到B执行,变成情况1,B先选,B输。先选的胜
  3. 情况三. 当n = 3时,A先执行,选择x=1,到B执行,变成情况2,先选的胜可知B胜。先选的输
  4. 情况四. 当n = 4时,A先执行,可选择x=1或者x=2,当x=1时,到B选择变成情况3,B先选,B输;当x=2,到B选择变成情况2,B选,B胜,由于最佳状态参与游戏,所以还是A胜

假设:N是偶数,先选的胜,N是奇数,先选的败

证明:

  1. 假设 N≤k 时该结论成立,则N=k+1 时:
  2. 如果k为偶数,则k+1为奇数,x是k+1的因数,只可能是奇数,而奇数减去奇数等于偶数,所以到B的时候都是偶数。而根据我们的猜想假设N≤k的时候偶数的时候,先手必赢,所以A败B胜。
  3. 如果k为奇数,则k+1为偶数,x可以是奇数也可以是偶数,若减去一个奇数,那么k+1−x是一个小于等于k的奇数,此时B选,B输,所以A胜B败

代码

#include <stdio.h>
#include <iostream>
using namespace std;
class Solution {
public:
    bool divisorGame(int N) {
        return N%2==0;
    }
};
int main()
{
    int n = 2;
    Solution s;
    cout<<s.divisorGame(n);
}

今天也是爱zz的一天哦!


本文链接: http://www.dtmao.cc/news_show_50092.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?