专栏首页用户6093955的专栏Sequential Nim(CodeForces - 1382B)【博弈】

Sequential Nim(CodeForces - 1382B)【博弈】

B - Sequential Nim (CodeForces - 1382B)

题目链接

算法

博弈

时间复杂度O(N)

1.这道题乍一看以为用Nim博弈直接套用就可以了,结果通过题意发现并不是。题目中要求取石子时只能从下标最小的那一堆开始取,也就是说一堆一堆的取,不能跳着取。

2.分析完题意,我们知道最后取完最后一堆的人必胜。那么怎么分析谁最后会赢呢?

如果只有一堆的话,很容易得出第一个人获胜。关键在于如何分析多堆的情况。

为了方便,我们将每一堆中首先取的人称为先手,然后取的人是后手,下面我们来进行分类讨论:

  • 如果某一堆只有1个石子,那么先手只能取这一个石子。如果还有剩余的石堆,那么此先手在下一堆中将成为后手(因为两个人是轮流取的);如果没有剩余的石堆,那么此先手获胜。
  • 如果某一堆中有若干个石子(超过1个),为了最优,先手有两种取法,要么全取完,要么取走大部分,只剩余一个。前者会使得先手在下一堆中充当后手,后者会使先手在下一堆中充当先手。当然如果没有下一堆了,取完即可,这时先手赢。否则还要继续判断。

分类讨论后发现,一共就上面两大类情况。那么该怎么做呢?这里是题目的一个难点。

对于先手,当该石堆中石子个数超过1并且还有其他的石堆时,他可以根据实际情况选择在下一堆中成为先手还是后手。但是当石堆中石子个数为1时他别无选择,只能是在下一堆中成为后手。所以说石子个数为1的石堆为转折点。

既然当某石堆石子个数大于1时先手可以任意选择在下一堆中他的身份,所以如果还有其他石堆,那么该先手必胜。(因为他掌握着主动权,所以他完全可以根据剩余的石堆数来选择接下来的身份,至于怎么选我们不用考虑)

当石子个数等于1时,先手变成后手,后手变成先手。

3.总结一下,我们只需从头判断每一堆的石子的个数,若个数为1,则继续循环,直到循环完。如果循环完了,说明都为1,这时只需判断石堆个数即可;若出现个数不为1的,则先手必胜,跳出循环即可。

C++代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N];
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        int first = 1, second = 0;
        bool flag = false;
        for(int i = 0; i < n; i++)
        {
            if(a[i] == 1)
            {
                if(first)
                {
                    first = 0;
                    second = 1;
                }
                else
                {
                    first = 1;
                    second = 0;
                }
            }
            else
            {
                if(first)
                    puts("First");
                else
                    puts("Second");
                flag = true;
                break;
            }
        }
        if(!flag)
        {
            if(n % 2 == 1) puts("First");
            else puts("Second");
        }

    }
}

思路来源(注意这里“先手”的定义与思路来源连接里的“先手"定义不同)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-4544 湫湫系列故事——消灭兔子 (贪心+优先队列)

    将兔子的血量从大到小排列,将箭的属性写在类中(结构体也成),排序按照伤害从大到小排列,若有相等的则按价格从小到大排。

    _DIY
  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • cf1090 I.Minimal Product(贪心)

    给出长度为\(n\)的序列\(a\),序列中的元素取值为\([-2e9, 2e9]\)

    attack
  • 【DB笔试面试495】Oracle中哪个包可以获取环境变量的值?

    可以通过DBMS_SYSTEM.GET_ENV来获取环境变量的当前生效值,示例如下所示:

    小麦苗DBA宝典
  • Linux命令(6)——sort命令

    以行为单位对文本文件的内容进行排序,将结果显示在标准输出,比较原则是从行首字符向后,依次按ASCII码值进行比较,最后按升序输出。如果file参数指定多个文件,...

    Dabelv
  • 蒙特卡洛随机方法/模拟(Monte Carlo method)

    蒙特卡洛随机方法,即统计模拟方法,是一类以概率统计理论为指导的数值计算方法。本质上是用部分估计整体,采样越多,则越近似最优解。

    生信编程日常
  • SEO网站优化,一直原创,为什么排名上不去?

    即使你在SEO行业,有着几年的工作经验,你偶尔也会有这样的疑问,我长期的坚持写原创高质量内容,但有的时候,针对某些网站,它的排名就是上去。

    蝙蝠侠IT
  • Linux 命令(86)—— head 命令

    可以指定多个文件 FILE,以空格分隔,此种情况下,输出的内容前会列出所属文件名。如果未给定 FILE 或者 FILE 是 -,则从标准输入读取。

    Dabelv
  • 初识 Python 网络请求库 urllib

    urllib 是 Python 自带的网络请求标准库,包含了多个处理 URL 功能的模块。

    keinYe

扫码关注云+社区

领取腾讯云代金券