A-级数求和

从1开始枚举n，每次累加Sn，直到Sn>k结束，只需要一个循环即可实现。需要注意Sn应为小数，并注意整除和小数除法的区别。

#include<bits/stdc++.h>
using namespace std;
int main()
{
int k;
cin>>k;
double Sn=0;
int n=0;
while(Sn<=k)//当Sn>k时，跳出循环
{
n++;
Sn+=1.0/n;//注意此处为小数除法
}
cout<<n;
return 0;
}

B-地毯

思路：差分

这道题与1904题差分矩阵几乎相同，只是把子矩阵中的每个元素的值加上c改成了固定加上1。所以只要掌握了差分矩阵的思路，这道题便可迎刃而解。

#include<bits/stdc++.h>
using namespace std;
int a[1024][1024],b[1024][1024];
//a为原矩阵 b为差分矩阵
int main()
{
int n,m,xa,ya,xb,yb;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i)
{
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
b[xa][ya]++;
b[xb+1][ya]--;
b[xa][yb+1]--;
b[xb+1][yb+1]++;
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}

C-数水坑

思路：搜索

这是一道典型的搜索题，搜索思路是从每个水坑出发，并标记和它相连的所有点（即把同一个水坑中的点全部标记），这个过程可以用dfs或bfs来解决。搜索完这一个水坑过后，这个水坑中的所有点就都被标记了（被标记的点我们不再搜索），并且我们找到了一个相连的水坑，cnt++。

这道题需要注意的是搜索是向八个方向搜索的，且在搜索时要控制边界条件，并且要下一个点是水坑才向下搜索。

最后输出水坑的个数cnt即可，这也是我们进行搜索的次数。

#include<bits/stdc++.h>
using namespace std;

char a[110][110];
int ne[8][2]= {{1,0},{0,1},{-1,0},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
int n,m,cnt=0;
void dfs(int x,int y)
{
a[x][y]='U';
for(int i=0; i<8; i++)
{
int nx=x+ne[i][0],ny=y+ne[i][1];
if(nx<=0||nx>=n+1||ny<=0||ny>=m+1||a[nx][ny]!='W') continue;
dfs(nx,ny);
}
}

int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>a[i][j];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(a[i][j]=='W')
{
dfs(i,j);
cnt++;
}
}
}
cout<<cnt;
return 0;
}

D-纪念品

思路：完全背包

我们进行 t-1 轮完全背包:

把今天手里的钱当做背包的容量，

把商品今天的价格当成它的消耗,

把商品明天的价格当做它的价值，

每一天结束后把总钱数加上今天赚的钱，直接写背包模板即可。

另： 在这道题中，我们可以当天买当天卖，所以不必考虑跨天的买卖，只需考虑当天的即可。

定义f数组，f[i]为用 i 元钱去购买商品所能盈利的最大值（不含成本）

定义price数组，price[i][j]为第i件商品第j天的价格。

转移方程： f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);

始终保证m为我们目前手里的总钱数，所以最后输出m即可。

#include <bits/stdc++.h>
using namespace std;
int n, m, t, price[101][101], f[10001];
int main()
{
cin >> t >> n >> m;
for(int i = 1; i <= t; i++)
for(int j = 1; j <= n; j++)
cin >> price[j][i];
//读入每种商品每天的价格
for(int k = 1; k < t; k++)
{
memset(f, 0, sizeof f);//每轮开始前都要将f数组清零（如果不会用memset可以写循环）
for(int i = 1; i <= n; i++)
for(int j = price[i][k]; j <= m; j++)//完全背包,正着循环
f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
m += f[m];//加上盈利的钱，进入下一轮买卖
}
cout << m;
return 0;
}