当前位置：首页 > article >正文

蓝桥杯刷题冲刺 | 倒计时24天

article 2024/12/27 12:05:00

作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

文章目录

1.修剪灌木
2.统计子矩阵

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;
}