首页 > 其他分享 >poj 2311 Cutting Game (sg函数)

poj 2311 Cutting Game (sg函数)

时间:2023-07-18 19:38:03浏览次数:46  
标签:函数 int 2311 Game Cutting MAXN 后继 sg mex


小记:这题是对sg函数的初步理解。

对于sg函数只要 g[x] == 0,则此时为必败态。

x作为后继,我们就要对所有的后继进行标记,然后mex之。

因为每次只能切一刀,所以切完之后,会有两块方格,而对每一块方格进行游戏又会有一个sg函数值,

所以根据sg函数的性质,它这一刀所代表的后继,即为这两块方格的sg函数值的异或值(即为x)。

然后根据后继mex之。

mex的到的值即为此态的sg函数值,返回即可。

根据sg函数值判断必败必胜态。

 

代码:

 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 210

int dp[MAXN][MAXN];

int sg(int n,int m){
    if(dp[n][m] != -1)return dp[n][m];
    bool g[MAXN]={0};
    for(int i = 2; i <= n/2; i++){
        g[sg(i,m) ^ sg(n - i,m)] = 1;
    }
    for(int j = 2; j <= m/2; j++){
        g[sg(n,j) ^ sg(n,m - j)] = 1;
    }
    for(int i = 0; ; i++){
        if(g[i]==0)return dp[n][m] = i;
    }

}

int main()
{
    memset(dp,-1,sizeof(dp));

    int n,m;
    while(~scanf("%d%d",&n,&m)){
        if(sg(n,m)>0){
            printf("WIN\n");
        }
        else printf("LOSE\n");
    }
    return 0;
}

 

标签:函数,int,2311,Game,Cutting,MAXN,后继,sg,mex
From: https://blog.51cto.com/u_16192154/6767443

相关文章

  • Python pygame实现中国象棋单机版源码
    今天给大家带来的是关于Python实战的相关知识,文章围绕着用Pythonpygame实现中国象棋单机游戏版展开,文中有非常详细的代码示例,需要的朋友可以参考下#-*-coding:utf-8-*-"""CreatedonSunJun1315:41:562021@author:Administrator"""importpygamefrompygame.local......
  • Cutting Game
    题目来源:POJ2311CuttingGame题意给定一张\(N*M\)的矩形网格纸,两名玩家轮流行动。在每一次行动中,可以任选一张矩形网格纸,沿着某一行或者某一列的格线,把它剪成两部分。首先剪出\(1*1\)的玩家获胜。两名玩家都采取最优策略行动,求先手是否必胜。\[1\leqslantN,M\leqslant......
  • LWC 51:682. Baseball Game
    LWC51:682.BaseballGame传送门:682.BaseballGameProblem:You’renowabaseballgamepointrecorder.Givenalistofstrings,eachstringcanbeoneofthe4followingtypes:Integer(oneround’sscore):Directlyrepresentsthenumberofpointsyougetinthis......
  • LWC 50:679. 24 Game
    LWC50:679.24Game传送门:679.24GameProblem:Youhave4cardseachcontaininganumberfrom1to9.Youneedtojudgewhethertheycouldoperatedthrough*,/,+,-,(,)togetthevalueof24.Example1:Input:[4,1,8,7]Output:TrueExplanation:(8-4)......
  • CodeChef Cutting Plants难题题解
    STL-CodeChefCuttingPlants题解单调队列哦我要造福后人,因为题解太jb难找了题意:2个操作找一段l-r区间,取其<=最小值的任意高度,记为h将l-r变为h时间复杂度暂时归为n吧思路:(思路应该很容易跟上)最特殊的:L=R,来嘛我每个独自减那为什么会有-1呢涨不回去呗(bi>ai)现在关键在......
  • CF842E Nikita and game 题解
    题意一棵树初始只有一个编号为1的根结点。\(n\)次操作,每次新增一个点作为\(p_i\)的子结点,询问更新后有多少点可以作为树直径的端点。\(n\le3\times10^5\)。题解以下\(dist(x,y)\)表示点\(x\)与点\(y\)在树上的距离。不难发现若干条直径必然叠合于至少一点,任选这......
  • Building a Dice Game using JavaScript Javascript构建一个dice game 项目
    WewillbebuildingaDiceGameProjectusingHTML,CSS,andJavaScript.TheDiceGameisbasedonatwo-player.Bothplayersrollthediceandtheplayerwhogetsthehighestphasevaluewillwinthegame.ImagesofDicePhases: Thelistofdicephasesi......
  • CF1411G No Game No Life
    猜它是一个multi-sg,只用算出每个位置的sg值。不过注意到这是一个图,你要求mex肯定不会太大,毛咕咕一下不会超过\(\sqrt{m}\)。并且根据均摊,你求mex的复杂度是\(O(m)\)的。接下来相当于你有一个数\(v\)每次选一个点异或上它的sg值,求最后是\(0\)的概率。枚举这个过程......
  • xss漏洞攻击复现(xssgame靶场通关)
     这篇文章简单的介绍下xssgame的通关方法,从名字可以看出,xssgame就是针对xss攻击进行专门的漏洞复现,由易到难。 链接:https://pan.baidu.com/s/1F9I7iBdu7MPLLvegM5kAQg 提取码:469c 这是xssgame的安装包,将它放到phpstudy/WWW文件夹下访问即可 第一关 这一关没有任......
  • 关于游戏开发及Gamejam的一些尝试
    阅读笔记《01游戏设计》01游戏开发的意义文创意义1.时刻牢记,我们设计的终究是一款游戏,它首先需要对玩家的体验负责。所谓教育意义和弘扬文化只是在游戏体验完善的基础上,和题材风格叠加产生的效果。一开始就抱着“使命感”去设计游戏,反而不会制作出优秀的作品,只有优秀的游戏......