1.修剪灌木

题目

链接：修剪灌木 - 蓝桥云课 (lanqiao.cn)

找到一个蓝桥官网相比acwing刷题的优点：蓝桥官网可以看ac的占比
爱丽丝要完成一项修剪灌木的工作。

有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

输入格式

一个正整数 N, 含义如题面所述。

输出格式

输出 N 行, 每行一个整数, 第 i 行表示从左到右第 i 棵树最高能长到多高。

样例输入
```
3
```
样例输出
```
4
2
4
```

第一次

#include<bits/stdc++.h>
using namespace std;const int N=1e4+10;
int a[N],m[N];int main()
{int n;scanf("%d",&n);int k=pow(n,2)+2;while(k>0){for(int i=0;i<n;i++){for(int j=0;j<n;j++)  //每天长1{a[j]++;m[j]=max(m[j],a[j]);} a[i]=0;  //轮到的灌木，变0}for(int i=n-2;i>=1;i--)  //边界条件处理好{for(int j=0;j<n;j++){a[j]++;m[j]=max(m[j],a[j]);}a[i]=0;}k-=2;}for(int i=0;i<n;i++)printf("%d\n",m[i]);return 0;
}

简单暴力，只能 ac 30%

我感觉每次所有数组元素+1，可以优化成差分

第二次

#include<bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cout<<max(n-i,i-1)*2<<endl; //找规律：当剪刀离灌木最远的时候，长的很高，然后返回马上要剪它的时候，最高，两倍高度；画图可知，到两个端点返回来的时候，最高}return 0;
}

反思

纯纯规律题，感觉错了

发散性思维，在做蓝桥杯的时候，遇到这种数的题，先静下心来，找找规律

2.统计子矩阵

题目

链接： 4405. 统计子矩阵 - AcWing题库
给定一个 N×M 的矩阵 A，请你统计有多少个子矩阵 (最小 1×1，最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K?

输入格式

第一行包含三个整数 N,M 和 K。

之后 N 行每行包含 M 个整数，代表矩阵 A。

输出格式

一个整数代表答案。

数据范围

对于 30% 的数据，N,M≤20，
对于 70%的数据，N,M≤100，
对于 100% 的数据，1≤N,M≤500;0≤Aij≤1000;1≤K≤2.5× $10^8$ 。

输入样例：
```
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
```
输出样例：
```
19
```
样例解释

满足条件的子矩阵一共有 19，包含：
- 大小为 1×1 的有 10 个。
- 大小为 1×2 的有 3 个。
- 大小为 1×3 的有 2 个。
- 大小为 1×4 的有 1 个。
- 大小为 2×1 的有 3 个。

第一次

#include<bits/stdc++.h>
using namespace std;const int N=510;
int s[N][N];
int n,m,k;int sum(int dx,int dy,int x,int y)
{int res=0;res=s[x][y]-s[x-dx][y]-s[x][y-dy]+s[x-dx][y-dy];return res;
}int main()
{int cnt=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&s[i][j]);s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];  //前缀和}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){for(int l=1;l<=n;l++)  // l,r 表示 每个小矩阵，右下角的元素for(int r=1;r<=m;r++){if(sum(i,j,l,r)<=k) cnt++;}}cout<<cnt;return 0;
}

答案错误，样例都过不了，目前还没有找出来 bug

正确题解 ->前缀和+双指针

思路

前缀和把数组存起来

用四个指针把整个矩阵分成一小块一小块的

左右使用 i，j 指针，上下使用 u，d 指针

#include<bits/stdc++.h>
using namespace std;const int N=510;
int s[N][N];
int n,m,k;int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){scanf("%d",&s[i][j]);s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];}//i表示左边界，j表示右边界，u 表示上边界，d表示下边界long long ans=0;for(int i=1;i<=m;i++)for(int j=i;j<=m;j++){for(int u=1,d=1;d<=n;d++){while(u<=d&&s[d][j]-s[u-1][j]-s[d][i-1]+s[u-1][i-1]>k) u++; //u++ 表示上边界下移，区间变小，递减if(u<=d) ans+=d-u+1;  //表示这段区间的矩阵，满足条件}}cout<<ans;return 0;
}