首页 > 编程语言 >【基础算法】差分

【基础算法】差分

时间:2024-03-03 20:25:23浏览次数:27  
标签:y2 int 基础 cin 差分 算法 y1 x1

差分

// 每日一题
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int n;
int a[N], s[N];
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i - 1] + a[i]; // 前缀和
	}
	LL res = 0;
	for (int i = 1; i <= n - 1; i++)
	{
		res = res + (LL)a[i] * (s[n] - s[i]);
	}
	cout << res << endl;
	return 0;
}

什么是差分?

差分就是一个序列中后一项减前一项的过程。

差分数组就是一个序列中后一项减前一项的值组成的一个新的序列。

例如

有一个序列为:\([2,1,4,6,3,2]\) 那么这个序列的差分数组为:\([2,-1,3,2,-3,-1]\)

差分可以解决什么问题?

  • 区间修改(将 \(O(n)\) 时间的修改区间变为 \(O(1)\) 时间的修改端点)

例题:一维差分

暴力:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) 
	{
		cin >> a[i];
	}
	while (m --)
	{
		int l, r, c;
		cin >> l >> r >> c;
		for (int i = l; i <= r; i ++)
			a[i] += c;
	}
	for (int i = 1; i <= n; i++) cout << a[i] << ' ';
	return 0;
}

差分:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) 
	{
		cin >> a[i];
		b[i] = a[i] - a[i - 1]; // 初始化差分数组
	}
	while (m --)
	{
		int l, r, c;
		cin >> l >> r >> c;
		b[l] += c;
		b[r + 1] -= c;
	}
	for (int i = 1; i <= n; i++) b[i] += b[i - 1]; // 前缀和
	
	for (int i = 1; i <= n; i++) cout << b[i] << ' ';
	return 0;
}

例题:二维差分

暴力:

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N];
int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	while (q --)
	{
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		for (int i = x1; i <= x2; i++)
			for (int j = y1; j <= y2; j++)
				a[i][j] += c;
	}
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cout << a[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

差分:

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void modify(int x1, int y1, int x2, int y2, int c)
{
	b[x1][y1] += c;
	b[x2 + 1][y1] -= c;
	b[x1][y2 + 1] -= c;
	b[x2 + 1][y2 + 1] += c;
}
int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][j];
			//b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]; // 初始化差分数组
     		modify(i, j, i, j, a[i][j]); // 初始化差分数组       
		}
	while (q--)
	{
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		modify(x1, y1, x2, y2, c);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; // 求前缀和
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
			cout << b[i][j] << ' ';
		cout << endl;
	}
	return 0;
}

标签:y2,int,基础,cin,差分,算法,y1,x1
From: https://www.cnblogs.com/yhgm/p/18050606

相关文章

  • Java:基础语法
    注释平时我们编写代码,在代码量比较少的时候,我们还可以看懂自己写的,但是当项目结构一旦复杂起来,我们就需要用到一个注释了,注释就类似于我们上学时候写的笔记,我们看着笔记就知道自己写的什么东西了!在程序中也是如此。我们来看一下Java中的注释怎么写,看以下代码:/**@DescriptionH......
  • 【基础算法】二分查找
    二分查找什么是二分?将问题分成两个部分。猜数游戏计算机给你一个范围内的随机数,你要输入一个数,计算机给你反馈是太大了还是太小了,直到你输出正确的答案。怎么设计这个程序呢?#include<iostream>#include<ctime>usingnamespacestd;intmain(){srand(time(NULL));......
  • 【基础算法】二分答案
    二分答案什么是二分答案?将答案区间进行二分,不断缩小答案区间,直到区间缩小到符合题意的答案。我们又该怎么书写呢?常用的二分模版://不断缩小答案区间while(l<=r){intmid=l+r>>1;if(check(mid))r=mid-1;elsel=mid+1;}模版的含义\(......
  • nginx系列文章01---基础知识
    1.何为反向代理?在介绍反向代理之前,先来了解一下正向代理。正向代理:如果把局域网外的Internet想象成一个巨大的资源库,则局域网中的客户端要访问Internet,则需要通过代理服务器来访问,这种代理服务就称为正向代理,下面是正向代理的原理图。由于工作环境原因,日常工作只能局限于单位的......
  • 如何判断算法的好坏?
    事后统计法(直接运行两个算法程序后比较运行速度)1.过于依赖测试数据 2.过于依赖硬件条件事前分析法     时间复杂度  大O表示法  ......
  • 2024AcWing蓝桥杯集训·每日一题-差分
    1.[AcWing4262.空调]题目描述FarmerJohn的\(N\)头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些,而有些奶牛则喜欢温度高一些。FarmerJohn的牛棚包含一排\(N\)个牛栏,编号为\(1…N\),每个牛栏里有一头牛。第\(i\)头奶牛希望她的牛栏中的温度是\(p_i\),而现......
  • 动手学强化学习(五):时序差分算法
    第5章时序差分算法5.1简介第4章介绍的动态规划算法要求马尔可夫决策过程是已知的,即要求与智能体交互的环境是完全已知的(例如迷宫或者给定规则的网格世界)。在此条件下,智能体其实并不需要和环境真正交互来采样数据,直接用动态规划算法就可以解出最优价值或策略。这就好比对于......
  • 手写HashMap基础部分代码
    代码展示:packagecom.north.hashmap;importjava.util.Map;/***@AuthorNorth*@Date2024/3/3*手写HashMap*/@SuppressWarnings("all")publicclassMyHashMap<K,V>{/***哈希表*/privateNode<K,V>[]table;......
  • Nestjs系列 Nestjs基础(二)
    providers使用该内容可以结合Nestjs中文网-自定义提供者查看创建一个nest项目,创建一个Personcrud模块。providers写法providers完整和简写@Injectable()装饰器将PersonService类标记为提供者。然后在Module中声明,即和PersonService做关联,个人感觉provider......
  • 【Java基础】Maven入门笔记
    本篇笔记参考尚硅谷Maven课程,概括总结了Maven的核心功能Maven仓库地址:MavenRepository:Search/Browse/Explore一、Maven简介1.Maven是一个依赖管理工具、构建工具2.Maven介绍Maven是一款为Java项目管理构建、依赖管理的工具(软件),使用Maven可以自动化构建、测试、打......