Description

我們稱一個由0和1組成的矩陣是和諧的，當且僅當每個元素都有偶數個相鄰的1.一個元素相鄰的元素包括它本身，及他上下左右的4個元素(如果存在)。

給定矩陣的行數和列數，請計算并輸出一個和諧的矩陣。注意：所有元素為0的矩陣是不允許的。

Input

輸入一行，包含兩個空格分隔的整數m和n，分別表示矩陣的行數和列數。

Output

輸出包含m行，每行n個空格分隔整數(0或1)，為所求矩陣。測試數據保證有解。

Sample Input

4 4

Sample Output

0 1 0 0

1 1 1 0

0 0 0 1

1 1 0 1

Data Constraint

1<=m,n<=40

Solution

• 首先，我們可以發現結論①：存在一種方案滿足第一行沿中軸（豎著的）左右對稱。

• 因為左邊滿足條件則右邊也會滿足條件。

• 接著，我們又可以發現結論②：一個方案，只要確定了第一行，接下來的每一個位置都唯一確定。

• 因為我們可以通過上一行位置的1的奇偶性推出下一行。

• 于是我們就可以先枚舉第一行的一半（O(220)），在翻折得到第一行。

• 之后再往后推，看最后一行是否合法即可。找到一種方案就可以直接輸出了。

• 但是判斷是否合法的時候如果是 O(N2) 判斷的話，就可能會超時（主要看人品）。

• 我們迫切要尋求更快的方法迅速推導！

• 機智地考慮位運算。

• 首先，我們先處理出第一行的異或值（即每個數周圍的1的奇偶性），

• 設為 num，并將其壓成一個長整型。

• 那么我們要推出下一行的話，每一個數就要異或周圍的四個數（包括自己）。

• 于是就可以直接異或起來即可：

  num?xor?(num<<1)?xor?(num>>1)?xor?last

• 左移一位、右移一位、自己、上一行（在草稿紙上畫一畫更好理解）。

• 這樣就處理出每個數異或周圍的數之后的值了，還是 O(1) 的！

• 注意不要忘了抹去左移后突出的一位（and 上 2m?1 這個全 1 值即可）。

• 最后判斷最后一行的異或值是否為零即可，零則說明合法，可以直接輸出。

• 這樣判斷的時間復雜度就是 O(N) ，跑得飛快（位運算真強大）！

• 總時間復雜度 O(N?2n2) ，輕松通過本題。

Code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=42,way[5][2]={{1,0},{0,1},{-1,0},{0,-1},{0,0}}; int n,m,h; long long an; int a[N],b[N],f[N][N],ans[N][N]; void dfs(int x) {if(x>h){long long num=0,last=0;memcpy(b,a,sizeof(b));for(int i=(m&1)?h-1:h,k=h;i;i--) b[++k]=a[i];for(int i=1;i<=m;i++){num=num<<1|(b[i-1]^b[i]^b[i+1]);last=last<<1|b[i];}for(int i=2;i<=n;i++){long long s=num;num=last^num^(num<<1&an)^(num>>1);last=s;}if(!num){for(int i=1;i<=m;i++)if(ans[1][i]=b[i])for(int j=0;j<=4;j++) f[1+way[j][0]][i+way[j][1]]++;for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(f[i-1][j]&1){ans[i][j]=1;for(int k=0;k<=4;k++) f[i+way[k][0]][j+way[k][1]]++;}for(int i=1;i<=n;i++,printf("\n"))for(int j=1;j<=m;j++)printf("%d ",ans[i][j]);exit(0);}return;}a[x]=1;dfs(x+1);a[x]=0;dfs(x+1); } int main() {scanf("%d%d",&n,&m);h=(m+1)>>1,an=((long long)1<<m)-1;dfs(1);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3596. 【CQOI2014】和谐矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

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