题解：P1074 [NOIP2009 提高组] 靶形数独

ridewind2013 · 2025-01-26 07:24:52 · 题解

题目传送门

思路

一道搜索题，建议降绿，如果写一个朴素暴力的话，你就会得到 TLE 的拥抱，所以必须要进行优化。

朴素暴力部分我就不用讲了，很简单，用三个数组标记每行，每列，每宫可以填什么，最后计算得分即可，我重点讲一下优化。

• 优化 1：位运算优化，每次搜索都需要从 1 到 9 挨个看，时间复杂度很高，我们可以用一个数来表示它的状态，1 表示可以填，0 表示不可以填（和状态压缩有异曲同工之妙），给三个标记每行，每列，每宫的数组预处理，表示状态的数就是这三个数组按位与的结果，我们可以用 lowbit 来判断哪个位置上是 1，如果 lowbit 的结果是 2_{}^{k}，那么这里要填的数就是 k，所以我们可以用 p 数组预处理一下。

• 优化 2：每次寻找可能性最小的位置，从那个位置进行搜索，可以预处理 o 数组，o_{i} 表示 i 的二进制中 1 的个数，每个位置有几个 1，就有几种可能性。

用了这两个优化，时间复杂度会减小很多。

接下来要计算得分，通过找规律，我们发现第 i 行第 j 列的得分就是 a_{i,j} \times (6 + \min(\min(i,8-i),\min(j,8-j)))。

最后求出最大得分，输出即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
int a[10][10],r[10],c[10],e[5][5],p[1<<11],ans=-1;
int o[1<<10];
int gs(int i,int j){//计算得分
    return a[i][j]*(6+min(min(i,8-i),min(j,8-j)));
}
void init(){//初始化
    for(int i=0;i<9;i++)r[i]=c[i]=e[i/3][i%3]=(1<<9)-1;
    for(int i=0;i<(1<<9);i++){
        int t=i;
        while(t){
            t&=t-1;
            o[i]++;
        }
    }
    for(int i=0;i<9;i++)p[1<<i]=i+1;
}
void dfs(int cnt,int sum){//搜索
    if(cnt==0){
        ans=max(ans,sum);
    }
    int mi=10,x,y;
    for(int i=0;i<9;i++){//求出可能性最小的位置
        for(int j=0;j<9;j++){
            if(!a[i][j]){
                int t=r[i]&c[j]&e[i/3][j/3];
                if(o[t]<mi){
                    mi=o[t],x=i,y=j;
                }
            }
        }
    }
    int t=r[x]&c[y]&e[x/3][y/3];
    while(t){//位运算优化
        int l=(t&-t);
        t-=l;
        a[x][y]=p[l];
        r[x]-=l,c[y]-=l,e[x/3][y/3]-=l;
        dfs(cnt-1,sum+gs(x,y));
        a[x][y]=0;
        r[x]+=l,c[y]+=l,e[x/3][y/3]+=l;
    }
}
int main(){
    init();
    int cnt=0,sum=0;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cin>>a[i][j];
            if(a[i][j]){
                r[i]-=1<<a[i][j]-1;
                c[j]-=1<<a[i][j]-1;
                e[i/3][j/3]-=1<<a[i][j]-1;
                sum+=gs(i,j);
            }else cnt++;
        }
    }
    dfs(cnt,sum);
    cout<<ans;//输出答案
    return 0;
}