洛谷P3164 和諧矩陣

2022-09-23 02:42:08 字數 1164 閱讀 8244

給出 \(n,m\),輸出任意一個 \(n\times m\) 的 01 矩陣滿足矩陣中任意元素與其四周元素的權值和均為偶數。

\(n,m\leq 40\)。

挺顯然的高斯消元。太久沒敲了,就當做練練手吧。

對於矩陣中的一個點 \((x,y)\),就是要我們求出一種方案滿足 \(a[x][y]\ \operatorname\ a[x-1][y]\ \operatorname\ a[x+1][y]\ \operatorname\ a[x][y-1]\ \operatorname\ a[x][y+1]=0\)。

那麼我們對於每一個點 \((x,y)\),我們可以列出一個形如 \(a_1x_1\ \operatorname\ a_2x_2\ \operatorname\ ...\ \operatorname\ a_x_=0\) 的方程。其中如果一個點與 \((x,y)\) 相鄰或就是 \((x,y)\),那麼該位置的係數 \(a=1\),否則 \(a=0\)。

然後就是高斯消元板子了。

時間複雜度 \(o\)

\(\large\)

\((nm)^3\)

\(\large\)。顯然跑不過。

我們發現,題目要求是 01 矩陣,每一位的取值就只有 0 或 1。所以可以用 \(\operatorname\) 搞搞就可以了。時間複雜度 \(o(\frac)\)。

#include #include #include #include using namespace std;

const int n=50;

const int dx=,dy=;

int n,m,id[n][n],ans[n*n];

bitseta[n*n];

void gauss()

if (!a[i][i]) ans[i]=1;

for (int j=i+1;j<=n*m;j++)

if (a[j][i]) a[j]^=a[i];

} for (int i=n*m;i>=1;i--)

for (int j=i+1;j<=n*m;j++)

ans[i]^=(ans[j]*a[i][j]);

}int main()

} gauss();

for (int i=1;i<=n*m;i++)

return 0;

}

洛谷p1009

用高精度計算出s 1 2 3 n n 50 其中 表示階乘,例如 5 5 4 3 2 1。 一個正整數n。 一個正整數s,表示計算結果。 輸...

洛谷p1101

給一n times nn n的字母方陣,內可能蘊含多個 yizhong 單詞。單詞在方陣中是沿著同一方向連續擺放的。擺放可沿著 88 個方向...

洛谷p1044

棧是計算機中經典的資料結構,簡單的說,棧就是限制在一端進行插入刪除操作的線性表。 棧有兩種最重要的操作,即 pop 從棧頂彈出一個元素 和...