无敌测试点

全部评论 1

• 

  Πpaid·King

  

  删除

  1、枚举算法
  1、枚举所有情况
  2、判断每种情况是否符合条件

  2、贪心算法
  1、贪
  排序

  bool cmp(int x,int y){
      return x>y; // > 从大到小; < 从小到大 
  }
  
  sort(a+1,a+n+1); // 从小到大
  sort(a+1,a+n+1,greater<int>()); // 从大到小
  sort(a+1,a+n+1,cmp); // 从大到小
  

  3、前缀和
  定义: s[i]: 原数组 a 的前 i 个数(1 ~ i)的和

  预处理: s[i] = s[i-1] + a[i]
  for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
  
  应用: 求区间 [L,R] 的区间和 sum(L,R)
      sum(L,R) = s[R] - s[L-1];
  
  用在有 多次 查询 区间和 的问题 O(1)
  

  4、差分
  定义: d[i]: 原数组 a 的相邻两项元素的差值

  预处理: d[i] = a[i] - a[i-1];
  for(int i=1;i<=n;i++) d[i]=a[i]-a[i-1];
  
  应用: 对原数组 a 区间 [L,R] 每个数加上 c
  
      d[L]+=c;
      d[R+1]-=c;
  
      直接对原数组 a 进行修改, 一次修改 时间复杂度 O(n);
      
      间接对差分数组 d 进行修改, 一次修改 时间复杂度 O(1),
      再通过对差分数组求前缀和得到修改后的原数组了 O(n);
  
  用在有 多次 区间修改 的问题
  

  5、原 前 差的转换

  昨天 来自 浙江

  0