【蓝桥杯逐日一题】3.25

 

🏝️专栏： 【蓝桥杯备篇】
🌅主页： f狐o狸x

“OJ超时不是尽头，是算法在提示你该优化时间复杂度了！”

---

目次

3.25 差分数组
一、一维差分
        标题链接：
        标题形貌：
        解题思绪：
        解题代码：
二、海底高铁
        标题链接：
        标题形貌：
        解题思绪：
        解题代码：
三、二维差分
        标题链接：
        标题形貌：
        解题思绪：
        解题代码：
四、地毯
        标题链接：
        标题形貌：
        解题思绪：
        解题代码：

---

3.25 差分数组

        我们直接用一道题来相识差分数组吧
一、一维差分

        标题链接：

        【模板】差分
        标题形貌：

        解题思绪：

        照旧可以用暴力摆列来搞定，我们把整个数组遍历一遍，再把对应位置加上x就行了，但是如许绝对是会超时长滴，否则我干嘛用这个例题？
        对于类似的题，我们就可以用差分算法，和前缀和数组类似，我们必要预处理惩罚一个差分数组出来

        这个数组的利益就是当你要在 l ~ r 的区间加上 x 的时间（图中用2~5）来表现，就只必要在差分数组中的 l 位置加上 x ，r + 1 位置减去 x ，再还原为原数组就行

            也就是：a[ l ] += x; a[ r + 1 ] -= x;
          此时尚有人要问：煮波煮波，那怎么还原数组呢？着实把差分数组做一个前缀和运算即可还原 证明如下：

        解题代码：

1. #include <iostream>
2. using namespace std;
4. typedef long long LL;
6. const int N = 1e5 + 10;
8. LL a[N];
10. int n, m;
12. int main()
13. {
14.     cin >> n >> m;
15.     // 利用差分的性质预处理差分数组
16.     for(int i = 1; i <= n; i++)
17.     {
18.         LL x;cin >> x;
19.         a[i] += x;
20.         a[i + 1] -= x;
21.     }
22.     // m次操作
23.     while(m--)
24.     {
25.         LL l, r, x; cin >> l >> r >> x;
26.         a[l] += x;
27.         a[r + 1] -= x;
28.     }
29.     // 利用前缀和还原数组
30.     for(int i = 1; i <= n; i++)
31.     {
32.         a[i] = a[i - 1] + a[i];
33.         cout << a[i] << " ";
34.     }
36.    
37.     return 0;
38. }

复制代码

二、海底高铁

        标题链接：

        P3406 海底高铁
        标题形貌：

        解题思绪：

        这里我们只必要知道这个人每段铁路一共坐了反复，再判断是直接买票划算照旧买卡划算，末了累加输出即可
        解题代码：

1. #include <iostream>
3. using namespace std;
5. const int N = 1e5 + 10;
7. typedef long long LL;
9. LL f[N];
11. int n, m;
13. int main()
14. {
15.         cin >> n >> m;
16.         int l, r; cin >> l;
17.         // 利用差分记录每段铁路经过的次数
18.         for (int i = 2; i <= m; i++)
19.         {
20.                 cin >> r;
21.                 if (l <= r) f[l] += 1, f[r] -= 1;
22.                 else f[r] += 1, f[l] -= 1;
23.                 l = r;
24.         }
25.         // 还原数组
26.         for (int i = 1; i <= n; i++)
27.         {
28.                 f[i] = f[i - 1] + f[i];
29.         }
31.         LL ret = 0;
32.         for(int i = 1; i < n; i++)
33.         {
34.                 LL a, b, c; cin >> a >> b >> c;
35.                 ret += min(a * f[i], c + b * f[i]);
36.         }
37.         cout << ret << endl;
39.         return 0;
40. }

复制代码

三、二维差分

        标题链接：

        【模板】二维差分
        标题形貌：

        解题思绪：

        如图所示我们必要对以下结果数组举行利用：

   f[x1][y1] + k
  f[x2 + 1][y1] - k
  f[x1][y2 + 1] - k
  f[x2 + 1][y2 + 1] - k
           如许我们累加起来以后就可以得到二维数组中区间+k的利用
        解题代码：

1. #include <iostream>
3. using namespace std;
5. typedef long long LL;
7. const int N = 1010;
9. LL f[N][N];
11. int n, m, q;
13. void insert(int x1, int y1, int x2, int y2, int x)
14. {
15.     f[x1][y1] += x;
16.     f[x2 + 1][y1] -= x;
17.     f[x1][y2 + 1] -= x;
18.     f[x2 + 1][y2 + 1] += x;
19. }
21. int main()
22. {
23.     cin >> n >> m >> q;
24.     // 预处理二维齐差分数组
25.     for(int i = 1; i <= n; i++)
26.     {
27.         for(int j = 1; j <= m; j++)
28.         {
29.             LL a; cin >> a;
30.             insert(i, j, i , j ,a);
31.         }   
32.     }
33.     while(q--)
34.     {
35.         LL x1, y1, x2, y2, a; cin >> x1 >> y1 >> x2 >> y2 >>a;
36.         insert(x1, y1, x2, y2, a);
37.     }
38.     for(int i = 1; i <= n; i++)
39.     {
40.         for(int j = 1; j <= m; j++)
41.         {
42.             f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
43.             cout << f[i][j] << " ";
44.         }
45.         cout << endl;
46.     }
47.    
48.     return 0;
49. }

复制代码

四、地毯

        标题链接：

        P3397 地毯
        标题形貌：

        

        解题思绪：

        这题着实就是把地毯对应的地区全加上一，末了再输出数组即可办理
        解题代码：
 

1. #include <iostream>
3. using namespace std;
5. const int N = 1010;
7. int f[N][N];
9. int n, m;
11. void insert(int x1, int y1, int x2, int y2, int a)
12. {
13.         f[x1][y1] += a;
14.         f[x2 + 1][y1] -= a;
15.         f[x1][y2 + 1] -= a;
16.         f[x2 + 1][y2 + 1] += a;
17. }
19. int main()
20. {
21.         cin >> n >> m;
22.         while (m--)
23.         {
24.                 int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
25.                 insert(x1, y1, x2, y2, 1);
26.         }
28.         for (int i = 1; i <= n; i++)
29.         {
30.                 for (int j = 1; j <= n; j++)
31.                 {
32.                         f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
33.                         cout << f[i][j] << " ";
34.                 }
35.                 cout << endl;
36.         }
38.         return 0;
39. }

复制代码

        本日就到这里吧，下一期我们将讲授二分算法~886~
        蓝桥杯选手一样寻常：
        睡醒→看题→看不懂→搜题解→抄代码→被卡常→怒删重写→提交→WA