0
0

蓝桥杯第九讲--差分【例/习题】

文章目录

前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第九讲：差分【例/习题】

本篇博客所包含习题有：
👊差分
👊差分矩阵

有关差分的内容细致讲解见博文：差分
有关差分的模板见博文：差分算法模板

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

差分

题目要求

题目描述：

输入一个长度为 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 的整数序列。

接下来输入 

  1.     m
  2.    
  3.   
  4.   
  5.    m
  6.   
  7.  
  8. m 个操作，每个操作包含三个整数 
  10.  
  11.   
  12.    
  13.     l
  14.    
  15.    
  16.     ,
  17.    
  18.    
  19.     r
  20.    
  21.    
  22.     ,
  23.    
  24.    
  25.     c
  26.    
  27.   
  28.   
  29.    l,r,c
  30.   
  31.  
  32. l,r,c，表示将序列中 
  34.  
  35.   
  36.    
  37.     [
  38.    
  39.    
  40.     l
  41.    
  42.    
  43.     ,
  44.    
  45.    
  46.     r
  47.    
  48.    
  49.     ]
  50.    
  51.   
  52.   
  53.    [l,r]
  54.   
  55.  
  56. [l,r] 之间的每个数加上 
  58.  
  59.   
  60.    
  61.     c
  62.    
  63.   
  64.   
  65.    c
  66.   
  67.  
  68. c。

请你输出进行完所有操作后的序列。

输入格式：

第一行包含两个整数 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 和 
  10.  
  11.   
  12.    
  13.     m
  14.    
  15.   
  16.   
  17.    m
  18.   
  19.  
  20. m。

第二行包含 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 个整数，表示整数序列。

接下来 

  1.     m
  2.    
  3.   
  4.   
  5.    m
  6.   
  7.  
  8. m 行，每行包含三个整数 
  10.  
  11.   
  12.    
  13.     l
  14.    
  15.    
  16.     ，
  17.    
  18.    
  19.     r
  20.    
  21.    
  22.     ，
  23.    
  24.    
  25.     c
  26.    
  27.   
  28.   
  29.    l，r，c
  30.   
  31.  
  32. l，r，c，表示一个操作。

输出格式：

共一行，包含 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 个整数，表示最终序列。

数据范围：

  1.     1
  2.    
  3.    
  4.     ≤
  5.    
  6.    
  7.     n
  8.    
  9.    
  10.     ,
  11.    
  12.    
  13.     m
  14.    
  15.    
  16.     ≤
  17.    
  18.    
  19.     100000
  20.    
  21.    
  22.     ,
  23.    
  24.   
  25.   
  26.    1≤n,m≤100000,
  27.   
  28.  
  29. 1≤n,m≤100000,
  32.  
  33.   
  34.    
  35.     1
  36.    
  37.    
  38.     ≤
  39.    
  40.    
  41.     l
  42.    
  43.    
  44.     ≤
  45.    
  46.    
  47.     r
  48.    
  49.    
  50.     ≤
  51.    
  52.    
  53.     n
  54.    
  55.    
  56.     ,
  57.    
  58.   
  59.   
  60.    1≤l≤r≤n,
  61.   
  62.  
  63. 1≤l≤r≤n,
  66.  
  67.   
  68.    
  69.     −
  70.    
  71.    
  72.     1000
  73.    
  74.    
  75.     ≤
  76.    
  77.    
  78.     c
  79.    
  80.    
  81.     ≤
  82.    
  83.    
  84.     1000
  85.    
  86.    
  87.     ,
  88.    
  89.   
  90.   
  91.    −1000≤c≤1000,
  92.   
  93.  
  94. −1000≤c≤1000,
  97.  
  98.   
  99.    
  100.     −
  101.    
  102.    
  103.     1000
  104.    
  105.    
  106.     ≤
  107.    
  108.   
  109.   
  110.    −1000≤
  111.   
  112.  
  113. −1000≤ 整数序列中元素的值 
  115.  
  116.   
  117.    
  118.     ≤
  119.    
  120.    
  121.     1000
  122.    
  123.   
  124.   
  125.    ≤1000
  126.   
  127.  
  128. ≤1000

输入样例：

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

输出样例：

3 4 5 3 4 2

思路分析

一维差分的模板题，对于差分你可以理解成为前缀和的逆运算，差分数组的构造方法为：

  1. s数组是差分数组,a数组是原数组
  2. s[0]=0, a[0]=0;
  3. s[1]= a[1]- a[0];
  4. s[2]= a[2]- a[1];...
  5. s[n]= a[n]- a[n -1];

令 

  1.     a
  2.    
  3.   
  4.   
  5.    a
  6.   
  7.  
  8. a数组在 
  10.  
  11.   
  12.    
  13.     [
  14.    
  15.    
  16.     l
  17.    
  18.    
  19.     ,
  20.    
  21.    
  22.     r
  23.    
  24.    
  25.     ]
  26.    
  27.   
  28.   
  29.    [l,r]
  30.   
  31.  
  32. [l,r] 的区间内加上一个数 
  34.  
  35.   
  36.    
  37.     c
  38.    
  39.   
  40.   
  41.    c
  42.   
  43.  
  44. c 可以用差分的思维：
  1. s[l]+= c;
  2. s[r +1]-= c;

然后对差分数组做一遍前缀和即可。

代码

  1. #include<cstdio>#include<cstring>#include<algorithm>usingnamespace std;constint N =100010;int a[N], s[N];intmain(){int n, m;scanf("%d%d",&n,&m);for(int i =1; i <= n; i ++)scanf("%d",&a[i]);// 处理差分数组for(int i =1; i <= n; i ++) s[i]= a[i]- a[i -1];while(m --){int l, r, c;scanf("%d%d%d",&l,&r,&c);
  2.         s[l]+= c, s[r +1]-= c;}for(int i =1; i <= n; i ++){
  3.         s[i]+= s[i -1];printf("%d ", s[i]);}return0;}

差分矩阵

题目要求

题目描述：

输入一个 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 行 
  10.  
  11.   
  12.    
  13.     m
  14.    
  15.   
  16.   
  17.    m
  18.   
  19.  
  20. m 列的整数矩阵，再输入 
  22.  
  23.   
  24.    
  25.     q
  26.    
  27.   
  28.   
  29.    q
  30.   
  31.  
  32. q 个操作，每个操作包含五个整数 
  34.  
  35.   
  36.    
  37.     
  38.      x
  39.     
  40.     
  41.      1
  42.     
  43.    
  44.    
  45.     ,
  46.    
  47.    
  48.     
  49.      y
  50.     
  51.     
  52.      1
  53.     
  54.    
  55.    
  56.     ,
  57.    
  58.    
  59.     
  60.      x
  61.     
  62.     
  63.      2
  64.     
  65.    
  66.    
  67.     ,
  68.    
  69.    
  70.     
  71.      y
  72.     
  73.     
  74.      2
  75.     
  76.    
  77.    
  78.     ,
  79.    
  80.    
  81.     c
  82.    
  83.   
  84.   
  85.    x_1,y_1,x_2,y_2,c
  86.   
  87.  
  88. x1​,y1​,x2​,y2​,c，其中 
  90.  
  91.   
  92.    
  93.     (
  94.    
  95.    
  96.     
  97.      x
  98.     
  99.     
  100.      1
  101.     
  102.    
  103.    
  104.     ,
  105.    
  106.    
  107.     
  108.      y
  109.     
  110.     
  111.      1
  112.     
  113.    
  114.    
  115.     )
  116.    
  117.   
  118.   
  119.    (x_1,y_1)
  120.   
  121.  
  122. (x1​,y1​) 和 
  124.  
  125.   
  126.    
  127.     (
  128.    
  129.    
  130.     
  131.      x
  132.     
  133.     
  134.      2
  135.     
  136.    
  137.    
  138.     ,
  139.    
  140.    
  141.     
  142.      y
  143.     
  144.     
  145.      2
  146.     
  147.    
  148.    
  149.     )
  150.    
  151.   
  152.   
  153.    (x_2,y_2)
  154.   
  155.  
  156. (x2​,y2​) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 

  1.     c
  2.    
  3.   
  4.   
  5.    c
  6.   
  7.  
  8. c。

请你将进行完所有操作后的矩阵输出。

输入格式：

第一行包含整数 

  1.     n
  2.    
  3.    
  4.     ,
  5.    
  6.    
  7.     m
  8.    
  9.    
  10.     ,
  11.    
  12.    
  13.     q
  14.    
  15.   
  16.   
  17.    n,m,q
  18.   
  19.  
  20. n,m,q。

接下来 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 行，每行包含 
  10.  
  11.   
  12.    
  13.     m
  14.    
  15.   
  16.   
  17.    m
  18.   
  19.  
  20. m 个整数，表示整数矩阵。

接下来 

  1.     q
  2.    
  3.   
  4.   
  5.    q
  6.   
  7.  
  8. q 行，每行包含 
  10.  
  11.   
  12.    
  13.     5
  14.    
  15.   
  16.   
  17.    5
  18.   
  19.  
  20. 5 个整数 
  22.  
  23.   
  24.    
  25.     
  26.      x
  27.     
  28.     
  29.      1
  30.     
  31.    
  32.    
  33.     ,
  34.    
  35.    
  36.     
  37.      y
  38.     
  39.     
  40.      1
  41.     
  42.    
  43.    
  44.     ,
  45.    
  46.    
  47.     
  48.      x
  49.     
  50.     
  51.      2
  52.     
  53.    
  54.    
  55.     ,
  56.    
  57.    
  58.     
  59.      y
  60.     
  61.     
  62.      2
  63.     
  64.    
  65.    
  66.     ,
  67.    
  68.    
  69.     c
  70.    
  71.   
  72.   
  73.    x_1,y_1,x_2,y_2,c
  74.   
  75.  
  76. x1​,y1​,x2​,y2​,c，表示一个操作。

输出格式：

共 

  1.     n
  2.    
  3.   
  4.   
  5.    n
  6.   
  7.  
  8. n 行，每行 
  10.  
  11.   
  12.    
  13.     m
  14.    
  15.   
  16.   
  17.    m
  18.   
  19.  
  20. m 个整数，表示所有操作进行完毕后的最终矩阵。

数据范围：

  1.     1
  2.    
  3.    
  4.     ≤
  5.    
  6.    
  7.     n
  8.    
  9.    
  10.     ,
  11.    
  12.    
  13.     m
  14.    
  15.    
  16.     ≤
  17.    
  18.    
  19.     1000
  20.    
  21.    
  22.     ,
  23.    
  24.   
  25.   
  26.    1≤n,m≤1000,
  27.   
  28.  
  29. 1≤n,m≤1000,
  32.  
  33.   
  34.    
  35.     1
  36.    
  37.    
  38.     ≤
  39.    
  40.    
  41.     q
  42.    
  43.    
  44.     ≤
  45.    
  46.    
  47.     100000
  48.    
  49.    
  50.     ,
  51.    
  52.   
  53.   
  54.    1≤q≤100000,
  55.   
  56.  
  57. 1≤q≤100000,
  60.  
  61.   
  62.    
  63.     1
  64.    
  65.    
  66.     ≤
  67.    
  68.    
  69.     
  70.      x
  71.     
  72.     
  73.      1
  74.     
  75.    
  76.    
  77.     ≤
  78.    
  79.    
  80.     
  81.      x
  82.     
  83.     
  84.      2
  85.     
  86.    
  87.    
  88.     ≤
  89.    
  90.    
  91.     n
  92.    
  93.    
  94.     ,
  95.    
  96.   
  97.   
  98.    1≤x_1≤x_2≤n,
  99.   
  100.  
  101. 1≤x1​≤x2​≤n,
  104.  
  105.   
  106.    
  107.     1
  108.    
  109.    
  110.     ≤
  111.    
  112.    
  113.     
  114.      y
  115.     
  116.     
  117.      1
  118.     
  119.    
  120.    
  121.     ≤
  122.    
  123.    
  124.     
  125.      y
  126.     
  127.     
  128.      2
  129.     
  130.    
  131.    
  132.     ≤
  133.    
  134.    
  135.     m
  136.    
  137.    
  138.     ,
  139.    
  140.   
  141.   
  142.    1≤y_1≤y_2≤m,
  143.   
  144.  
  145. 1≤y1​≤y2​≤m,
  148.  
  149.   
  150.    
  151.     −
  152.    
  153.    
  154.     1000
  155.    
  156.    
  157.     ≤
  158.    
  159.    
  160.     c
  161.    
  162.    
  163.     ≤
  164.    
  165.    
  166.     1000
  167.    
  168.    
  169.     ,
  170.    
  171.   
  172.   
  173.    −1000≤c≤1000,
  174.   
  175.  
  176. −1000≤c≤1000,
  179.  
  180.   
  181.    
  182.     −
  183.    
  184.    
  185.     1000
  186.    
  187.    
  188.     ≤
  189.    
  190.   
  191.   
  192.    −1000≤
  193.   
  194.  
  195. −1000≤ 矩阵内元素的值 
  197.  
  198.   
  199.    
  200.     ≤
  201.    
  202.    
  203.     1000
  204.    
  205.   
  206.   
  207.    ≤1000
  208.   
  209.  
  210. ≤1000

输入样例：

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

输出样例：

2 3 4 1
4 3 4 1
2 2 2 2

思路分析

对于二维差分数组，你可以这么去理解：如果前缀和的二维矩阵上的某一点是影响从矩阵左上角到该点内的数，那么差分数组矩阵就是影响从这一点到矩阵右下角，往 

  1.     a
  2.    
  3.   
  4.   
  5.    a
  6.   
  7.  
  8. a数组（二维） 
  10.  
  11.   
  12.    
  13.     (
  14.    
  15.    
  16.     
  17.      x
  18.     
  19.     
  20.      1
  21.     
  22.    
  23.    
  24.     ,
  25.    
  26.    
  27.     
  28.      y
  29.     
  30.     
  31.      1
  32.     
  33.    
  34.    
  35.     )
  36.    
  37.   
  38.   
  39.    (x_1,y_1)
  40.   
  41.  
  42. (x1​,y1​) 【左上角】和 
  44.  
  45.   
  46.    
  47.     (
  48.    
  49.    
  50.     
  51.      x
  52.     
  53.     
  54.      2
  55.     
  56.    
  57.    
  58.     ,
  59.    
  60.    
  61.     
  62.      y
  63.     
  64.     
  65.      2
  66.     
  67.    
  68.    
  69.     )
  70.    
  71.   
  72.   
  73.    (x_2,y_2)
  74.   
  75.  
  76. (x2​,y2​) 【右下角】的矩阵内加上一个数 
  78.  
  79.   
  80.    
  81.     c
  82.    
  83.   
  84.   
  85.    c
  86.   
  87.  
  88. c 可用差分：
  1. s[x1][y1]+= c;
  2. s[x2 +1][y1]-= c;
  3. s[x1][y2 +1]-= c;
  4. s[x2 +1][y2 +1]+= c;

然后再计算一遍前缀和数组，即可得到结果，注意我们的前缀和模板应该是：

  1. s[i, j]= s[i, j -1]+ s[i -1, j]- s[i -1, j -1]+ a[i, j];

但此时的 

  1.     s
  2.    
  3.    
  4.     [
  5.    
  6.    
  7.     i
  8.    
  9.    
  10.     ,
  11.    
  12.    
  13.     j
  14.    
  15.    
  16.     ]
  17.    
  18.   
  19.   
  20.    s[i, j]
  21.   
  22.  
  23. s[i,j] 其实就是一个值，即也为 
  25.  
  26.   
  27.    
  28.     a
  29.    
  30.    
  31.     [
  32.    
  33.    
  34.     i
  35.    
  36.    
  37.     ,
  38.    
  39.    
  40.     j
  41.    
  42.    
  43.     ]
  44.    
  45.   
  46.   
  47.    a[i,j]
  48.   
  49.  
  50. a[i,j]，故把差分数组变为前缀和数组为：
  1. s[i][j]+= s[i][j -1]+ s[i -1][j]- s[i -1][j -1];

代码

  1. #include<cstdio>#include<cstring>#include<algorithm>usingnamespace std;constint N =1010;int a[N][N], s[N][N];voidinsert(int x1,int y1,int x2,int y2,int c){
  2.     s[x1][y1]+= c;
  3.     s[x2 +1][y1]-= c;
  4.     s[x1][y2 +1]-= c;
  5.     s[x2 +1][y2 +1]+= c;}intmain(){int n, m, q;scanf("%d%d%d",&n,&m,&q);for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++)scanf("%d",&a[i][j]);// 处理差分数组for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++)insert(i, j, i, j, a[i][j]);while(q --){int x1, y1, x2, y2, c;scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);insert(x1, y1, x2, y2, c);}// 计算前缀和数组for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++) 
  6.             s[i][j]+= s[i][j -1]+ s[i -1][j]- s[i -1][j -1];for(int i =1; i <= n; i ++){for(int j =1; j <= m; j ++)printf("%d ", s[i][j]);puts("");}return0;}
标签： 蓝桥杯 差分 算法
本文转载自: https://blog.csdn.net/qq_52156445/article/details/122766080
版权归原作者 辰chen 所有， 如有侵权，请联系我们删除。
登录后发布评论

“蓝桥杯第九讲--差分【例/习题】”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？