第一题：生日蛋糕
题解：这题是蛋糕结构是一层一层的，估计很多人很快就能想到是dfs，但是这题的难想的点在于
你每层的状态该怎么去确定，你怎么来确定每层的半径和高度是多少，一开始我也不知很理解，直到在网上看到了一篇大佬的博客才让我茅塞顿开，我干嘛非要确定呢，全用最小的不就好了，因此我们要写出每层的最小的体积和面积，然后用前缀和累加起来，然后三个剪枝（代码里有注释）减少运算，就可以愉快的AC了
#include<iostream>
#include<cstring>
#include<cstdio>
#include <queue>
#include<math.h>
using namespace std;
int n,m;
int sums[16];
int sumv[16];
int sum=0x7fffffff;//记录最小的值
void dfs(int t,int s,int v,int r,int h)
{
if(t==0)
{
if(s<sum&&v==n)
{
sum=s;
}
return ;
}
if(s+sums[t]>sum)//第一个剪枝，你目前的面积，加上上面层的最小的面积>已知面积，可以直接跳过
return ;
if(v+sumv[t]>n)//第二个剪枝，你目前的体积，加上上面层的最小的体积>要求的体积，可以直接跳过
return ;
if(s+2*(n-v)/r>sum)//第三个剪枝，你把所有体积都做成一层蛋糕，如果面积>已知面积，跳过
return ;
for(int i=r-1;i>=t;i--)
{
if(t==m)
s=i*i;
int h1=min(h-1,(n-v-sumv[t-1])/(i*i));
for(int j=h1;j>=t;j--)
{
dfs(t-1,s+2*i*j,v+i*i*j,i,j);
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
sumv[i]+=sumv[i-1]+i*i*i;
sums[i]+=sums[i-1]+2*i*i;
}
dfs(m,0,0,sqrt((double)n)+1,n);
if(sum==0x7fffffff)
{
printf("0");
return 0;
}
printf("%d",sum);
return 0;
}第二题：速算24
题解：这题一开始也卡了我好久，我一直不明白哪里错了，后面问了学长，但是还是自己想出来为什么错了，因为有可能二三进行运算，这样的话，就会漏掉情况，所以一开始一直过不了，然后写出来了，还用到了全排列函数（不会的可以去了解一下），AC代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
char s[5]={0};
int num[5]={0};
int flag=0;
void dfs(int sum,int count,int nextt)
{
if(flag==1)
return ;
if(count==3)
{
if(sum+nextt==24)
flag=1;
if(sum-nextt==24)
flag=1;
if(sum*nextt==24)
flag=1;
if(nextt!=0&&sum%nextt==0&&sum/nextt==24)
flag=1;
return ;
}
dfs(sum+nextt,count+1,num[count+1]);
dfs(sum-nextt,count+1,num[count+1]);
dfs(sum*nextt,count+1,num[count+1]);
if(nextt!=0&&sum%nextt==0)
{
dfs(sum/nextt,count+1,num[count+1]);
}
dfs(sum,count+1,nextt+num[count+1]);
dfs(sum,count+1,nextt-num[count+1]);
dfs(sum,count+1,nextt*num[count+1]);
if(num[count+1]!=0&&nextt%num[count+1]==0)
{
dfs(sum,count+1,nextt/num[count+1]);
}
// dfs(sum+nextt,count+1,num[count+1]);
// dfs(sum-nextt,count+1,num[count+1]);
// dfs(sum*nextt,count+1,num[count+1]);
// if(sum%nextt==0&&nextt!=0)
// {
// dfs(sum/nextt,count+1,num[count+1]);
// }
// dfs(sum,count+1,nextt+num[count+1]);
// dfs(sum,count+1,nextt-num[count+1]);
// dfs(sum,count+1,nextt*num[count+1]);
// if(nextt%num[count+1]==0&&num[count+1]!=0)
// {
// dfs(sum,count+1,nextt/num[count+1]);
// }
}
int main()
{
while (~scanf("%s", s))
{
flag = 0;
if (strlen(s) == 2)
num[0] = 10;
else
{
if (s[0] == 'A')
num[0] = 1;
else if (s[0] == 'J')
num[0] = 11;
else if (s[0] == 'Q')
num[0] = 12;
else if (s[0] == 'K')
num[0] = 13;
else
num[0] = s[0] - '0';
}
for (int i = 1; i < 4; i++)
{
scanf("%s", s);
if (strlen(s) == 2)
num[i] = 10;
else
{
if (s[0] == 'A')
num[i] = 1;
else if (s[0] == 'J')
num[i] = 11;
else if (s[0] == 'Q')
num[i] = 12;
else if (s[0] == 'K')
num[i] = 13;
else
num[i] = s[0] - '0';
}
}
flag=0;
sort(num,num+4);
do
{
dfs(num[0],1,num[1]);
}
while(next_permutation(num,num+4)&&flag==0);
if (flag == 1)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
