笔记

Luogu P1784 数独

这题一个比较基础的 dfs

#include<bits/stdc++.h>

using namespace std;

const int N = 20,n = 9;
int a[N][N],ge[n+1][n+1] = {
	{},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9}
	};
bool h[N][N],l[N][N],w[N][N];
void dfs(int x,int y){
	if(x > n || y > n){
		//printf("x=%d y=%d\n",x,y);
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
		//printf("\n");
		exit(0);
	}
	int nx = x,ny = y+1;
	if(ny > n){
		nx++;
		ny = 1;
	}
	if(a[x][y] == 0){
		for(int i = 1;i <= 9;i++){
			if(!h[x][i] && !l[y][i] && !w[ge[x][y]][i]){
				h[x][i] = true;
				l[y][i] = true;
				w[ge[x][y]][i] = true;
				a[x][y] = i;

				dfs(nx,ny);

				h[x][i] = false;
				l[y][i] = false;
				w[ge[x][y]][i] = false;
				a[x][y] = 0;
			}
		}
	} else{
		dfs(nx,ny);
	}
}

int main(){
	//freopen("1.in","r",stdin);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			scanf("%d",&a[i][j]);
			h[i][a[i][j]] = true;
			l[j][a[i][j]] = true;
			w[ge[i][j]][a[i][j]] = true;
		}
	}
	dfs(1,1);
	return 0;
}

Luogu P1074 [NOIP 2009 提高组] 靶形数独

上一题的加强版，不过限制比上一题多很多，要想通过可以看看这篇题解（调了一天，还问了老师）

#include<bits/stdc++.h>
#define PII pair<int,int>
#define one first
#define two second

using namespace std;

const int N = 20,n = 9;
int a[N][N],ge[n+1][n+1] = {
	{},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,1,1,1,2,2,2,3,3,3},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,4,4,4,5,5,5,6,6,6},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9},
	{0,7,7,7,8,8,8,9,9,9}
};
int fen[n+1][n+1] = {
	{},
	{0,6,6,6,6,6,6,6,6,6},
	{0,6,7,7,7,7,7,7,7,6},
	{0,6,7,8,8,8,8,8,7,6},
	{0,6,7,8,9,9,9,8,7,6},
	{0,6,7,8,9,10,9,8,7,6},
	{0,6,7,8,9,9,9,8,7,6},
	{0,6,7,8,8,8,8,8,7,6},
	{0,6,7,7,7,7,7,7,7,6},
	{0,6,6,6,6,6,6,6,6,6}
};
int ans = -1,m;
bool h[N][N],l[N][N],w[N][N],vis[N][N];
PII z[N*N];
void dfs(int now){
	if(now > m){
		int sum = 0;
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				sum += (a[i][j]*fen[i][j]);
			}
		}
		ans = max(ans,sum);
		return;
	}
	int y = z[now].two,x = z[now].one;
	for(int i = 1;i <= 9;i++){
		if(!h[x][i] && !l[y][i] && !w[ge[x][y]][i]){
			h[x][i] = true;
			l[y][i] = true;
			w[ge[x][y]][i] = true;
			a[x][y] = i;

			dfs(now+1);

			h[x][i] = false;
			l[y][i] = false;
			w[ge[x][y]][i] = false;
			a[x][y] = 0;
		}
	}
}
int r[N],c[N],b[N];
PII tmp[N*N];

int main(){
	//freopen("1.in","r",stdin);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			scanf("%d",&a[i][j]);
			h[i][a[i][j]] = true;
			l[j][a[i][j]] = true;
			w[ge[i][j]][a[i][j]] = true;
			if(a[i][j] == 0){
				m++;
				z[m] = {i,j};
			} else{
				c[i]++;
				r[j]++;
				b[ge[i][j]]++;
			}
		}
	}

	for(int j = 1;j <= m;j++){
		int mx = -1,idx = 0;
		for(int i = 1;i <= m;i++){
			int x = z[i].one,y = z[i].two;
			if(vis[x][y]){
				continue;
			}
			int me = r[y]+c[x]+b[ge[x][y]];
			if(me > mx){
				mx = me;
				idx = i;
			}
		}
		int x = z[idx].one,y = z[idx].two;
		vis[x][y] = true;
		c[x]++;
		r[y]++;
		b[ge[x][y]]++;
		tmp[j] = z[idx];
	}
	swap(z,tmp);

	dfs(1);
	printf("%d",ans);
	return 0;
}

Luogu P1434 [SHOI2002] 滑雪

刷个简单题

#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int a[N][N];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int c,r,ans;
int f[N][N];
int dfs(int x,int y){
	if(f[x][y] != 0){
		return f[x][y];
	}
	int now = 0;
	for(int i = 0;i < 4;i++){
		int nx = x+dx[i],ny = y+dy[i];
		if(nx < 1 || ny < 1 || nx > r || ny > c){
			continue;
		}
		if(a[nx][ny] < a[x][y]){
			now = max(now,dfs(nx,ny));
		}
	}
	f[x][y] = now+1;
	ans = max(ans,f[x][y]);
	return f[x][y];
}

int main(){
	scanf("%d%d",&r,&c);
	for(int i = 1;i <= r;i++){
		for(int j = 1;j <= c;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i = 1;i <= r;i++){
		for(int j = 1;j <= c;j++){
			dfs(i,j);
		}
	}
	printf("%d",ans);
	return 0;
}

剩下3道蓝题，写完那个靶形数独之后就再也不想写蓝题了