记录编号	600151	评测结果	AAAAAAAATAAAAAAATTTT
题目名称	[NOIP 2009]靶形数独	最终得分	75
用户昵称	ChenBp	是否通过	未通过
代码语言	C++	运行时间	12.242 s
提交时间	2025-04-17 06:28:17	内存使用	3.36 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x*f;
}
void write(int x) {
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
	return;
}
constexpr int f[9][9]={
	{6,6,6,6,6, 6,6,6,6},
	{6,7,7,7,7, 7,7,7,6},
	{6,7,8,8,8, 8,8,7,6},
	{6,7,8,9,9, 9,8,7,6},
	{6,7,8,9,10,9,8,7,6},
	{6,7,8,9,9, 9,8,7,6},
	{6,7,8,8,8, 8,8,7,6},
	{6,7,7,7,7, 7,7,7,6},
	{6,6,6,6,6, 6,6,6,6}
};
int g[9][9];
int h[9],l[9],gr[3][3];
int num=0;
struct node {
	short x,y,sum=0,w;
} s[100];
bool cmp(node x,node y) {
	return x.sum<y.sum;
}
int lowbit(int x) {
	return x&(-x);
}
ll ans=-1;
void dfs(ll t) {
	if(t==num+1) {
		ll now=0;
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				now+=f[i][j]*g[i][j];
			}
		}
		ans=max(ans,now);
		return;
	}
	int w=s[t].w;
	int x=s[t].x,y=s[t].y;
	while(w) {
		int k=log2(lowbit(w));
		if((((h[x]>>k)&1)+((l[y]>>k)&1)+((gr[x/3][y/3]>>k)&1))==0) {
			h[x]|=1<<k;
			l[y]|=1<<k;
			gr[x/3][y/3]|=1<<k;
			g[x][y]=k;
			dfs(t+1);
			g[x][y]=0;
			h[x]&=(~(1<<k));
			l[y]&=(~(1<<k));
			gr[x/3][y/3]&=(~(1<<k));
		}
		w-=lowbit(w);
	}
}
int main() {
	for(int i=0; i<9; i++) {
		for(int j=0; j<9; j++) {
			g[i][j]=read();
			if(g[i][j]==0) continue;
			h[i]|=1<<g[i][j];
			l[j]|=1<<g[i][j];
			gr[i/3][j/3]|=1<<g[i][j];
		}
	}

//    for(int i=0;i<9;i++){while(h[i]){cout<<log2(bitset(h[i]))<<" ";h[i]-=bitset(h[i]);}cout<<endl;}
//    for(int i=0;i<9;i++){while(l[i]){cout<<log2(bitset(l[i]))<<" ";l[i]-=bitset(l[i]);}cout<<endl;}
//    for(int i=0;i<3;i++){for(int j=0;j<3;j++){while(gr[i][j]){cout<<log2(bitset(gr[i][j]))<<" ";gr[i][j]-=bitset(gr[i][j]);}cout<<endl;}}

	for(int i=0; i<9; i++) {
		for(int j=0; j<9; j++) {
			if(g[i][j]!=0) continue;
			num++;
			s[num].x=i;
			s[num].y=j;
			for(int k=1; k<=9; k++) {
				if((((h[i]>>k)&1)+((l[j]>>k)&1)+((gr[i/3][j/3]>>k)&1))==0) {
					s[num].sum++;
					s[num].w|=1<<k;
				}
			}
		}
	}
	sort(s+1,s+1+num,cmp);
//    for(int i=1;i<=num;i++){cout<<s[i].x<<" "<<s[i].y<<" "<<s[i].sum<<"\n";
	dfs(1);
	write(ans);
	return 0;
}