【AcWing】蓝桥杯辅导课-二分与前缀和

目录

二分

数的范围

数的三次方跟

机器人跳跃问题

四平方和

分巧克力

前缀和

前缀和

子矩阵的和

K倍区间

激光炸弹

二分

数的范围

789. 数的范围 - AcWing题库

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 10;
  5.  
  6. int n, q, k, a[N];
  7.  
  8. int main()
  9. {
  10.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  11.     cin >> n >> q;
  12.     for(int i = 0;i < n;i ++) cin >> a[i];
  13.     while(q --)
  14.     {
  15.         cin >> k;
  16.         int l = 0, r = n - 1;
  17.         // 先找左端点
  18.         while(l < r)
  19.         {
  20.             int mid = l + r >> 1;
  21.             if(a[mid] < k) l = mid + 1;
  22.             else r = mid;
  23.         }
  24.         if(a[l] != k) cout << "-1 -1" << '\n';
  25.         else
  26.         {
  27.             cout << l << ' ';
  28.             l = 0, r = n - 1;
  29.             while(l < r)
  30.             {
  31.                 int mid = l + r + 1 >> 1;
  32.                 if(a[mid] > k) r = mid - 1;
  33.                 else l = mid;
  34.             }
  35.             cout << r << '\n';
  36.         }
  37.     }
  38.     return 0;
  39. }

数的三次方跟

790. 数的三次方根 - AcWing题库

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  8.     double n; cin >> n;
  9.     double l = -10000, r = 10000;
  10.     while(r - l > 1e-8)
  11.     {
  12.         double mid = (l + r) / 2;
  13.         if(mid * mid * mid < n) l = mid;
  14.         else r = mid;
  15.     }
  16.     cout << fixed << setprecision(6) << l << '\n';
  17.     return 0;
  18. }

机器人跳跃问题

730. 机器人跳跃问题 - AcWing题库

这道题是一个求最值的问题，我们在求最值时，通常是二分->dfs->dp->贪心。
二分的重点是看是否有二段性。在很多情况下，二分不仅仅只有二段性，还有单调性，但是没有单调性也可能可以使用二分做，只要有二段性即可，有单调性就一定有二段性。

H(k + 1) > E    ->  E - (H(k + 1) - E) = 2*E - H(k + 1)

H(k + 1) <= E  ->  E + E - H(k + 1)  = 2*E - H(k + 1)

会发现无论当前剩余能量大于、小于或等于下一个建筑的能力值，新能量值的计算方法是一样的 

有了这个计算公式之后。假设起始的最低能力值是E0，也就是说2*E0 - H(k + 1)始终能够大于等于0，若E >= E0，则一定有2*E0 - H(k + 1) >= 0；若E < E0，则一定有2*E0 - H(k + 1) < 0
这样我们就找到了二段性，即这道题可以使用二分来解

如何验证当前的mid是否可行呢？
只需要使用当前的mid去递推一遍，看中间是否有小于0的即可

刚开始二分时，l和r分别要是多少呢？
当数组中全是0时，可以取到初始能量值的最小值，也就是0，所以l从0开始
假设数组中的最大值是hm，当我们当前剩余能力E>=hm时，可以利用放缩
跳到下一个建筑物后剩余能量 = E + E - H(k + 1) >= E + hm - H(k + 1) >= E
也就是说，当某一时刻剩余能量大于等于数组H的最大值时，就不需要计算了，因为往后
2*E - H(k + 1)一定大于等于E，也就是大于等于0。所以，r直接从hm开始即可。

因为h[i]的最大值是10^5，而当前剩余能量E只要大于hm就可以不需要计算，所以2*E一定不会超过int的范围，所以不需要开long long

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 10;
  5.  
  6. int h[N], n, m;
  7.  
  8. bool check(int mid)
  9. {
  10.     for(int i = 1;i <= n;i ++)
  11.     {
  12.         mid = 2 * mid - h[i];
  13.         if(mid >= m) return true; // 当大于数组最大值时返回true
  14.         if(mid < 0) return false;
  15.     }
  16.     return true;
  17. }
  18.  
  19. int main()
  20. {
  21.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  22.     cin >> n;
  23.     for(int i = 1;i <= n;i ++) 
  24.     {
  25.         cin >> h[i];
  26.         if(h[i] > m) m = h[i];
  27.     }
  28.     int l = 0, r = m;
  29.     while(l < r)
  30.     {
  31.         int mid = (l + r) / 2;
  32.         if(check(mid)) r = mid;
  33.         else l = mid + 1;
  34.     }
  35.     cout << l << '\n';
  36.     return 0;
  37. }

四平方和

AcWing 1221. 四平方和 - AcWing

这道题很容易就能想到暴力做法，枚举a，b，c三个数，再直接计算出d，因为n的最大值是5*10^6，所以a，b，c，d的最大值约为2232，时间复杂度是高于10^8，所以不行。

由于时间复杂度是原因，最多只能枚举两个数，此时可以考虑空间换时间。我们先两层for循环枚举出c^2+d^2，然后将c^2+d^2的结果保存起来，完成之后，再来两层for循环枚举a^2+b^2，然后根据目标值n及a^2+b^2的结果，去找是否有对于的c^2+d^2。判断一个数在一个集合中是否出现过，就可以使用哈希或者二分。

注意：一个数的表示方法是不唯一的，这道题要求我们输出字典序最小的一组，在循环过程中，a和b，c和d都是按照字典序最小排的，但是两者的组合不一定是按照字典序的组合来排序的，所以，我们在存储c^2+d^2时，不能只存储平方和，还需要将c和d都存储起来，直接存储成一个结构体即可

二分

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 2500010;
  8.  
  9. struct Sum
  10. {
  11.     int s, c, d;
  12.     bool operator< (const Sum &t)const // 重载，因为二分要对其进行排序
  13.     {
  14.         if (s != t.s) return s < t.s;
  15.         if (c != t.c) return c < t.c;
  16.         return d < t.d;
  17.     }
  18. }sum[N];
  19.  
  20. int n, m;
  21.  
  22. int main()
  23. {
  24.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  25.     
  26.     cin >> n;
  28.     for (int c = 0; c * c <= n; c ++ )
  29.         for (int d = c; c * c + d * d <= n; d ++ )
  30.             sum[m ++ ] = {c * c + d * d, c, d};
  31.  
  32.     sort(sum, sum + m);
  33.  
  34.     for (int a = 0; a * a <= n; a ++ )
  35.         for (int b = 0; a * a + b * b <= n; b ++ )
  36.         {
  37.             int t = n - a * a - b * b;
  38.             int l = 0, r = m - 1;
  39.             while (l < r) // 查找c^2+d^2中是否有与t相等的
  40.             {
  41.                 int mid = l + r >> 1;
  42.                 if (sum[mid].s >= t) r = mid;
  43.                 else l = mid + 1;
  44.             }
  45.             if (sum[l].s == t)
  46.             {
  47.                 cout << a << ' ' << b << ' ' << sum[l].c << ' ' << sum[l].d << '\n'; 
  48.                 return 0;
  49.             }
  50.         }
  51.  
  52.     return 0;
  53. }

哈希表

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int N = 5e6 + 10;
  5.  
  6. bool flag[N];
  7. int C[N], D[N];
  8.  
  9. int n, m;
  10.  
  11. int main() 
  12. {
  13.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  14.     
  15.     cin >> n;
  17.     for (int c = 0; c * c <= n; c++)
  18.         for (int d = c; c * c + d * d <= n; d++) 
  19.         {
  20.             int t = c * c + d * d;
  21.             if (!flag[t]) 
  22.             {
  23.                 C[t] = c, D[t] = d;
  24.                 flag[t] = true;
  25.             }
  26.         }
  27.  
  28.     for (int a = 0; a * a <= n; a++)
  29.         for (int b = 0; a * a + b * b <= n; b++) 
  30.         {
  31.             int t = n - a * a - b * b;
  32.             if (flag[t]) 
  33.             {
  34.                 cout << a << ' ' << b << ' ' << C[t] << ' ' << D[t] << '\n';
  35.                 return 0;
  36.             }
  37.         }
  38.  
  39.     return 0;
  40. }

分巧克力

1227. 分巧克力 - AcWing题库


这道题是很容易找到二段性的，在1到x之间都是能够切出来的，在x+1到1e5之间是切不出来的，而我们要求的答案就是x，所以此时可以直接使用二分

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 10;
  5.  
  6. int n, k, h[N], w[N];
  7.  
  8. bool check(int mid)
  9. {
  10.     // 看所有的巧克力中，能否切下k个边长为mid的正方形
  11.     int sum = 0;
  12.     for(int i = 0;i < n;i ++)
  13.     {
  14.         sum += (w[i] / mid) * (h[i] / mid);//每一大块可以分成的边长为 mid 的巧克力数量
  15.         if (sum >= k) return true;//大于要求数量，返回真
  16.     }
  17.     return false;
  18. }
  19.  
  20. int main()
  21. {
  22.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  23.     cin >> n >> k;
  24.     int l = 1, r = 1e5;
  25.     for(int i = 0;i < n;i ++) cin >> h[i] >> w[i];
  26.     while(l < r)
  27.     {
  28.         int mid = l + r + 1 >> 1;
  29.         if(check(mid)) l = mid;
  30.         else r = mid - 1;
  31.     }
  32.     cout << l << '\n';
  33.     return 0;
  34. }

前缀和

前缀和

795. 前缀和 - AcWing题库

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 10;
  5.  
  6. int n, m, l, r, a[N], s[N];
  7.  
  8. int main()
  9. {
  10.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  11.     cin >> n >> m;
  12.     for(int i = 1;i <= n;i ++) cin >> a[i];
  13.     for(int i = 1;i <= n;i ++) s[i] = s[i - 1] + a[i];
  14.     while(m --)
  15.     {
  16.         cin >> l >> r;
  17.         cout << s[r] - s[l - 1] << '\n';
  18.     }
  19.     return 0;
  20. }

子矩阵的和

796. 子矩阵的和 - AcWing题库

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 1010;
  5.  
  6. int n, m, q, x1, x2, y1, y2, a[N][N], s[N][N];
  7.  
  8. int main()
  9. {
  10.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  11.     cin >> n >> m >> q;
  12.     for(int i = 1;i <= n;i ++)
  13.         for(int j = 1;j <= m;j ++)
  14.         {
  15.             cin >> a[i][j];
  16.             s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
  17.         }
  18.     while(q --)
  19.     {
  20.         cin >> x1 >> y1 >> x2 >> y2;
  21.         cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << '\n';
  22.     }
  23.     return 0;
  24. }

K倍区间

1230. K倍区间 - AcWing题库

这道题最容易想到的就是直接暴力枚举区间

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5.  
  6. const int N = 1e5 + 10;
  7.  
  8. int n, k, a[N];
  9. LL ans;
  10.  
  11. int main()
  12. {
  13.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  14.     cin >> n >> k;
  15.     for(int i = 1;i <= n;i ++) cin >> a[i];
  16.     for(int r = 1;r <= n;r ++)
  17.         for(int l = 1;l <= r;l ++)
  18.         {
  19.             int t = 0;
  20.             for(int i = l;i <= r;i ++) t += a[i];
  21.             if(t % k == 0) ans ++;
  22.         }
  23.     cout << ans << '\n';
  24.     return 0;
  25. }

此时时间复杂度是O(N^3)，N的最大值是10^5，会超时
此时我们会发现，最里面一层循环是求下标为[l, r]这个区间的和，所以可以使用前缀和来进行优化

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5.  
  6. const int N = 1e5 + 10;
  7.  
  8. int n, k;
  9. LL s[N], ans;
  10.  
  11. int main()
  12. {
  13.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  14.     cin >> n >> k;
  15.     for(int i = 1;i <= n;i ++)
  16.     {
  17.         cin >> s[i];
  18.         s[i] += s[i - 1];
  19.     }
  20.     for(int r = 1;r <= n;r ++)
  21.         for(int l = 0;l < r;l ++)
  22.         {
  23.             if((s[r] - s[l]) % k == 0) ans ++;
  24.         }
  25.     cout << ans << '\n';
  26.     return 0;
  27. }

此时时间复杂度优化到了O(N^2)，还是不行。
我们看两层循环中，里面的那一层循环，这一层循环的意思就是当区间右端点r固定时，左区间端点为0 - r-1中，有几个s[l] % k的余数与s[r] % k的余数相同的。所以，我们此时可以去掉这一层循环，维护一个cnt数组，cnt[i]表示r之前的前缀和中%k余数为i的数的个数

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5.  
  6. const int N = 1e5 + 10;
  7.  
  8. int n, k;
  9. LL s[N], cnt[N], ans;
  10.  
  11. int main()
  12. {
  13.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  14.     cin >> n >> k;
  15.     for(int i = 1;i <= n;i ++)
  16.     {
  17.         cin >> s[i];
  18.         s[i] += s[i - 1];
  19.     }
  20.     cnt[0] = 1; // cnt[0]中存的是s[]中等于0的数的个数 由于s[0] = 0 所以最初等于0的有1个数 所以cnt[0] = 1
  21.     for(int i = 1;i <= n;i ++)
  22.     {
  23.         ans += cnt[s[i] % k];
  24.         cnt[s[i] % k] ++;
  25.     }
  26.     cout << ans << '\n';
  27.     return 0;
  28. }

激光炸弹

99. 激光炸弹 - AcWing题库

这道题的思路很简单，就是先计算出前缀和，然后取出R*R的区间，取值的最大值即可。唯一需要注意的就是R可能很大，需要防止数组越界

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int N = 5010;
  5.  
  6. int cnt, n, r, x, y, w, s[N][N]; // s数组存放的是前缀和
  7. long long ans;
  8.  
  9. int main()
  10. {
  11.     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  12.     cin >> cnt >> r;
  13.     if(r > 5001) r = 5001; // r再大是没有意义的，为了防止数组越界，取5001与r的最小值
  14.     int n = r, m = r; // n表示的是用到的最大的横坐标与r的较大值，m是纵坐标
  15.     while (cnt--)
  16.     {
  17.         cin >> x >> y >> w;
  18.         x++, y++;
  19.         if (x > n) n = x;
  20.         if (y > m) m = y;
  21.         s[x][y] += w;
  22.     }
  23.     // 计算前缀和
  24.     for (int i = 1; i <= n; i++)
  25.         for (int j = 1; j <= m; j++)
  26.         {
  27.             s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
  28.         }
  29.     // 取前缀和中R*R区间的最大值
  30.     for (int i = r; i <= n; i++)
  31.         for (int j = r; j <= m; j++)
  32.         {
  33.             int t = s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r];
  34.             if (t > ans) ans = t;
  35.         }
  36.     cout << ans << '\n';
  37.     return 0;
  38. }

注：本文转载自blog.csdn.net的while(77)的文章"https://blog.csdn.net/2301_80277275/article/details/145431127"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！