如何在vps上搭建网站简单网站建设方案

如何在vps上搭建网站,简单网站建设方案,seo建设者,网站开发 文档#x1f4a1;Yupureki:个人主页 ✨个人专栏:《C》 《算法》 #x1f338;Yupureki#x1f338;的简介: 目录 前言 1. 一维差分 算法原理 实操代码 2. 海底高铁 算法原理 实操代码 3. 二位差分 算法原理 实操代码 4. 地毯 算法原理 实操代码 前言 前缀和和差分的…Yupureki:个人主页✨个人专栏:《C》 《算法》Yupureki的简介:目录前言1. 一维差分算法原理实操代码2. 海底高铁算法原理实操代码3. 二位差分算法原理实操代码4. 地毯算法原理实操代码前言前缀和和差分的本质是预处理可在暴力枚举的过程中快速得到答案是空间换时间的做法。另外前缀和和差分是一对互逆的运算1. 一维差分题目链接:【模板】差分算法原理我们引入差分数组的概念:我们有一个整型数组a定义差分数组f[n] a[n] - a[n-1]因此差分数组就是数组中一个数与前一个数的差值现在我把原数组下标为[L,R]的范围内统一增加一个数字c那么差分数组如何改变?由于是一个数减去前一个数那么[L 1,R]这个范围的值就不会改变因为统一增加c相当于(f[i] c) - (f[i-1] c) f[i] - f[i-1]等于原来的值但是如果是f[L]和f[R1]就要变了因为a[L]c,a[R]c那么f[L] a[L] c - a[L-1]f[R1] a[R1] - a[R] - c因此f[L]相比原来增加了cf[R1]相比原来减少了c这这就是差分数组的性质。我们发现如果我们统一对一段区间加上或减去一个相同的数在原数组中需要挨个遍历但差分数组只需要更改两个值即可。因此差分适用于统一对一段区间加上或减去一个相同的数这个操作另外对差分数组求前缀和就可以得到原数组实操代码#include iostream #include vector using namespace std; int main() { int a,b;cinab; vectorlong long v(a1,0);//原数组 vectorlong long del(a1,0);//差分数组 for(int i 1;ia;i) { long long num;cinnum; v[i] num; } for(int i 1;ia;i) del[i] v[i] - v[i-1];//初始化差分数组 while(b--) { int i,j,k;cinijk; del[i] k; del[j1] - k; } long long num 0; for(int i 1;ia;i) { num del[i];//差分数组求前缀和得到原数组 coutnum ; } return 0; }2. 海底高铁题目链接:P3406 海底高铁 - 洛谷算法原理先考虑如何让花费最小要想直到最小的花费就必须得知道一段地铁坐了多少次记f[n]随后算出买票的花费和买卡的花费之间的最小值买票花费:a[i] * f[i]买卡花费:b[i] * f[i] c[i]接下来考虑一段地铁坐了多少次由于从i城市 到 j城市需要坐[i,j-1]之间的所有地铁因此这实际上就是对一段区间统一加上一个数的操作我们使用差分数组f[i]表示一段地铁坐了i次实操代码#include iostream #include vector using namespace std; int main() { int n, m; cin n m; vectorint v; vectorint a(n); vectorint b(n); vectorint c(n); vectorint del(n 1);//差分数组 for (int i 0; i m; i) { int num; cin num; v.push_back(num); } for (int i 1; i n; i) { int A, B, C; cin A B C; a[i] A; b[i] B; c[i] C; } for (int i 0; i v.size() - 1; i) { int l v[i]; int r v[i 1]; if (l r) { int tmp r; r l; l tmp; } del[l]; del[r]--; } long long ret 0; long long k 0; for (int i 1; i n; i) { k del[i]; long long cost1 a[i] * k; long long cost2 c[i] b[i] * k; ret cost1 cost2 ? cost2 : cost1;//加上一段地铁的最小花费 } cout ret; return 0; }3. 二位差分题目链接:【模板】二维差分算法原理同样的对一段区间统一加值不过现在是二维矩阵我们需要推导出二维差分数组我们利用前缀和的思想思考假设我们对原数组左上角(x1,y1)右下角(x2,y2)的矩阵统一加上k由于求差分数组的前缀和就可以得到原数组那么在差分数组中就相当于是(x1,y1)这个位置加k这样(x1,y1)到(x2,y2)求前缀和就都能加上一个k但是不仅是紫色这一部分黄色绿色和粉色求前缀和都能加上一个k而原数组并没有对这些部分加k因此我们需要对(x21,y1) (x1,y21)减去一个k来抵消但是这样粉色部分又多减一个k因此再在(x2 1,y2 1)加k如何初始化二维差分数组?我们这样思考。假设原数组全是0读取一个数据k就是某个方格加上k也可以看做是(x1,y1)到(x2,y2)这个矩阵加k不过这个矩阵很小只有一个方格那么x2 x1 ,y2 y1实操代码#include iostream #include vector using namespace std; const int N 1010; void insert(long long x1, long long y1, long long x2, long long y2, long long value, vectorvectorlong long v) { v[x1][y1] value; v[x1][y2 1] - value; v[x2 1][y1] - value; v[x2 1][y2 1] value; } int main() { int n, m, k; cin n m k; static vectorvectorlong long v(N, vectorlong long(N, 0));//二维差分数组 for (int i 1; i n; i) { for (int j 1; j m; j) { long long value; cin value; insert(i, j, i, j, value, v);//初始化二维差分数组,x1 x2,y1 y2 } } for(int i 0;ik;i) { long long x1, y1, x2, y2, value; cin x1 y1 x2 y2 value; insert(x1, y1, x2, y2, value, v);//某一个矩阵统一加上value } for (int i 1; i n; i) { for (int j 1; j m; j) { v[i][j] v[i - 1][j] v[i][j - 1] - v[i - 1][j - 1];//差分数组求前缀和得到原数组 cout v[i][j] ; } cout endl; } return 0; }4. 地毯题目链接:P3397 地毯 - 洛谷算法原理铺一个地毯可以同时覆盖一个矩阵的点我们直接套用二维差分数组即可实操代码#include iostream #include vector using namespace std; const int N 1010; void insert(long long x1, long long y1, long long x2, long long y2, long long value, vectorvectorlong long v) { v[x1][y1] value; v[x1][y2 1] - value; v[x2 1][y1] - value; v[x2 1][y2 1] value; } int main() { int n, m; cin n m; static vectorvectorlong long v(N, vectorlong long(N, 0)); for (int i 0; i m; i) { long long x1, y1, x2, y2; cin x1 y1 x2 y2; insert(x1, y1, x2, y2, 1, v); } for (int i 1; i n; i) { for (int j 1; j n; j) { v[i][j] v[i - 1][j] v[i][j - 1] - v[i - 1][j - 1]; cout v[i][j] ; } cout endl; } return 0; }