众所周知，人类的本质是鸽子。
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，那么它出现在剩下的哪个组其实都一样。而如果拼接失败，则代表它拼在哪个组都不行，所以上一根就没对，直接退出。
如果当前枚举的木棍长度=剩余未拼接长度，那么把当前的这根拼上其实就转化为上面的情况了，所以同理。
总结一下所有优化：
- 事先排序，搜索时从大到小搜
- 每次枚举从上一次搜索用的下一根木棍开始搜
- 预处理
nxt[]数组，跳过重复 - 如果拼接失败，而且当前已拼接的长度为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。我把能用的卡常方法都用上了，包括register、O3、位运算什么的都试过了，但依然卡不进那时限。最后干脆直接打表过了。
#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;
}以上。