正文

A Funny Game——打表&&找规律

IP云
IP云V管理员/3 阅读
12/01
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目

n枚硬币排成一个圈。Alice和Bob轮流从中取一枚或两枚硬币。不过，取两枚时，所取的两枚硬币必须是连续的。硬币取走之后留下空格，相隔空格的硬币视为不连续。Alice开始先取，取走最后一枚硬币的获胜。当双方都采取最有策略时，谁会获胜？

分析

不管，先爆搜找规律。 

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const int maxn = ;

int a[maxn], n;

map<ll, int>mp;

bool check()

{

    bool flag = true;

    for(int i = ;i < n;i++)

        if(a[i] == )  flag = false;

    return flag;

}

ll state()

{

    ll ret = ;

    for(int i = ;i < n;i++)  ret = ret * + a[i];

    return ret;

}

int dfs(int cnt)  //必胜返回1，平局返回2，必败返回-1

{

    int& ret = mp[state()];

    if(ret)  return ret;

    if(check())  return ret=-;

    if(cnt >= n)  return ret=;

    bool flag = false;       //能否成平局

    for(int i = ;i < n;i++)

    {

        if(a[i])  continue;

        a[i] = ;

        int tmp = dfs(cnt+);

        a[i] = ;

        if(tmp == -)  return ret=;    //后面存在必败态，先手必胜

        if(tmp == )  flag = true;  //存在平局

        if(a[(i+)%n] == )

        {

            a[i] = ;

            a[(i+)%n] = ;

            int tmp = dfs(cnt+);

            a[i] = ;

            a[(i+)%n] = ;

            if(tmp == -)  return ret=;    //后面存在必败态，先手必胜

            if(tmp == )  flag = true;  //存在平局

        }

    }

    return ret=(flag ?  : -);

}

int main()

{

    for(n=;;n++)

    {

        memset(a, , sizeof(a));

        mp.clear();

        printf("%d %d\n", n, dfs());

    }

}

规律很明显，小于等于2先手赢，否则后手赢。

A Funny Game——打表&&找规律的更多相关文章
  1. hdu 3032 Nim or not Nim? (SG函数博弈+打表找规律)

    Nim or not Nim? Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Sub ...

  2. HDU 5753 Permutation Bo （推导 or 打表找规律）

    Permutation Bo 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5753 Description There are two sequen ...

  3. HDU 4861 Couple doubi （数论 or 打表找规律）

    Couple doubi 题目链接: http://acm.hust.edu.cn/vjudge/contest/121334#problem/D Description DouBiXp has a ...

  4. HDU2149-Good Luck in CET-4 Everybody!(博弈，打表找规律)

    Good Luck in CET-4 Everybody! Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

  5. 【ZOJ】3785 What day is that day? ——浅谈KMP在ACM竞赛中的暴力打表找规律中的应用

    转载请声明出处:http://www.cnblogs.com/kevince/p/3887827.html    ——By Kevince 首先声明一下,这里的规律指的是循环,即找到最小循环周期. 这 ...

  6. HDU 5795 A Simple Nim（SG打表找规律）

    SG打表找规律 HDU 5795 题目连接 #include<iostream> #include<cstdio> #include<cmath> #include ...

  7. hdu_5894_hannnnah_j’s Biological Test(打表找规律)

    题目链接:hdu_5894_hannnnah_j’s Biological Test 题意: 有n个不同的位置围成一个圈,现在要安排m个人坐,每个人至少的间隔为k,问有多少种安排 题解: 先打表找规律 ...

  8. hdu_5795_A Simple Nim(打表找规律的博弈)

    题目链接:hdu_5795_A Simple Nim 题意: 有N堆石子,你可以取每堆的1-m个,也可以将这堆石子分成3堆,问你先手输还是赢 题解: 打表找规律可得: sg[0]=0 当x=8k+7时 ...

  9. hdu_5793_A Boring Question(打表找规律)

    题目链接:hdu_5793_A Boring Question 题意: 自己看吧,说不清楚了. 题解: 打表找规律 #include<cstdio> typedef long long l ...

  10. hdu 3032 Nim or not Nim? （sg函数打表找规律）

    题意:有N堆石子,每堆有s[i]个,Alice和Bob两人轮流取石子,可以从一堆中取任意多的石子,也可以把一堆石子分成两小堆 Alice先取,问谁能获胜 思路:首先观察这道题的数据范围  1 ≤ N ...

随机推荐
  1. ES6中的关键字 - let

    let关键字 1.let关键字声明的变量仅仅在自己的块级作用域内起作用,出了块级作用域就不起作用了: var arr2 = []; for (let index = 0; index < 10; ...

  2. [IOT] - Raspberry Pi 4 Model B 系统初始化，Docker CE + .Net Core 开发环境配置

    本教程为在 Docker 中配置 .Net Core,如果想在树莓派 Raspbian 系统中配置 .Net Core,请参考:[IOT] - 在树莓派的 Raspbian 系统中安装 .Net Co ...

  3. Linux时间日期类，压缩和解压类

    一.时间日期类 1.data指令 1.基本指令 date 显示当前日期 data +%Y 显示当前年份 data +%m 显示当前月份 data +%d 显示当前天 data +%Y-%m-%d %H ...

  4. FPGA成神之路

    先占个坑,网上写的都太没有体系了,打算写一个从电路到语法,从软件使用到硬件调试,从IP核调用到时序分析的系列帖子,人就是太懒,想把自己这两年踩的坑分享一下,加油,特种兵

  5. HDU校赛 | 2019 Multi-University Training Contest 5

    2019 Multi-University Training Contest 5 http://acm.hdu.edu.cn/contests/contest_show.php?cid=852 100 ...

  6. python 搭建 websocket server 发送 sensor 数据

    搞了几天,顺便把代码贴这里,需要的 python 包: gevent,gevent-websocket,bottle,wiringpi-python 简单说明: - gevent 提供了支持 conc ...

  7. asp.net core mvc 集成miniprofiler

    原文:asp.net core mvc 集成miniprofiler asp.net core mvc 集成miniprofiler 一.环境介绍 二.监控asp.net 页面 三.监控执行的sql语 ...

  8. chrome安装插件

    看了很多的解决办法,也试了很多种,有的有点用,有的只能用一次,最后成功了,在这里总结一下 一.首先下载 很多人下载的都ctx格式的,然后拖进去安装,用了一次就崩溃了,主要还是安装方式不对,一般需要将下 ...

  9. 解决v-html无法理解vue模版的问题-动态获取模版，动态插入app并使用当下app状态数据需求

    很多情况下,我们需要使用动态的html作为某个dom元素的inner html,如果这个内容是标准的html的话,则v-html能够圆满满足需求,而如果内容包含了vue组件,则使用v-html就不能达 ...

  10. Maven中 jar包冲突原理与解决办法

    Maven中jar包冲突是开发过程中比较常见而又令人头疼的问题,我们需要知道 jar包冲突的原理,才能更好的去解决jar包冲突的问题.本文将从jar包冲突的原理和解决两个方面阐述Maven中jar包冲 ...

相关阅读

目录[+]