医药电商网站建设,辽宁建设工程信息网投标指定读卡器,北京市朝阳区住房建设网站,暴雪中国P2575 高手过招
题意#xff1a;
AKN玩游戏玩累了#xff0c;于是他开始和同伴下棋了#xff0c;玩的是跳棋#xff01;对手是wwx#xff01;这两位上古神遇在一起下棋#xff0c;使得棋局变得玄幻莫测#xff0c;高手过招#xff0c;必有一赢#xff0c;他们都将用…P2575 高手过招
题意
AKN玩游戏玩累了于是他开始和同伴下棋了玩的是跳棋对手是wwx这两位上古神遇在一起下棋使得棋局变得玄幻莫测高手过招必有一赢他们都将用最佳策略下棋现在给你一个n*20的棋盘以及棋盘上有若干个棋子问谁赢akn先手
游戏规则是这样的
对于一个棋子能将它向右移动一格如果右边有棋子则向右跳到第一个空格如果右边没有空格则不能移动这个棋子如果所有棋子都不能移动那么将输掉这场比赛。
题解
注意题目意思题目说的是每个棋子只能向右移动一格也就是说棋盘的每一行是独立的所以我们求出每一行的sg值然后全部异或起来 对于每一行我们来分析根据题目意思我们可以得知一次操作中棋子是跳到右侧第一个空格处如果右侧没有空格就说明该棋子不能动所以我们从右侧开始每次找到遇到空格就记录然后往左找找到棋子就将该棋子跳到记录的空格上相当于执行了一步操作得到新状态然后查找新状态的答案终状态就是所有棋子都不能动输掉游戏 我们利用mex运算来求sg函数对于一个状态x我们求出x的后继局面的所有sg值根据mex运算可以求出sg[x]的值。 状态x我们可以用二进制来实现因为每个位置只有存在棋子和不存在棋子两个情况 这个题很不错很考验思维解法也很妙 复杂度状态数 * 转移
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn2e69;
int sg[maxn];
int t,n;
int dfs(int x){if(sg[x]!-1)return sg[x];int vis[21];memset(vis,0,sizeof(vis));int last0-1;//最近的一个0的位置 for(int j19;j0;j--){if((xj)1){//如果第j位有棋子 if(last0!-1){//如果右侧有0 vis[dfs(x^(1j)^(1last0))]1;//棋子移动一步到空格位置 }}else last0j;}for(int i0;i20;i){if(vis[i]0)return sg[x]i;}
}
int main()
{cint;memset(sg,-1,sizeof(sg));while(t--){cinn;int ans0;for(int i1;in;i){int x0,col,m;cinm;while(m--){cincol;col--; x|(1col);//最左边是第零列 }ans^dfs(x);}if(ans0)coutNOendl;else coutYESendl; }
}
