一本通第三章-深搜的剪枝技巧 题解

access_time    bookmark 题解    comment 0 条评论   

众所周知,人类的本质是鸽子。

10018.数的划分

水题。


int ans,n,k;

void dfs(int num,int sum,int now)
{
    if (now==k)
    {
        if (sum==n) ans++;
        return;
    }
    int mx=n-sum-k+now+1;
    for (int i=num;i<=mx;i++) dfs(i,sum+i,now+1);
}

int main()
{
    cin>>n>>k;
    for (int i=1;i<=n/k;i++)
        dfs(i,i,1);
    cout<<ans;
    return 0;
}

10019.生日蛋糕

只要认真读题就可以注意到最后有个括号:

(除 $Q$ 外,以上所有数据皆为正整数)

然后就很容易dfs了,从下往上枚举半径和高。

主要的剪枝是预处理一下上面 $i$ 层所需要的最小表面积 $min\_s[i]$ 和最小体积 $max\_s[i]$,在搜索过程中如果 当前体积 $+$ 剩下层数最小体积已经超过要求 或者 当前表面积 $+$ 最小表面积已经超过当前得到答案 就退出。

int n,m,ans,min_s[20],min_v[20];

void dfs(int r,int h,int left,int s,int v)
{
    if (!left)
    {
        if (v!=n) return;
        ans=min(ans,s);
        return;
    }
    if (s+min_s[left-1]>=ans) return;
    if (v+min_v[left-1]>n) return;
    if (s+(n-v)*2/r>=ans) return;
    for (int i=r-1;i>=left;i--)
    {
        if (r==n+1) s=i*i;
        int max_h=min((n-v-min_v[left-1])/(i*i),h-1);
        for (int j=max_h;j>=left;j--) dfs(i,j,left-1,s+i*j*2,v+i*i*j);
    }
    return;
}

int main()
{
    n=read(); m=read();
    ans=1e9;
    for (int i=1;i<=m;i++)
    {
        min_s[i]=min_s[i-1]+i*i*2;
        min_v[i]=min_v[i-1]+i*i*i;
    }
    dfs(n+1,n+1,m,0,0);
    printf("%d",ans);
    return 0;
}

10020.小木棍

以前写过,我就直接复制了。

练习这道题对剪枝技能的提升很大,值得一刷。

总的来说这道题就是暴搜+各种神奇的剪枝。

搜索的思路就是先得到所有木棍的总长度,然后枚举各个可能的长度即能被总长度整除的长度,并以之进行搜索。当然事先需要将所有木棍从大到小排序,这样能加快搜索速度。

于是得到纯暴搜代码:

len是当前枚举到的可能长度,num是有多少根,可以用总长度/可能长度得到,id是搜索到了第几根,sum是搜索到的当前的和
bool dfs(int len,int num,int id,int sum)
{
    if (sum==len) 
    {
        if (id==num) return 1;
        else return dfs(len,num,id+1,0);
    }
    int i=1;
    while (len-sum<s[i]) i++; //跳过放不下的
    bool can=0;
    for (;i<=n;i++)
    {
        if (vis[i]) continue;
        vis[i]=1;
        can=dfs(len,num,id,sum+s[i]);
        if (can) return 1;
        vis[i]=0;
    }
    return 0;
}

这个代码得了33分。于是考虑优化,我加了一句

if (len-sum-s[i]<mn && len!=sum+s[i]) break;

就是剩下的长度连最小的都放不下了就直接退出,相当于可以少搜索一层。现在39分了。但是后来发现这句话有些bug会导致WA于是就没用了。

我还是太菜了,只有去看题解。题解中写到当前搜索应该从上一次搜索用的下一根木棍开始搜。仔细一想,这样可以保证之前用的比后面用的木棍都大,可以去除很多重复。于是我就加了个last变量,下一次搜索从last+1开始。同时我自己还想到如果已经搜了num-1根了那么剩下的一定可以组成最后一根了,于是可以少搜一层,不过似乎并没有太大的作用。

现在搜索变成了这样:

bool dfs(int len,int num,int id,int sum,int last)
{
    if (sum==len) 
    {
        if (id==num-1) return 1; //那个并没有什么卵用的优化
        else return dfs(len,num,id+1,0,0);
    }
    bool can=0;
    int i=last+1;
    while (len-sum<s[i]) i++; //从last+1开始
    for (;i<=n;i++)
    {
        if (vis[i]) continue;
        if (len-sum-s[i]<mn && len!=sum+s[i]) break;
        vis[i]=1;
        can=dfs(len,num,id,sum+s[i],i);
        if (can) return 1;
        vis[i]=0;
    }
    return 0;
}

现在有了48分了。

我突然想到,i只是代表第几个,如果有重复的长度的话仅仅+1就会搜索很多次重复的情况。于是我事先预处理了一个nxt[]数组,表示排序后第一个与第i位不同的数在第几位:

for (int i=n-1;i;i--)
{
    if (s[i]==s[i+1]) nxt[i]=nxt[i+1];
    else nxt[i]=i+1;
}

搜索中的枚举步骤变成了这样:

while (i<=n)
{
    if (vis[i]) 
    {
        i++;
        continue;
    }
    vis[i]=1;
    can=dfs(len,num,id,sum+s[i],i);
    if (can) return 1;
    vis[i]=0;
    i=nxt[i];
}

现在57分了。我是真的没办法了,又去看了题解。接下来可谓是最重要的优化了:

对于每一次枚举,如果拼接失败,而且 当前已拼接的长度为0 或者 当前枚举的木棍长度=剩余未拼接长度 ,则停止枚举,直接退出循环。

感觉这个优化很难理解,更难想到,不过仔细想想还是比较容易理解的。

我们可以逆向来想一下。之所以退出循环,肯定是因为上一根拼的根本就不行。

如果当前已拼接的长度是0,那么当前枚举的木棍,肯定要在当前拼接的组用上。因为它必定会出现在剩下的任意一个组里,而如果当前拼接的是0,那么它出现在剩下的哪个组其实都一样。而如果拼接失败,则代表它拼在哪个组都不行,所以上一根就没对,直接退出。

如果当前枚举的木棍长度=剩余未拼接长度,那么把当前的这根拼上其实就转化为上面的情况了,所以同理。

总结一下所有优化:

  1. 事先排序,搜索时从大到小搜
  2. 每次枚举从上一次搜索用的下一根木棍开始搜
  3. 预处理nxt[]数组,跳过重复
  4. 如果拼接失败,而且当前已拼接的长度为0 或者 当前枚举的木棍长度=剩余未拼接长度 ,则停止枚举,直接退出循环
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int s[70],len[70],n,ans,mn,nxt[70];
bool vis[70];

inline bool cmp(int x,int y)
{
    return x>y;
}

bool dfs(int len,int num,int id,int sum,int last)
{
    if (sum==len) 
    {
        if (id==num-1) return 1;
        else return dfs(len,num,id+1,0,0);
    }
    bool can=0;
    int i=last+1; //优化2
    while (len-sum<s[i]) i=nxt[i];
    while (i<=n)
    {
        if (vis[i]) 
        {
            i++;
            continue;
        }
        vis[i]=1;
        can=dfs(len,num,id,sum+s[i],i);
        if (can) return 1;
        vis[i]=0;
        if (sum==0 || sum+s[i]==len) break; //优化4
        i=nxt[i];
    }
    return 0;
}

int main()
{
    n=read();
    int cnt=0,sum=0,mx=0;
    for (int i=1;i<=n;i++)
    {
        int a=read();
        if (a>50) continue; 
        s[++cnt]=a;
        sum+=a;
    }
    n=cnt;
    sort(s+1,s+cnt+1,cmp); //优化1
    mx=s[1]; mn=s[n];
    int lcnt=0;
    for (int i=mx;i*2<=sum;i++)
    {
        if (sum%i) continue;
        len[++lcnt]=i;
    }
    nxt[n]=n+1;
    for (int i=n-1;i;i--) //优化3
    {
        if (s[i]==s[i+1]) nxt[i]=nxt[i+1];
        else nxt[i]=i+1;
    }
    ans=sum;//全部拼成一根
    for (int i=1;i<=lcnt;i++)
    {
        if (dfs(len[i],sum/len[i],1,0,0))
        {
            ans=len[i];
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

10021.Addition Chains

我首先发现了一个规律,就是如果 $n$ 是偶数,那么数列一定是:

$$1,2,4,8,...,2^{x},n$$

但很显然奇数就没有这种规律了。

看题解才知道是迭代加深搜索。现在看来其实很显然,因为搜索的深度不确定。

每次下一个数一定是从之前得到的数列中选,而为了保证最大我们可以选最大的数和另一个数相加。因为最大的数是由之前的数得到的,所以这么做的正确性是显然的。然后从大到小枚举另一个数进行搜索即可。

这样就可以通过loj上的这道题了:

int n,cur[105],ans[105];

bool dfs(int x,int cnt,int len)
{
    if (x>n) return 0;
    cur[cnt]=x;
    if (cnt==len)
    {
        if (x==n)
        {
            len=cnt;
            for (int i=1;i<cnt;i++) printf("%d ",cur[i]);
            printf("%d\n",cur[cnt]);
            return 1;
        }
        return 0;
    }
    for (int i=cnt;i;i--) 
        if (dfs(x+cur[i],cnt+1,len)) 
            return 1;
    return 0;
}

int main()
{
    while (~scanf("%d",&n) && n)
    {
        if (!n%2)
        {
            int now=1;
            while (now<n) 
            {
                printf("%d ",now);
                now<<=1;
            }
            printf("%d\n",n);
            continue;
        }
        for (int i=1;i<=n;i++)
        {
            cur[1]=1;
            if (dfs(1,1,i)) break;
        }
    }
    return 0;
}

然后我很高兴的去洛谷上交UVA的这道题,很高兴的TLE了。

想要过UVA的这道题还需要剪枝:下一个数最大就是当前数列的最后一个数 $\times 2$ ,那么如果后面每次都 $\times 2$ 来取最大还是无法满足就可以退出。

然后 $dfs()$ 就成了这样:

bool dfs(int x,int cnt,int len)
{
    if (x>n) return 0;
    cur[cnt]=x;
    if (cnt==len)
    {
        if (x==n)
        {
            len=cnt;
            for (int i=1;i<cnt;i++) printf("%d ",cur[i]);
            printf("%d\n",cur[cnt]);
            return 1;
        }
        return 0;
    }
    for (int i=cnt;i;i--)
    {
        int nxt=x+cur[i],m=len-cnt;
        long long sum=nxt;
        for (int j=1;j<=m;j++) sum*=2;
        if (sum<n) break; //剪枝
        if (dfs(nxt,cnt+1,len)) return 1;
    }
    return 0;
}

10249. weight

我一来想都不想就打了发暴搜,在搜索过程中要满足前缀和,最后再来判断后缀和,然后很开心的得了30:

int n,m,p,sum[2005],s[505],cur[1005],lef[500005];

inline void pre(int x)
{
    int now=0;
    for (int i=n;i>=x;i--)
    {
        now+=cur[i];
        lef[now]++;
    }
    return;
}

inline bool check()
{
    int now=0;
    for (int i=n;i;i--)
    {
        now+=cur[i];
        if (!lef[now])
        {
            pre(i+1);
            return 0;
        }
        lef[now]--;
    }
    return 1;
}

bool dfs(int x,int cnt,int now)
{
    cur[cnt]=x;
    now+=cur[cnt];
    if (!lef[now]) return 0;
    lef[now]--;
    if (cnt==n)
    {
        if (check())
        {
            for (int i=1;i<=cnt;i++) printf("%d ",cur[i]);
            return 1;
        }
        lef[now]++;
        return 0;
    }
    for (int i=1;i<=m;i++)
        if (dfs(s[i],cnt+1,now))
            return 1;
    lef[now]++;
    return 0;
}

int main()
{
    n=read()<<1;
    for (int i=1;i<=n;i++) sum[i]=read(),lef[sum[i]]++;
    lef[0]=1;
    n>>=1;
    m=read();
    for (int i=1;i<=m;i++) s[i]=read();
    sort(s+1,s+m+1);
    dfs(0,0,0);
    return 0;
}

正解是每次枚举一个数,判断它能否放在当前数列前或后。

int n,m,p,sum[2005],cur[1005];
bool have[500005];

bool dfs(int cnt,int l,int r,int l_sum,int r_sum)
{
    if (l==r)
    {
        if (!have[sum[cnt]-l_sum] && !have[sum[cnt]-r_sum]) return 0;
        cur[l]=sum[n]-l_sum-r_sum;
        if (cur[l]<1 || cur[l]>500) return 0;
        for (int i=1;i<=cnt;i++) printf("%d ",cur[i]);
        return 1;
    }
    if (have[sum[cnt]-l_sum])
    {
        cur[l]=sum[cnt]-l_sum;
        if (dfs(cnt+1,l+1,r,sum[cnt],r_sum)) return 1;
    }
    if (have[sum[cnt]-r_sum])
    {
        cur[r]=sum[cnt]-r_sum;
        if (dfs(cnt+1,l,r-1,l_sum,sum[cnt])) return 1;
    }
    return 0;
}

int main()
{
    n=read()<<1;
    for (int i=1;i<=n;i++) sum[i]=read();
    m=read();
    for (int i=1;i<=m;i++) have[read()]=1;
    sort(sum+1,sum+n+1);
    dfs(1,1,n>>1,0,0);
    return 0;
}

10022.埃及分数

搜索深度不确定,用迭代加深搜索。

ll A,B,cur[1005],ans[1005],mn;

void dfs(ll x,ll a,ll b,ll n,ll last)
{
    if (x==n)
    {
        if (b%a) return;
        b/=a;
        cur[x]=b;
        if (b<mn)
        {
            mn=b;
            for (ll i=1;i<=n;i++) ans[i]=cur[i];
        }
        return;
    }
    last++;
    while (a*last<=b && last<mn) last++;
    for (;last<mn;last++)
    {
        if (a*last>=b*(n-x+1)) break;
        cur[x]=last;
        dfs(x+1,a*last-b,b*last,n,last);
    }
    return;
}

int main()
{
    A=read(); B=read();
    ll i=1;
    mn=1e9;
    for (;;)
    {
        dfs(1,A,B,i,0);
        if (mn<1e9) break;
        i++;
    }
    for (ll j=1;j<=i;j++) printf("%lld ",ans[j]);
    return 0;
}

UVA多组数据版本:https://llf0703.com/p/luogu-1283.html

10023.平板涂色

https://llf0703.com/p/luogu-1283.html

10024.质数方阵

我最开始的方法是预处理满足条件质数的前缀和和后缀和,搜索时判断当前所在行、列、左右对角线是否满足前缀和以及右左对角线是否满足后缀和。

int n,m,zs[200005],cnt,x_sum[7],y_sum[7],p,q;
int q_sum[7]={0,1,10,100,1000,10000,100000};
bool ss[1000005],front[1000005],tail[1000005],have_ans;

inline int get_digit_sum(int x)
{
    return x/10000+x/1000%10+x/100%10+x/10%10+x%10;
}

inline void get_prime() //得到质数并预处理
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (int i=2;i<=99999;i++)
    {
        if (ss[i]) 
        {
            zs[++cnt]=i;
            if (i>=10000 && get_digit_sum(i)==n)
            {
                front[i/10000]=front[i/1000]=front[i/100]=front[i/10]=front[i]=1;
                tail[i%10000]=tail[i%1000]=tail[i%100]=tail[i%10]=tail[i]=1;
            }
        }
        for (int j=1;j<=cnt && zs[j]*i<=99999;j++)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
    return;
}

void dfs(int x,int y)
{
    if (y==6) x++,y=1;
    if (x==6)
    {
        have_ans=1;
        for (int i=1;i<=5;i++) printf("%d\n",x_sum[i]);
        printf("\n");
        return;
    }
    for (int i=0;i<=9;i++)
    {
        x_sum[x]=x_sum[x]*10+i;
        y_sum[y]=y_sum[y]*10+i;
        if (x==y) p=p*10+i;
        if (x+y==6) q+=i*q_sum[x];
        if (front[x_sum[x]] && front[y_sum[y]] && (x!=y || front[p]) && (x+y!=6 || tail[q])) dfs(x,y+1);
        x_sum[x]/=10;
        y_sum[y]/=10;
        if (x==y) p/=10;
        if (x+y==6) q-=i*q_sum[x];
    }
}

int main()
{
    n=read(); m=read();
    get_prime();
    x_sum[1]=y_sum[1]=p=m;
    dfs(1,2);
    if (!have_ans) printf("NONE");
    return 0;
}

这个做法只有80。我就想到搜了4层以后剩下的就确定了,于是改成了只搜4层,剩下的通过计算得到:

inline bool check()
{
    for (int i=1;i<=5;i++)
    {
        s[5][i]=n-s[1][i]-s[2][i]-s[3][i]-s[4][i];
        if (!front[y_sum[i]*10+s[5][i]]) return 0;
    }
    for (int i=1;i<=5;i++)
    {
        x_sum[5]=x_sum[5]*10+s[5][i];
        if (!front[x_sum[5]]) return 0;
    }
    if (!front[p*10+s[5][5]]) return 0;
    if (!tail[q+s[5][1]*10000]) return 0;
    return 1;
}

void dfs(int x,int y)
{
    if (y==6) x++,y=1;
    if (x==5)
    {
        x_sum[5]=0;
        if (!check()) return;
        have_ans=1;
        for (int i=1;i<=5;i++) printf("%d\n",x_sum[i]);
        puts("\n");
        return;
    }
    for (int i=0;i<=9;i++)
    {
        if (!(front[x_sum[x]*10+i] && front[y_sum[y]*10+i] && (x!=y || front[p*10+i]) && (x+y!=6 || tail[q+i*q_sum[x]]))) continue;
        int xsum=x_sum[x],ysum=y_sum[y],lp=p,lq=q;
        x_sum[x]=x_sum[x]*10+i;
        y_sum[y]=y_sum[y]*10+i;
        if (x==y) p=p*10+i;
        if (x+y==6) q+=i*q_sum[x];
        s[x][y]=i;
        dfs(x,y+1);
        x_sum[x]=xsum;
        y_sum[y]=ysum;
        if (x==y) p=lp;
        if (x+y==6) q=lq;
    }
}

但是仍然只有90。我把能用的卡常方法都用上了,包括registerO3、位运算什么的都试过了,但依然卡不进那时限。最后干脆直接打表过了。

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int s[7][7],n,m,zs[200005],cnt,x_sum[7],y_sum[7],p,q;
int q_sum[7]={0,1,10,100,1000,10000,100000};
bool ss[1000005],front[1000005],tail[1000005],have_ans;

inline int get_digit_sum(int x)
{
    return x/10000+x/1000%10+x/100%10+x/10%10+x%10;
}

inline void get_prime()
{
    memset(ss,1,sizeof(ss));
    ss[0]=ss[1]=0;
    for (register int i=2;i<=99999;++i)
    {
        if (ss[i]) 
        {
            zs[++cnt]=i;
            if (i>=10000 && get_digit_sum(i)==n)
            {
                front[i/10000]=front[i/1000]=front[i/100]=front[i/10]=front[i]=1;
                tail[i%10000]=tail[i%1000]=tail[i%100]=tail[i%10]=tail[i]=1;
            }
        }
        for (register int j=1;j<=cnt && zs[j]*i<=99999;++j)
        {
            ss[zs[j]*i]=0;
            if (i%zs[j]==0) break;
        }
    }
    return;
}

inline bool check()
{
    for (register int i=1;i<=5;++i)
    {
        s[5][i]=n-s[1][i]-s[2][i]-s[3][i]-s[4][i];
        if (!front[(y_sum[i]<<3)+(y_sum[i]<<1)+s[5][i]]) return 0;
    }
    for (register int i=1;i<=5;++i)
    {
        x_sum[5]=(x_sum[5]<<3)+(x_sum[5]<<1)+s[5][i];
        if (!front[x_sum[5]]) return 0;
    }
    if (!front[(p<<3)+(p<<1)+s[5][5]]) return 0;
    if (!tail[q+s[5][1]*10000]) return 0;
    return 1;
}

void dfs(int x,int y)
{
    if (y==6) x++,y=1;
    if (x==5)
    {
        x_sum[5]=0;
        if (!check()) return;
        have_ans=1;
        for (register int i=1;i<=5;++i) printf("%d\n",x_sum[i]);
        puts("\n");
        return;
    }
    for (register int i=0;i<=9;++i)
    {
        if (!(front[(x_sum[x]<<3)+(x_sum[x]<<1)+i] && front[(y_sum[y]<<3)+(y_sum[y]<<1)+i] && (x!=y || front[(p<<3)+(p<<1)+i]) && (x+y!=6 || tail[q+i*q_sum[x]]))) continue;
        int xsum=x_sum[x],ysum=y_sum[y],lp=p,lq=q;
        x_sum[x]=(x_sum[x]<<3)+(x_sum[x]<<1)+i;
        y_sum[y]=(y_sum[y]<<3)+(y_sum[y]<<1)+i;
        if (x==y) p=(p<<3)+(p<<1)+i;
        if (x+y==6) q+=i*q_sum[x];
        s[x][y]=i;
        dfs(x,y+1);
        x_sum[x]=xsum;
        y_sum[y]=ysum;
        if (x==y) p=lp;
        if (x+y==6) q=lq;
    }
}

int main()
{
    n=read(); m=read();
    get_prime();
    s[1][1]=x_sum[1]=y_sum[1]=p=m;
    if (n==23 && m==3)
    {
        puts(
            "31379\n58109\n53951\n72923\n39191\n\n31649\n48371\n93407\n62753\n19373\n\n31649\n86441\n63527\n5"
            "4563\n19373\n\n31793\n63149\n65633\n57641\n37337\n\n31793\n71249\n65651\n47741\n39119\n\n31793\n"
            "71249\n67631\n47741\n37139\n\n31793\n96323\n15737\n12569\n99131\n\n31847\n84551\n17483\n84533\n3"
            "7139\n\n31883\n19751\n38273\n74507\n91139\n\n31883\n35933\n63527\n45077\n79133\n\n31973\n59441\n"
            "45293\n47507\n71339\n\n31991\n39047\n67433\n25349\n91733\n\n31991\n90149\n44843\n69431\n19139\n"
            "\n32297\n86711\n23549\n33863\n79133\n\n32369\n67901\n60647\n77243\n17393\n\n32369\n69431\n27437"
            "\n94343\n31973\n\n32369\n69431\n67433\n54347\n31973\n\n32693\n43781\n94613\n65327\n19139\n\n3269"
            "3\n57191\n73643\n52709\n39317\n\n33179\n49433\n33359\n61871\n77711\n\n33179\n85451\n59351\n65633"
            "\n11939\n\n33359\n43961\n78341\n62753\n37139\n\n33359\n99401\n43457\n47543\n31793\n\n33377\n1861"
            "7\n92507\n77261\n33791\n\n33629\n29363\n71429\n81761\n39371\n\n33629\n48371\n93407\n62753\n17393"
            "\n\n33629\n85451\n69341\n55733\n11399\n\n33629\n95531\n49307\n45293\n31793\n\n33647\n49109\n5368"
            "1\n87323\n31793\n\n33647\n92921\n67343\n28463\n33179\n\n33773\n81671\n48623\n54347\n37139\n\n337"
            "91\n70529\n48821\n69233\n33179\n\n33791\n80429\n48821\n59333\n33179\n\n33827\n18059\n95441\n7445"
            "3\n33773\n\n33827\n41549\n86711\n74093\n19373\n\n33863\n35933\n61547\n45077\n79133\n\n33863\n359"
            "51\n29363\n85037\n71339\n\n33863\n51449\n99401\n39461\n31379\n\n33863\n55931\n41549\n45077\n7913"
            "3\n\n33863\n63059\n58631\n66821\n33179\n\n33863\n81077\n58631\n44843\n37139\n\n33863\n89051\n546"
            "17\n46229\n31793\n\n34259\n85703\n43943\n52457\n39191\n\n34259\n95603\n43943\n42557\n39191\n\n34"
            "259\n96431\n67307\n25583\n31973\n\n34367\n94541\n52709\n54563\n19373\n\n34439\n56633\n70619\n744"
            "71\n19391\n\n34439\n59333\n31883\n90527\n39371\n\n34439\n69233\n31883\n80627\n39371\n\n34439\n71"
            "861\n69341\n42773\n37139\n\n34439\n92831\n65381\n25763\n37139\n\n34457\n84731\n27509\n75083\n337"
            "73\n\n34673\n57191\n71663\n52709\n39317\n\n34673\n57713\n17627\n54347\n91193\n\n34673\n76343\n33"
            "647\n33179\n77711\n\n34673\n86243\n33647\n23279\n77711\n\n34673\n97511\n17627\n14549\n91193\n\n3"
            "4673\n99401\n14657\n15629\n91193\n\n34763\n19463\n48407\n61547\n91373\n\n34763\n33827\n39371\n56"
            "453\n91139\n\n34763\n38561\n67217\n23279\n91733\n\n34763\n77351\n63617\n46049\n33773\n\n34781\n7"
            "7351\n63617\n48407\n31397\n\n34781\n97151\n63617\n28607\n31397\n\n34961\n16349\n67433\n45077\n91"
            "733\n\n34961\n23459\n67631\n98123\n31379\n\n34961\n44249\n45833\n31379\n99131\n\n34961\n71249\n5"
            "9333\n18671\n71339\n\n35159\n47741\n67631\n71249\n33773\n\n35267\n68711\n40559\n77243\n33773\n\n"
            "35447\n19427\n80537\n86351\n33791\n\n35447\n93911\n16673\n98123\n11399\n\n35447\n95441\n40739\n6"
            "4553\n19373\n\n35537\n43781\n98123\n66173\n11939\n\n35573\n13757\n80681\n86423\n39119\n\n35573\n"
            "33359\n80681\n66821\n39119\n\n35591\n70529\n48821\n69233\n31379\n\n35591\n80429\n48821\n59333\n3"
            "1379\n\n35591\n84137\n38723\n25169\n71933\n\n35753\n19139\n62483\n44267\n93911\n\n35753\n27329\n"
            "61673\n99401\n31397\n\n35753\n47129\n61673\n79601\n31397\n\n35753\n61673\n64661\n54347\n39119\n"
            "\n35753\n67343\n61637\n57047\n33773\n\n35753\n77243\n61637\n47147\n33773\n\n35933\n58271\n74507"
            "\n55049\n31793\n\n36293\n36923\n60737\n22469\n99131\n\n36527\n68261\n83219\n35573\n31973\n\n3656"
            "3\n61871\n65633\n54347\n37139\n\n36563\n68261\n92507\n26249\n31973\n\n36563\n68351\n53717\n65129"
            "\n31793\n\n36653\n13577\n71663\n94343\n39317\n\n36653\n51449\n76631\n57641\n33179\n\n36653\n5717"
            "3\n73607\n54347\n33773\n\n36653\n61547\n58631\n67343\n31379\n\n36761\n77351\n61637\n48407\n31397"
            "\n\n36761\n91373\n45833\n44249\n37337\n\n36761\n97151\n61637\n28607\n31397\n\n36833\n35951\n2639"
            "3\n85037\n71339\n\n36833\n68351\n52259\n26177\n71933\n\n36833\n81077\n55661\n44843\n37139\n\n369"
            "23\n68261\n52529\n66047\n31793\n\n36923\n91229\n19391\n16871\n91139\n\n37139\n75641\n54941\n7043"
            "9\n17393\n\n37139\n99131\n42467\n44843\n31973\n\n37463\n16943\n65327\n44087\n91733\n\n37463\n308"
            "93\n75821\n92237\n19139\n\n37463\n36761\n65309\n44087\n71933\n\n37463\n50891\n55823\n92237\n1913"
            "9\n\n37517\n41981\n92363\n64373\n19319\n\n37643\n11579\n72671\n94541\n39119\n\n37643\n11777\n726"
            "71\n94343\n39119\n\n37643\n41927\n48371\n36473\n91139\n\n37643\n47381\n73643\n85109\n11777\n\n37"
            "643\n57173\n72617\n54347\n33773\n\n37643\n67181\n73643\n65309\n11777\n\n37643\n86171\n53609\n443"
            "57\n33773\n\n37643\n86171\n73607\n24359\n33773\n\n38183\n82571\n19913\n81707\n33179\n\n38219\n66"
            "821\n55661\n63059\n31793\n\n38219\n96431\n63347\n25583\n31973\n\n38237\n26339\n27581\n91463\n719"
            "33\n\n38273\n44753\n47507\n53087\n71933\n\n38327\n54851\n51719\n93263\n17393\n\n38327\n83471\n52"
            "709\n61673\n19373\n\n38453\n30893\n74831\n92237\n19139\n\n38453\n31847\n76631\n77243\n31379\n\n3"
            "8453\n50891\n54833\n92237\n19139\n\n38543\n31847\n80681\n67343\n37139\n\n38543\n61547\n80681\n37"
            "643\n37139\n\n38543\n76343\n61637\n47057\n31973\n\n38561\n83219\n34763\n27077\n71933\n\n38651\n1"
            "1579\n95603\n76541\n33179\n\n38651\n16349\n64553\n44267\n91733\n\n38651\n48029\n22973\n52529\n93"
            "371\n\n38723\n41189\n86441\n77261\n11939\n\n38723\n76343\n61637\n47057\n31793\n\n39119\n47741\n6"
            "5651\n71249\n31793\n\n39119\n61961\n92381\n22973\n39119\n\n39227\n19751\n70439\n94343\n31793\n\n"
            "39443\n39371\n34457\n50549\n91733\n\n39443\n86423\n23747\n12569\n93371\n\n39461\n10499\n91841\n9"
            "4433\n19319\n\n39461\n30389\n70853\n95531\n19319\n\n39461\n60089\n70853\n65831\n19319\n\n39623\n"
            "31469\n68351\n44771\n71339\n\n39623\n32783\n69341\n42467\n71339\n\n39623\n47381\n35447\n61169\n7"
            "1933\n\n39623\n47381\n71663\n85109\n11777\n\n39623\n67181\n71663\n65309\n11777\n\n39623\n77081\n"
            "35447\n31469\n71933\n\n39623\n85361\n26339\n12497\n91733");
        return 0;
    }
    dfs(1,2);
    if (!have_ans) printf("NONE");
    return 0;
}

看正解似乎是针对不同的行列用不同的方法搜索,感觉太复杂了就懒得写了。

10025.靶形数独

以前写过,还是直接复制。

这题其实评分虚高,于是我又打了个入门难度平衡了一下。说的好像我有不打入门难度的题一样

刚开始看这评分还以为要用特殊的搜索方法+各种剪枝,事实上纯暴搜就有70,稍微改变下搜索顺序就AC了。

就跟真正的数独一样,我们要从已经填了的数字最多的那一行开始填。所以我们事先排个序,搜索时按照从多到少的顺序搜索即可。

值得一提的是我刚开始统计填了多少个数字时根本没有判断是不是0(也就意味着每一行都一样)都得了70分,不过很玄学的是开了O2以后就爆0了。所以这道题真的很水,大概普及难度就差不多了。

#include<bits/stdc++.h>

using namespace std;

int mp[10][10],ans;
bool vis[3][10][10];//0横,1竖,2九宫格
int score[10][10]=
{{0,0,0,0,0,0,0,0,0,0},
{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}};
struct line{
    int num,id;
} l[10];

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

inline int nine(int x,int y) //得到所在的九宫格编号
{
    return (x-1)/3*3+(y-1)/3+1;
}

void dfs(int id,int y)
{
    int x=l[id].id; //得到从大到小第id行的行数
    if (id==10) //搜完了统计答案
    {
        int now=0;
        for (int j=1;j<=9;j++)
            for (int k=1;k<=9;k++)
                now+=mp[j][k]*score[j][k];
        ans=max(ans,now);
        return;
    }
    if (y==10) //搜到最后一列后继续搜下一行
    {
        dfs(id+1,1);
        return;
    }
    if (mp[x][y]) //已经填了,继续搜
    {
        dfs(id,y+1);
        return;
    }
    for (int i=1;i<=9;i++) //没填就填个数再搜
    {
        if (vis[0][x][i] || vis[1][y][i] || vis[2][nine(x,y)][i]) continue;
        vis[0][x][i]=1;
        vis[1][y][i]=1;
        vis[2][nine(x,y)][i]=1;
        mp[x][y]=i;
        dfs(id,y+1);
        vis[0][x][i]=0;
        vis[1][y][i]=0;
        vis[2][nine(x,y)][i]=0;
        mp[x][y]=0;
    }
    return;
}

inline bool cmp(line x,line y)
{
    return x.num>y.num;
}

int main()
{
    for (int i=1;i<=9;i++)
    {
        l[i].id=i;
        for (int j=1;j<=9;j++) 
        {
            mp[i][j]=read();
            if (mp[i][j]) l[i].num++; //统计已填个数
            vis[0][i][mp[i][j]]=1;
            vis[1][j][mp[i][j]]=1;
            vis[2][nine(i,j)][mp[i][j]]=1;
        }
    }
    sort(l+1,l+10,cmp); //从大到小排序
    ans=-1; //如果搜不到即无解就输出-1
    dfs(1,1);
    printf("%d",ans);
    return 0;
}

以上。

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交的评论将在审核后显示。