木棒
思路
我们可以先想暴搜
木棍的长度len只能是sum的约数(这其实是个可行性剪枝)
用u来表示是第几根 用num来表示现在的长度
每一次找到能拼接的木棍,拼上去. 当num=len就让u++,拼下一根木棍
剪枝：
优化搜索顺序:
让木棍从大到小排序,因为大的占更多空间,剩下的变小了
排除等效冗余：
我们可以用一个last记录上一个小木棍的长度,新的木棍从这个木棍开始找.
设上一根是x,新的是y. 先x再y和先y再x一样,x<y时,先y再x早找过了，这是重复
可行性剪枝
1.当这根小木棍作为第一个都不行，直接回溯，因为一个木棍可以换顺序,所以在第一个不行在其他地方也不行
2.当这根小木棍作为最后一个都不行，直接回溯，因为在拆分成多个小木棒,递归也必然不行。
代码
#include<bits/stdc++.h>
using namespace std;
int n,flag[70],a[70],sum,len,cnt;
bool dfs(int ans,int num,int last)
{
if(ans==cnt+1) return true;
if(num==len) return dfs(ans+1,0,1);
for(int i=last;i<=n;i++)
{
if(flag[i]) continue;
if(num+a[i]>len) continue;
if(a[i]==a[i-1]&&flag[i-1]==0) continue;
flag[i]=1;
if(dfs(ans,num+a[i],i)) return true;
flag[i]=0;
if(num+a[i]==len||num==0) return false;
}
return false;
}
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
while(cin>>n&&n)
{
int maxx=0;
sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]>50) continue;
maxx=max(maxx,a[i]);
sum+=a[i];
}
sort(a+1,a+1+n,cmp);
for(len=maxx;len<=sum;len++)
{
memset(flag,0,sizeof flag);
for(int i=1;i<=n;i++) if(a[i]>50) flag[i]=1;
if(sum%len) continue;
cnt=sum/len;
if(dfs(1,0,1)) break;
}
cout<<len<<endl;
}
}
生日蛋糕
思路
我们可以先想暴搜
暴力枚举每一层的半径和高度,并且存储体积和表面积.当层数到达m,体积是n时，更新答案.
设当前层是cnt,sum是第cnt+1层到第m层的体积和,第cnt层半径的上下界是
$r[cnt]=|cnt,min(r[cnt-1]-1,\sqrt\frac{n-sum}{h[cnt]})|$
设当前层是cnt,sum是第cnt+1层到第m层的体积和,第cnt层高度的上下界是
$h[cnt]=|cnt,min(h[cnt-1]-1,\frac{n-sum}{r[cnt]^2})|$
剪枝： 优化搜索顺序: 层数从大到小,先枚举半径再枚举高度
可行性剪枝:
1.当 当前体积加上(1~m)层的最小体积都大于,回溯
最优性剪枝:
1.当 当前表面积加上(1~m)层的最小表面积都大于答案,回溯
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,r[30],h[30],mins[30],minv[30],minn=2e9;
void dfs(int v,int s,int level)
{
if(!level)
{
if(v==n)
{
minn=min(minn,s);
}
return;
}
if(v+minv[level]>n) return;
if(s+mins[level]>=minn) return;
if(s+2*(n-v)/r[level+1]>=minn) return;
for(int r1=min(r[level+1]-1,(int)sqrt((n-v-minv[level-1])/level));r1>=level;r1--)
{
for(int h1=min(h[level+1]-1,(n-v-minv[level-1])/r1/r1);h1>=level;h1--)
{
r[level]=r1;
h[level]=h1;
if(level==m) dfs(v+r1*r1*h1,s+r1*r1+2*r1*h1,level-1);
else dfs(v+r1*r1*h1,s+2*r1*h1,level-1);
}
}
return;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
mins[i]=mins[i-1]+2*i*i;
minv[i]=minv[i-1]+i*i*i;
}
r[m+1]=2e9;
h[m+1]=2e9;
dfs(0,0,m);
if(minn==2e9) minn=0;
cout<<minn;
}
靶形数独
思路
(没啥好说的)
数独加上计算分数
代码
#include<bits/stdc++.h>
using namespace std;
int row[9],col[9],sqrae[3][3],maxx;
int bin_1[(1<<9)],num[(1<<9)];
char s[9][9];
int lowbit(int x)
{
return x&-x;
}
void db()
{
int sum=1;
for(int i=0;i<9;i++)
{
num[sum]=i;
sum*=2;
}
for(int i=0;i<(1<<9);i++)
{
for(int j=i;j;j-=lowbit(j))
{
bin_1[i]++;
}
}
return;
}
void db2()
{
for(int i=0;i<9;i++)
{
row[i]=(1<<9)-1;
col[i]=(1<<9)-1;
sqrae[i/3][i%3]=(1<<9)-1;
}
return;
}
int get(int x,int y)
{
int sum=(row[x]&col[y]&sqrae[x/3][y/3]);
return sum;
}
void dfs(int cnt)
{
if(cnt==0)
{
int sum=0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
for(int k=0;k<5;k++)
{
if(i==k||j==k||i+k==8||j+k==8)
{
sum+=(s[i][j]-'1'+1)*(k+6);
break;
}
}
}
}
maxx=max(maxx,sum);
return;
}
int i,j,minn=20;
for(int x=0;x<9;x++)
{
for(int y=0;y<9;y++)
{
if(s[x][y]=='.')
{
if(bin_1[get(x,y)]<minn)
{
i=x;
j=y;
minn=bin_1[get(x,y)];
}
}
}
}
for(int k=get(i,j);k;k-=lowbit(k))
{
int num2=num[lowbit(k)];
row[i]-=1<<num2;
col[j]-=1<<num2;
sqrae[i/3][j/3]-=1<<num2;
s[i][j]='1'+num2;
dfs(cnt-1);
row[i]+=1<<num2;
col[j]+=1<<num2;
sqrae[i/3][j/3]+=1<<num2;
s[i][j]='.';
}
return;
}
int main()
{
db();
db2();
int cnt=0;
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
cin>>s[i][j];
if(s[i][j]!='0')
{
int num=s[i][j]-'1';
row[i]-=1<<num;
col[j]-=1<<num;
sqrae[i/3][j/3]-=1<<num;
}
else
{
s[i][j]='.';
cnt++;
}
}
}
dfs(cnt);
if(!maxx) maxx=-1;
cout<<maxx<<endl;
}