P2575 高手過招

題意：

AKN玩游戲玩累了，于是他開始和同伴下棋了，玩的是跳棋！對手是wwx！這兩位上古神遇在一起下棋，使得棋局變得玄幻莫測，高手過招，必有一贏，他們都將用最佳策略下棋，現在給你一個n*20的棋盤，以及棋盤上有若干個棋子，問誰贏？akn先手！

游戲規則是這樣的：

對于一個棋子，能將它向右移動一格，如果右邊有棋子，則向右跳到第一個空格，如果右邊沒有空格，則不能移動這個棋子，如果所有棋子都不能移動，那么將輸掉這場比賽。

題解：

注意題目意思，題目說的是每個棋子只能向右移動一格，也就是說棋盤的每一行是獨立的，所以我們求出每一行的sg值，然后全部異或起來
對于每一行我們來分析：根據題目意思我們可以得知，一次操作中，棋子是跳到右側第一個空格處，如果右側沒有空格就說明該棋子不能動，所以我們從右側開始，每次找到遇到空格就記錄，然后往左找，找到棋子，就將該棋子跳到記錄的空格上，相當于執行了一步操作，得到新狀態，然后查找新狀態的答案，終狀態就是所有棋子都不能動，輸掉游戲
我們利用mex運算來求sg函數，對于一個狀態x，我們求出x的后繼局面的所有sg值，根據mex運算可以求出sg[x]的值。
狀態x我們可以用二進制來實現，因為每個位置只有存在棋子和不存在棋子兩個情況
這個題很不錯，很考驗思維，解法也很妙
復雜度：狀態數 * 轉移

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2e6+9; 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 j=19;j>=0;j--){if((x>>j)&1){//如果第j位有棋子 if(last0!=-1){//如果右側有0， vis[dfs(x^(1<<j)^(1<<last0))]=1;//棋子移動一步到空格位置 }}else last0=j;}for(int i=0;i<=20;i++){if(vis[i]==0)return sg[x]=i;} } int main() {cin>>t;memset(sg,-1,sizeof(sg));while(t--){cin>>n;int ans=0;for(int i=1;i<=n;i++){int x=0,col,m;cin>>m;while(m--){cin>>col;col--; x|=(1<<col);//最左邊是第零列 }ans^=dfs(x);}if(ans==0)cout<<"NO"<<endl;else cout<<"YES"<<endl; } }

總結

以上是生活随笔為你收集整理的P2575 高手过招的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。