A-陶陶摘苹果

有10个苹果，陶陶想要摘苹果，但是陶陶把手伸直的时候不一定能摘到，于是他拿来了30厘米高的小板凳，这样陶陶总的高度就是陶陶把手伸直的时候能够达到的最大高度+30了。如果这个高度比苹果的高度高，那么就可以摘到苹果，cnt++。

#include<bits/stdc++.h>
using namespace std;
int main()
{
int a[10];
int h,x,cnt=0;
for(int i=0; i<=9; i++) cin>>a[i]; // 读入10个苹果高度
cin>>x;
h=x+30;
for(int i=0; i<=9; i++) if(h>=a[i]) cnt++; //如果陶陶达到的高度>=a[i]，则摘下的数目加1
cout<<cnt;
return 0;
}

B-最大公约数和最小公倍数问题

思路：

最大公约数和最小公倍数的乘积就是原两个数的积

设作为答案的两个数为 x 和 y，我们要使它们同时满足以下三个条件，并统计这样的 x 和 y 的个数（gcd为最大公因数, lcm为最小公倍数）：

• x×y = x_0×y_0
• gcd(x,y) = x_0
• lcm(x,y) = y_0

我们可以枚举 x，判断是否存在满足条件 1 的整数 y（即判断 x 能否被整除）。满足第一个条件后，再判断当前的 x,y 是否能够同时满足另外两个条件即可。当积相同且 gcd 相同时，lcm 也一定相同，因此只需判断是否满足一、二两个条件。

显然，从1枚举到是很慢的。考虑优化这个程序。我们其实并不需要枚举两次，因为对于不同的 x,y ，交换它们的值一定可以得到另一组与之对应的解。因此，从 1 到 sqrt(x_0×y_0) 枚举一遍，每发现一组答案就将 ans 的值加上 2 即可。这时还需要特判x和y相不相等，如果相等ans只需要加一次。

c++库中有__gcd()函数，可以直接使用（建议学会自己写gcd函数，具体可复习1940题）。注意开long long。

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long x0,y0,ans=0;
cin>>x0>>y0;
long long sum=x0*y0;
for(long long x=1; x*x<=sum; x++)
{
if(sum%x!=0) continue;//不满足第一个条件
long long y=sum/x;
if(__gcd(x,y)==x0)
{
if(x==y) ans++;
else ans+=2;
}
}
cout<<ans;
return 0;
}

C-最大正方形

思路：动态规划

建立数据f，f[i][j]表示以节点i,j为右下角，可构成的最大正方形的边长。

只有a[i][j]==1时，节点i,j才能作为正方形的右下角；

对于一个已经确定的f[i][j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1；

对于一个待确定的f[i][j]，我们已知f[i-1][j]，f[i][j-1]，f[i-1][j-1]的值。

举个例子：

假设f数组为（？处为f[i][j]，已知f[i-1][j]，f[i][j-1]，f[i-1][j-1]）:

? ? ? ?

? ? 2 1

? ? 3 ?

则说明原a数组为（假设a[i][j]=1）：

1 1 1 0

1 1 1 1

1 1 1 1

由此得出状态转移方程：

if(a[i][j]==1)  f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;

else f[i][j]=0;

#include<bits/stdc++.h>
using namespace std;
int a[101][101],n,m,f[101][101],ans;
int main()
{
scanf("%d%d",&n,&m);//读入
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
//因为只需用到i，j上方，左方，左上方的信息，读入同步处理
if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
ans=max(ans,f[i][j]);//同步更新答案
}
printf("%d",ans);
return 0;
}

D-方格取数

思路：记忆化搜索

我们设 f_{i,j,0} 表示从一个格子下方走到该格子后，从这个格子出发的路径最大和，f_{i,j,1}​ 表示从一个格子上方走到该格子的路径最大和，f_{i,j,2}​ 表示从一个格子左方走到该格子的路径最大和。

如果搜到以前搜过的状态则直接返回搜过的最大和（也就是 f 数组中的值），否则继续搜索从这个格子出发时的最大和。

在搜索是要注意判断下一个要去的方向是不是来的方向，如果是的话就不能走。

在搜索前要预处理一下边界条件，即我们已知到达终点时就没必要往下搜索了，那就需要预处理终点的f数组为它本身的值。

具体细节见代码注释。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;//定义一个极大值
int n,m;
int ne[3][2]={{-1,0},{1,0},{0,1}}; // 上 下 右
ll w[1005][1005],f[1005][1005][3];
//f[i][j][k]表示从(i,j)这个点出发所能取到的最大值，k表示来的方向
ll dfs(int x, int y, int from)//返回从(x,y)这个点出发，且从from方向来到(x,y)这个点时，最终能取到的最大值
{
if (f[x][y][from] != -inf) return f[x][y][from]; //如果不等于-inf 证明以前来过 直接返回答案
//在主函数内已经初始化了边界条件（终点的f数组是已知的）
for(int i=0;i<3;i++) //往三个方向走
{
int nx=x+ne[i][0],ny=y+ne[i][1];
if(nx<1||nx>n||ny<1||ny>m) continue; //边界条件
if(i+from==1) continue; //两种情况，i==1&&from==0，i==0&&from==1，这时候表明来的方向和去的方向相同，显然没必要走回头路
f[x][y][from]=max(f[x][y][from],dfs(nx,ny,i)+w[x][y]);//记忆化，得到下一个点能取到的最大值，再加上当前点的值
}
return f[x][y][from];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%lld", &w[i][j]);
f[i][j][0] = f[i][j][1] = f[i][j][2] = -inf;
}
}
f[n][m][0] = f[n][m][1] = f[n][m][2] = w[n][m]; //初始化终点的f数组，因为到终点之后就不需要走了
printf("%lld\n", dfs(1, 1, 1));//从(1,1)这个点开始走，第三个变量是什么无所谓，因为1是起点不会有from
//但是要注意防止函数在i+from==1这一行误判，所以第三个变量设置为1，因为起点往上走就越界了，所以不会误判
return 0;
}