題目鏈接

https://www.lydsy.com/JudgeOnline/problem.php?id=2003

題解

考慮搜索。

確定了第一行和第一列，那么就確定了整個矩陣，因此搜索的范圍可以降到399個位置。

首先搜索第一行，顯然每個不是第一行第一列的位置都可以由三個位置唯一確定：$(1,1),(1,i),(j,1)$。由于搜索的是第一行，可以把$(i,j)$這個位置$=0$和$=p?1$都帶入一遍，得到的結果就是$(j,1)$的上下界。如果搜索的過程中發現沖突了那么說明第一行這樣填不行，剪枝。

代碼

#include <cstdio> #include <algorithm>int read() {int x=0,f=1;char ch=getchar();while((ch<'0')||(ch>'9')){if(ch=='-'){f=-f;}ch=getchar();}while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}return x*f; }const int maxn=200;int n,m,p,a[maxn+10][maxn+10],l[maxn+10][maxn+10],r[maxn+10][maxn+10];int f(int x) {return (x&1)?1:-1; }int search(int y) {if(y>m){return 1;}for(a[1][y]=0; a[1][y]<p; ++a[1][y]){int flag=1;for(int i=2; i<=n; ++i){int b=(0-a[1][1]*f(i+y)-a[1][y]*f(i)-a[i][y])*f(y),c=((p-1)-a[1][1]*f(i+y)-a[1][y]*f(i)-a[i][y])*f(y);if(b>c){std::swap(b,c);}l[y][i]=std::max(l[y-1][i],b);r[y][i]=std::min(r[y-1][i],c);if(l[y][i]>r[y][i]){flag=0;break;}}if(flag){if(search(y+1)){return 1;}}}return 0; }int main() {n=read();m=read();p=read();for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){a[i][j]=read();}}for(int i=2; i<=n; ++i){for(int j=2; j<=m; ++j){a[i][j]-=a[i-1][j]+a[i][j-1]+a[i-1][j-1];}}for(int i=2; i<=n; ++i){l[1][i]=0;r[1][i]=p-1;}for(a[1][1]=0; a[1][1]<p; ++a[1][1]){if(search(2)){for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){if(i==1){printf("%d%c",a[i][j],(j==m)?'\n':' ');}else if(j==1){printf("%d%c",l[m][i],(j==m)?'\n':' ');}else{printf("%d%c",a[i][j]+a[1][1]*f(i+j)+a[1][j]*f(i)+l[m][i]*f(j),(j==m)?'\n':' ');}}}return 0;}}return 0; }

轉載于:https://www.cnblogs.com/Canopus-wym/p/10376135.html

總結

以上是生活随笔為你收集整理的BZOJ 2003 [Hnoi2010]Matrix 矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

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