南京林业大学实验与建设网站,潍坊网站空间,用友财务软件官方网站,模板兔自用主题WordPress作者#xff1a;指针不指南吗 专栏#xff1a;蓝桥杯倒计时冲刺 #x1f43e;马上就要蓝桥杯了#xff0c;最后的这几天尤为重要#xff0c;不可懈怠哦#x1f43e; 文章目录1.修剪灌木2.统计子矩阵1.修剪灌木 题目 链接#xff1a; 修剪灌木 - 蓝桥云课 (lanqiao.cn) 找… 作者指针不指南吗 专栏蓝桥杯倒计时冲刺 马上就要蓝桥杯了最后的这几天尤为重要不可懈怠哦 文章目录1.修剪灌木2.统计子矩阵1.修剪灌木 题目 链接 修剪灌木 - 蓝桥云课 (lanqiao.cn) 找到一个蓝桥官网相比acwing刷题的优点蓝桥官网可以看ac的占比 爱丽丝要完成一项修剪灌木的工作。 有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晩会修剪一棵灌 木, 让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始, 每天向右修剪一棵灌木。当修剪了最右侧的灌木后, 她会调转方向, 下一天开 始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。 灌木每天从早上到傍晩会长高 1 厘米, 而其余时间不会长高。在第一天的 早晨, 所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。 输入格式 一个正整数 N, 含义如题面所述。 输出格式 输出 N 行, 每行一个整数, 第 i 行表示从左到右第 i 棵树最高能长到多高。 样例输入 3样例输出 4
2
4第一次 #includebits/stdc.h
using namespace std;const int N1e410;
int a[N],m[N];int main()
{int n;scanf(%d,n);int kpow(n,2)2;while(k0){for(int i0;in;i){for(int j0;jn;j) //每天长1{a[j];m[j]max(m[j],a[j]);} a[i]0; //轮到的灌木变0}for(int in-2;i1;i--) //边界条件处理好{for(int j0;jn;j){a[j];m[j]max(m[j],a[j]);}a[i]0;}k-2;}for(int i0;in;i)printf(%d\n,m[i]);return 0;
}简单暴力只能 ac 30% 我感觉 每次 所有数组元素1可以优化成差分 第二次 #includebits/stdc.h
using namespace std;int main()
{int n;cinn;for(int i1;in;i){coutmax(n-i,i-1)*2endl; //找规律当剪刀离灌木最远的时候长的很高然后返回马上要剪它的时候最高两倍高度画图可知到两个端点返回来的时候最高}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×10810^8108 。 输入样例 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 个。 第一次 #includebits/stdc.h
using namespace std;const int N510;
int s[N][N];
int n,m,k;int sum(int dx,int dy,int x,int y)
{int res0;ress[x][y]-s[x-dx][y]-s[x][y-dy]s[x-dx][y-dy];return res;
}int main()
{int cnt0;scanf(%d%d%d,n,m,k);for(int i1;in;i)for(int j1;jm;j){scanf(%d,s[i][j]);s[i][j]s[i-1][j]s[i][j-1]-s[i-1][j-1]; //前缀和}for(int i1;in;i)for(int j1;jm;j){for(int l1;ln;l) // l,r 表示 每个小矩阵右下角的元素for(int r1;rm;r){if(sum(i,j,l,r)k) cnt;}}coutcnt;return 0;
}答案错误样例都过不了目前还没有找出来 bug 正确题解 -前缀和双指针 思路 前缀和 把数组 存起来 用 四个指针 把 整个矩阵 分成 一小块一小块的 左右使用 ij 指针上下 使用 ud 指针 #includebits/stdc.h
using namespace std;const int N510;
int s[N][N];
int n,m,k;int main()
{scanf(%d%d%d,n,m,k);for(int i1;in;i)for(int j1;jm;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 ans0;for(int i1;im;i)for(int ji;jm;j){for(int u1,d1;dn;d){while(uds[d][j]-s[u-1][j]-s[d][i-1]s[u-1][i-1]k) u; //u 表示上边界下移区间变小递减if(ud) ansd-u1; //表示这段区间的矩阵满足条件}}coutans;return 0;
}反思 及时复习前面的知识忘光了 遇到矩阵和优先想到前缀和然后有区间的移动问题使用双指针 定义变量之前先想清楚它的数据类型和范围
