Description

Sample Input

5 1

2 4 2 2

Sample Output

1

1

0

1

0

Solution

這題可以直接考慮暴力，時(shí)限也給了 3s 那么簡(jiǎn)直是給暴力一條活路啊。

開(kāi)一個(gè)二維數(shù)組 \(CanBeGet[i][j]\) 表示石子個(gè)數(shù)在 \(i\) 時(shí)可以取走 \(j\) 個(gè)

暴力直接 \(O(N^3)\) 暴力把 \(CanBeGet\) 更新(Xor)一下。

最后統(tǒng)計(jì)答案的時(shí)候只要看看當(dāng)前狀態(tài)轉(zhuǎn)移出去的是否有必輸狀態(tài)，有的話當(dāng)前狀態(tài)為勝。

細(xì)節(jié)就是把取一個(gè)也給附上初值。

我們考慮怎么優(yōu)化這個(gè)鬼東西。

我們發(fā)現(xiàn)他要給一段區(qū)間 Xor 。

跟位運(yùn)算有關(guān)系的東西我們都得想想狀壓，但是發(fā)現(xiàn)這題數(shù)據(jù)范圍有 1e5 。。。。

那只能用bitset了。

我們記一個(gè)bitset,假設(shè)叫 \(f[i]\) ,表示當(dāng)前石子個(gè)數(shù)能否取到剩下 \(i\) 。

這樣每次變成一個(gè)新?tīng)顟B(tài)時(shí)就是要把之前的bitset左移一格，表示可以取的石子個(gè)數(shù)沒(méi)變，但是剩下的石子數(shù)量變多了。

同時(shí)我們的這個(gè)bitset還要異或上當(dāng)前這個(gè)石子堆大小可以取得區(qū)間的bitset。

可以取得區(qū)間就是區(qū)間全部為一的區(qū)間，可以用bitset快速做。

最后只要判斷一下后繼是否可以取到負(fù)的局面。

我用 \(ans[i]\) 保存答案。 如果 \(ans[i]==1\) 那么這就是必?cái)〉摹?/p>

所以只要判斷后繼是否有可以取到的，同時(shí)滿足是 \(ans\) 為 \(1\) ，那么當(dāng)前狀態(tài)就是必勝態(tài)，只有當(dāng)后繼沒(méi)有必?cái)B(tài)是才是敗態(tài)。

騙分代碼參考 \(subtask1\)

暴力代碼參考 \(subtask2\)

正解代碼參考 \(subtask3\)

#include<bits/stdc++.h> using namespace std; #define A first #define B secondtypedef pair<int,int> PII; int n,m; const int N=1005; int SG[N],CanBeGet[N][N];namespace subtask1{inline void solve(){for(int i=1;i<=n;++i) printf("%d\n",i&1);} }namespace subtask2{inline void solve(){for(int i=1;i<=m;++i){int a=0,b=0,c=0,d=0;scanf("%d%d%d%d",&a,&b,&c,&d);for(int j=a;j<=b;++j) for(int k=c;k<=d;++k)CanBeGet[j][k]^=1;}for(int i=1;i<=n;++i) CanBeGet[i][1]=1;for(int i=1;i<=n;++i) for(int j=1;j<=min(i,N-5);++j)if(CanBeGet[i][j]){if(i==j) SG[i]=1;else SG[i]|=(!SG[i-j]);}for(int i=1;i<=n;++i) printf("%d\n",SG[i]);} }namespace subtask3{const int M=1e5+5;vector <PII> v[M];bitset<M> f,ans,BASE;inline bitset<M> paint(int l,int r){BASE.set();BASE<<=l;BASE^=BASE<<(r-l+1);return BASE;}inline void solve(){for(int i=1;i<=m;++i){int a=0,b=0,c=0,d=0;scanf("%d%d%d%d",&a,&b,&c,&d);v[a].push_back(make_pair(c,d));v[b+1].push_back(make_pair(c,d));}ans[0]=1;// f[i] 表示從當(dāng)前的石子個(gè)數(shù)可以轉(zhuǎn)移到石子個(gè)數(shù)為i的石子狀態(tài)for(int i=1;i<=n;++i){f<<=1;f[i-1]=1;// 可以取得石子變多了，那么我們能剩下的就變多了，剛好比之前多1，for(int j=0;j<(int)v[i].size();++j) f^=paint(i-v[i][j].B,i-v[i][j].A);// 取出一段為1的區(qū)間if(!(f&ans).count()) ans[i]=1;}for(int i=1;i<=n;++i) printf("%d\n",~ans[i]);} }int main(){scanf("%d%d",&n,&m);if(m==0) return subtask1::solve(),0;if(n<=1000) return subtask2:: solve(),0;else subtask3::solve();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/JCNL666/p/10918103.html

總結(jié)

以上是生活随笔為你收集整理的【题解】弃疗Nim （2019,5.23）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。