蓝桥杯---第二讲---二分与前缀和

╰+攻爆jí腚メ 2024-02-26 04:15 12阅读 0赞

#### 文章目录 ####

*  前言
 *  Ⅰ. 数的范围
 *   *  0x00 算法思路
     *  0x00 代码书写
 *  Ⅱ. 数的三次方根
 *   *  0x00 算法思路
     *  0x01代码书写
 *  Ⅲ. 前缀和
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  Ⅳ. 子矩阵的和
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  Ⅴ. 机器人跳跃问题
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  Ⅵ. 四平方和
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  Ⅶ. 分巧克力
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  Ⅷ. 激光炸弹
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  Ⅸ. K倍区间
 *   *  0x00 算法思路
     *  0x01 代码书写
 *  总结

--------------------

## 前言 ##

本篇博客主要打卡记录博主学习蓝桥杯C++AB组辅导课的习题第一章节的题目。

--------------------

## Ⅰ. 数的范围 ##

### 0x00 算法思路 ###

详细可以看下这一篇博客，详细讲解了二分算法知识  
[【algorithm】算法基础课—二分查找算法（附笔记 | 建议收藏）][algorithm_ _]

### 0x00 代码书写 ###

#include <iostream>
    
    using namespace std;
    
    const int maxn = 100005;
    int n, q, x, a[maxn];
    
    int main() 
    {
        
        scanf("%d%d", &n, &q);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        while (q--) 
        {
        
            scanf("%d", &x);
            int l = 0, r = n - 1;
            while (l < r) 
            {
        
                int mid = l + r >> 1;
                if (a[mid] < x)  l = mid + 1;
                else    r = mid;
            }
            if (a[l] != x) 
            {
        
                printf("-1 -1\n");
                continue;
            }
            int l1 = l, r1 = n;
            while (l1 + 1 < r1) 
            {
        
                int mid = l1 + r1 >> 1;
                if (a[mid] <= x)  l1 = mid;
                else    r1 = mid;
            }
            printf("%d %d\n", l, l1);
        }
        return 0;
    }

## Ⅱ. 数的三次方根 ##

### 0x00 算法思路 ###

**1.迭代的思路，就是无脑迭代100次就可.  
2.根据题目法写的方法，其实这个就是while(r-l>谁就行啦).**

### 0x01代码书写 ###

#include<iostream>
    #include<cstdio>
    
    using namespace std;
    
    int main()
    {
        
        double n;
        scanf("%lf",&n);
        double l = -100000, r = 100000;
        while(r - l > 0.00000001)
        {
        
            double mid = (l + r) / 2;
            if(mid * mid * mid >= n) r = mid;
            else l = mid;
        }
        printf("%.6lf",l);
        
        return 0;
    }

## Ⅲ. 前缀和 ##

### 0x00 算法思路 ###

**详细知识看算法基础课笔记 前缀和与差分**  
[【algorithm】认真讲解前缀和与差分 (图文搭配)][algorithm_]

### 0x01 代码书写 ###

#include<iostream>
    
    using namespace std;
    
    int n,m;
    int sum[100010];
    
    int main()
    {
        
        cin>>n>>m;
    
        for(int i=1;i<=n;i++)
        {
        
            int tmp;
            cin>>tmp;
            sum[i]=sum[i-1]+tmp;
        }
    
        while(m--)
        {
        
            int l,r;
            cin>>l>>r;
            cout<<sum[r]-sum[l-1]<<endl;
        }
        return 0;
    }

## Ⅳ. 子矩阵的和 ##

### 0x00 算法思路 ###

**详细知识看算法基础课笔记 前缀和与差分**  
[【algorithm】认真讲解前缀和与差分 (图文搭配)][algorithm_]

### 0x01 代码书写 ###

#include<iostream>
    
    using namespace std;
    
    int n,m,q;
    int s[1010][1010];
    
    int main()
    {
        
        cin>>n>>m>>q;
    
        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
        
            cin>>s[i][j];
        }
    
        for(int i=1;i<=n;i++)
        {
        
            for(int j=1;j<=m;j++)
            {
        
                s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            }
        }
    
        while(q--)
        {
        
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
        }
    
        return 0;
    }

## Ⅴ. 机器人跳跃问题 ##

### 0x00 算法思路 ###

这一道题主要考查了二分答案的算法，通过物理计算得到不论是从低到高，还是从高到低都是：e = 2 \* e - h\[i\] 所以我们假设有一个临界点 E0 满足 0 ~ E0 能量是不满足的，E0 ~ 0x3f3f3f3f 是满足的，就可以使用y总的二分模板了。

### 0x01 代码书写 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n;
    int h[N];
    
    bool check(int e)
    {
        
        for(int i = 1 ; i <= n ; ++ i)
        {
        
            e = e * 2 - h[i];
            if(e >= 1e5) return true;//防止爆int
            else if(e < 0) return false;    
        }
        return true;
    }
    
    int main()
    {
        
        cin >> n;
        for(int i = 1 ; i <= n ; ++ i) cin >> h[i];
    
        int l = 0 , r = 1e5;
        while(l < r)
        {
        
            int mid = l + r >> 1;
    
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        cout << r << endl;
    
        return 0;
    }

## Ⅵ. 四平方和 ##

### 0x00 算法思路 ###

这一道题我没学具体的算法思路，感觉不如暴力来的实在，确信哈哈哈

### 0x01 代码书写 ###

#include<iostream>
    #include<cmath>
    
    using namespace std;
    
    int n;
    int a,b,c,d;
    
    int main()
    {
        
        scanf("%d",&n);
    
        for(int a=0;a*a<=n;a++)
        {
        
            for(int b=a;a*a+b*b<=n;b++)
            {
        
                for(int c=b;a*a+b*b+c*c<=n;c++)
                {
        
                    int t=n-a*a-b*b-c*c;
                    int d=sqrt(t);
                    if(d*d==t)
                    {
        
                        printf("%d %d %d %d\n",a,b,c,d);
                        return 0;
                    }
                }
            }
        }
    
        return 0;
    }

## Ⅶ. 分巧克力 ##

### 0x00 算法思路 ###

这道题主要考查了二分算法，主要是对于一块大巧克力进行分割，思考的到，当分割的块数越多，边长就越短，块数越少，边长就越大，所以肯定可以有一个临界点 mid 可以使得刚好的块数 满足要求 刚好 >= k 块 如果边长 在 Left ~ mid 之间的话 就是边长很大 所以check函数可以判断这个， 如果在 mid ~ Right 之间的话 肯定是都满足要求的。 最后套用y总的算法模板即可

### 0x01 代码书写 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 100010;
    
    int n,k;
    int h[N],w[N];
    
    bool check(int mid)
    {
        
    	int res = 0;
    	for(int i = 0 ; i < n ; ++ i)
    	{
        
    		res += (long long)h[i] / mid * (w[i] / mid);
    		if(res >= k) return true;
    	}
    	return false;
    }
    
    int main()
    {
        
    	cin >> n >> k;
    	
    	for(int i = 0 ; i < n ; ++ i) cin >> h[i] >> w[i];
    	
    	int l = 1 , r = 1e5;
    	
    	while(l < r)
    	{
        
    		int mid = l + r + 1 >> 1;
    		if(check(mid)) l = mid;
    		else r = mid - 1;
    	}
    	cout << r << endl;
    	
    	return 0;
    }

## Ⅷ. 激光炸弹 ##

### 0x00 算法思路 ###

贴一个acwing的图片 ： 链接 ： [AcWing 99. 激光炸弹第一题解][AcWing 99.]  
![在这里插入图片描述][349225a7e5ec3cccfe66d4ac686a0744.png_pic_center]  
![在这里插入图片描述][09ca0fff9855a145fe891352de683361.png_pic_center]

### 0x01 代码书写 ###

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 5010;
    int cnt,r;
    int s[N][N];
    int n,m;
    
    int main()
    {
        
        cin >> cnt >> r;
        r=min(r,5001);
        n = m = r;
        
        while(cnt --)
        {
        
            int x,y,w;
            cin >> x >> y >> w;
            x ++;
            y ++;
            n = max(x,n);
            m = max(y,m);
            
            s[x][y] += w;
        }
        
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= m ;++ j)// 构造二维前缀和
                s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1];
                
        int res = 0;      
        
        for(int i = r; i <= n ;++ i)
        {
        
            for(int j = r; j <= m ;++ j)//根据二维前缀和进行答案计算
            {
        
                res = max(res, s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
            }
        }
        cout << res << '\n';
        return 0;
    }

## Ⅸ. K倍区间 ##

### 0x00 算法思路 ###

这一道题我只是用了 前缀和做优化，感觉我考试的时候也想不到y总的算法思路，呜呜呜呜呜…

### 0x01 代码书写 ###

#include<iostream>
    
    using namespace std;
    
    int n,k;
    int a[100010];
    int sum[100010];
    
    int main()
    {
        
        cin>>n>>k;
    
        for(int i=1;i<=n;i++) cin>>a[i];
    
        int ans=0,i=0;
        for(i=1;i<=n;i++)
        {
        
            sum[i]=sum[i-1]+a[i];
        }
    
        for(int j=1;j<=i;j++)
        {
        
            for(int s=j+1;s<=i;s++)
            {
        
                if((sum[s]-sum[j])%k==0) // 前缀和优化
                {
        
                    ans++;
                }
                else continue;
            }
        }
        cout<<ans;
        return 0;
    }

--------------------

## 总结 ##

本篇博客主要讲解了前缀和 和 二分算法的知识，前面四道题都是算法基础课 的模板题，后面几道题才是真正考查这两个算法的真实难度，开始我也觉得很难很难，但是认真学习完发现其实还是可以学会的，所以请热爱 请认真学习，总会学好，总会获得不小的进步的，加油吧夏目浅石.

[algorithm_ _]: https://congfen214.blog.csdn.net/article/details/128733081
[algorithm_]: https://congfen214.blog.csdn.net/article/details/128772576
[AcWing 99.]: https://www.acwing.com/solution/content/10116/
[349225a7e5ec3cccfe66d4ac686a0744.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/4640bb9cdde140ae95e505e31c844604.png
[09ca0fff9855a145fe891352de683361.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/dcae949536df462fac7e7fadc06ef4b3.png