首页 > 其他分享 >斜率优化(超详细/看了就会)(基本知识+例题讲解+清晰代码)看了的人rp+++++++++ 烽火传递+玩具分组+特别行动队+征途

斜率优化(超详细/看了就会)(基本知识+例题讲解+清晰代码)看了的人rp+++++++++ 烽火传递+玩具分组+特别行动队+征途

时间:2024-08-24 21:56:45浏览次数:14  
标签:rp int sum 斜率 2A sm 行动队 fi 例题

斜率优化(超详细/看了就会)(基本知识+例题讲解+清晰代码)看了的人rp+++++++++ 烽火传递+玩具分组+特别行动队+征途

对于斜优啊也是早就有所耳闻

但是本蒟太蒻了前段时间才学

发现很有用诶

所以学的很认真

总结打的的也很认真

希望大家也可以看的认真

是为序。

前置芝士

单调队列

【单调】指元素递增或递减

【队列】指元素只能从队头队尾进行操作

不是优先队列哦

不要傻傻分不清啦

例题-烽火传递
题意

两个城市间有 n n n 个烽火台,每个烽火台 i i i 可以付出 a i a_i ai​ 的代价发出信号,每 m m m 个烽火台中至少要有一个发出信号,问情报在这两座城市之间传递所需要的代价。

解法

设 f i f_i fi​ 表示信号从第一座城市传递到 i i i 所需的最小代价

可得转移方程为
f i = min ⁡ i − m − 1 ≤ j < i f j + a i f_i=\min\limits_{i-m-1 \le j<i} f_j+a_i fi​=i−m−1≤j<imin​fj​+ai​
因为 m m m 座中只要有一座发出信号就好了,所以最后的 m m m 座都可以作为答案

那么最后的答案就是
a n s = min ⁡ n − m < i ≤ n f i ans=\min\limits_{n-m<i\le n} f_i ans=n−m<i≤nmin​fi​

代码
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5,Inf=2e9;
int a[N+10],f[N+10],q[N+10];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	int hd=0,tl=0;
	for(int i=1;i<=n;i++)
	{
		while((hd<tl)&&((q[hd]+m)<i))
		{
			hd++;
		}
		f[i]=f[q[hd]]+a[i];
		while((hd<tl)&&(f[q[tl]]>=f[i]))
		{
			tl--;
		}
		q[++tl]=i;
	}
	int ans=Inf;
	for(int i=n-m+1;i<=n;i++)
	{
		ans=min(ans,f[i]);
	}
	printf("%d",ans);
	return 0;
}

由此我们也可以提炼出单调队列优化的基本操作

即:First,不断将队头后移使得其满足最优决策点的性质,最后剩的队头就是最优决策点,可依此进行转移。Second,将加入新的点 i i i 后,不满足单调递增的队尾弹出,并将 i i i 加入队尾

[斜率(slope)](斜率_百度百科 (baidu.com))

上面的链接是百度百科,有需要的自行 click

不过也不用管那么多,简单解释下

一条直线的解析式可以用 y = k x + b y=kx+b y=kx+b 来表示, k k k 就是这条直线的斜率

或者如果知道直线 A B AB AB 上的两个点 A ( a x , a y ) , B ( b x , b y ) A(a_x,a_y),B(b_x,b_y) A(ax​,ay​),B(bx​,by​) ,也可以求出斜率

即: s l o p e ( A B ) = a y − b y a x − b x slope(AB)=\dfrac{a_y-b_y}{a_x-b_x} slope(AB)=ax​−bx​ay​−by​​

这个很重要,后面会用到

凸包

也是别管那么多,只要知道:

凸包上每条直线的斜率一定具有单调性

单调递增的是上凸包,单调递减的是下凸包

了解下就好了。


例题引路

[HNOI2008]玩具装箱

题意

有 n n n 个玩具,玩具 i i i 的长度为 c i c_i ci​ ,现要将玩具分组,每组里的编号需连续, i ∼ j i \sim j i∼j 的玩具组代价为 ( j − i + ∑ k = i j c k − L ) 2 (j-i+\sum_{k=i}^{j} c_k-L)^2 (j−i+∑k=ij​ck​−L)2 , L L L 为给定的常量。

解法

真真斜率优化板子题了

首先统一一下说法

s m i = ∑ j = 1 i c j sm_i=\sum_{j=1}^{i} c_j smi​=∑j=1i​cj​ (即前缀和,以下题目均为此含义)
L = L + 1 L=L+1 L=L+1

设 f i f_i fi​ 表示装前 i i i 个所需的最小花费,答案就是 f n f_n fn​

易得
f i = f j + ( i − j + s m i − s m j − L ) 2 f_i=f_j+(i-j+sm_i-sm_j-L)^2 fi​=fj​+(i−j+smi​−smj​−L)2
显然这是 O ( n 2 ) \Omicron( n^2 ) O(n2) 的

我们尝试将其优化至 O ( n ) \Omicron( n ) O(n)

然后就开始愉快的推柿子了

设 A i = s m i + i A_i=sm_i+i Ai​=smi​+i
f i = f j + ( A i − A j − L ) 2 f_i=f_j+(A_i-A_j-L)^2 fi​=fj​+(Ai​−Aj​−L)2
考虑 k < j k<j k<j 并且 j j j 转移到 i i i 优于 k k k 需要满足什么条件
f j + ( A i − A j − L ) 2 ≤ f k + ( A i − A k − L ) 2 f_j+(A_i-A_j-L)^2 \le f_k+(A_i-A_k-L)^2 fj​+(Ai​−Aj​−L)2≤fk​+(Ai​−Ak​−L)2
拆开,得
f j + A i 2 + A j 2 + L 2 − 2 A i A j − 2 A i L + 2 A j L ≤ f k + A i 2 + A k 2 + L 2 − 2 A i A k − 2 A i L + 2 A k L f_j+A_i^2+A_j^2+L^2-2A_iA_j-2A_iL+2A_jL \le f_k+A_i^2+A_k^2+L^2-2A_iA_k-2A_iL+2A_kL fj​+Ai2​+Aj2​+L2−2Ai​Aj​−2Ai​L+2Aj​L≤fk​+Ai2​+Ak2​+L2−2Ai​Ak​−2Ai​L+2Ak​L
化简一下
f j + A j 2 − 2 A i A j + 2 A j L ≤ f k + A k 2 − 2 A i A k + 2 A k L f_j+A_j^2-2A_iA_j+2A_jL \le f_k+A_k^2-2A_iA_k+2A_kL fj​+Aj2​−2Ai​Aj​+2Aj​L≤fk​+Ak2​−2Ai​Ak​+2Ak​L
移一下项
( f j + A j 2 ) − ( f k + A k 2 ) ≤ 2 A i A j − 2 A i A k + 2 A k L − 2 A j L (f_j+A_j^2)-(f_k+A_k^2) \le 2A_iA_j-2A_iA_k+2A_kL-2A_jL (fj​+Aj2​)−(fk​+Ak2​)≤2Ai​Aj​−2Ai​Ak​+2Ak​L−2Aj​L
设 B i = f i + A i 2 B_i=f_i+A_i^2 Bi​=fi​+Ai2​
B j − B k ≤ 2 ( A i − L ) ( A j − A k ) B_j-B_k \le 2(A_i-L)(A_j-A_k) Bj​−Bk​≤2(Ai​−L)(Aj​−Ak​)
最后
B j − B k A j − A k ≤ 2 ( A i − L ) \frac{B_j-B_k}{A_j-A_k} \le 2(A_i-L) Aj​−Ak​Bj​−Bk​​≤2(Ai​−L)
推柿子环节至此结束

那么柿子的左边就是斜率(忘记的往上滑回去看)

我们基于这个式子来进行单调队列优化

其实跟上面的烽火传递很类似,只是柿子部分改下就好了

不过并不是所有的斜率优化都能依靠单调队列进行,只有当斜率具有单调性才可以,不然我们就要利用别的数据结构了。

代码

Talk is cheap,show you the code.

#include<cstdio>
#define ll long long int 
using namespace std;
const int N=5e4;
ll sm[N+10],f[N+10];
int q[N+10];
ll A(int x)
{
	return sm[x]+x;
}
ll B(int x)
{
	return f[x]+A(x)*A(x);
}
double fnd(int x,int y)
{
	return (double)(B(x)-B(y))/(double)(A(x)-A(y));
}
int main()
{
	int n;
	ll m;
	scanf("%d%lld",&n,&m);
	m++;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&sm[i]);
		sm[i]+=sm[i-1];
	}
	int hd=0,tl=0;
	for(int i=1;i<=n;i++)
	{
		while((hd<tl)&&(fnd(q[hd],q[hd+1])<=((sm[i]+i-m)<<1)))
		{
			hd++;
		}
		f[i]=f[q[hd]]+(A(i)-A(q[hd])-m)*(A(i)-A(q[hd])-m);
		while((hd<tl)&&(fnd(q[tl-1],q[tl])>fnd(i,q[tl-1])))
		{
			tl--;
		}
		q[++tl]=i;
	}
	printf("%lld",f[n]);
	return 0;
}

一些练习题

相信通过上面的例题,大家都对斜率优化有了一些基本了解了。所以下面的练习题就只阐述推柿子的过程和放代码啦。

建议大家在看的时候,自己拿纸笔跟着推一下,收获会更大哦。

特别行动队

题意

现有 n n n 名士兵,士兵 i i i 的战斗力为 x i x_i xi​ ,要将士兵拆分成若干组,每组中士兵编号连续。一组 i ∼ j i \sim j i∼j 士兵组的初始战斗力 y y y 为 ∑ k = i j x k \sum_{k=i}^{j} x_k ∑k=ij​xk​ ,修正战斗力 z z z 为 a y 2 + b y + c ay^2+by+c ay2+by+c ,其中 a , b , c a,b,c a,b,c 为给定的系数。求划分后修正战斗力之和最大。

解法

照例, s m sm sm 表示前缀和

设 f i f_i fi​ 表示前 i i i 个的修正战斗力最大值,那么答案就是 f n f_n fn​

易得状态转移方程
f i = max ⁡ j < i f j + a ( s m i − s m j ) 2 + b ( s m i − s m j ) + c f_i=\max\limits_{j<i} f_j+a(sm_i-sm_j)^2+b(sm_i-sm_j)+c fi​=j<imax​fj​+a(smi​−smj​)2+b(smi​−smj​)+c
展开,化简,得
f i = f j + a s m i 2 + a s m j 2 − 2 a s m i s m j − b s m j + b s m i + c f_i=f_j+asm_i^2+asm_j^2-2asm_ism_j-bsm_j+bsm_i+c fi​=fj​+asmi2​+asmj2​−2asmi​smj​−bsmj​+bsmi​+c
照例,把与 j j j 无关的项挪到左边
f i − a s m i 2 − b s m i − c = f j + a s m j 2 − b s m j − 2 a s m i s m j f_i-asm_i^2-bsm_i-c=f_j+asm_j^2-bsm_j-2asm_ism_j fi​−asmi2​−bsmi​−c=fj​+asmj2​−bsmj​−2asmi​smj​
若 j j j 转移至 i i i 比 k k k 更优,需满足(注意,此题求的是最大值,所以实际上维护的是上凸包,式子中也应为 > 或 $ \ge $ )
f j + a s m j 2 − b s m j − 2 a s m i s m j ≥ f k + a s m k 2 − b s m k − 2 a s m i s m k f_j+asm_j^2-bsm_j-2asm_ism_j \ge f_k+asm_k^2-bsm_k-2asm_ism_k fj​+asmj2​−bsmj​−2asmi​smj​≥fk​+asmk2​−bsmk​−2asmi​smk​
令 A i = f i + a s m i 2 − b s m i A_i=f_i+asm_i^2-bsm_i Ai​=fi​+asmi2​−bsmi​
A j − 2 s m i s m j ≥ A k − 2 s m i s m k A_j-2sm_ism_j \ge A_k-2sm_ism_k Aj​−2smi​smj​≥Ak​−2smi​smk​
移项
A j − A k ≥ 2 s m i ( s m j − s m k ) A_j-A_k \ge 2sm_i(sm_j-sm_k) Aj​−Ak​≥2smi​(smj​−smk​)
最后
A j − A k s m j − s m k ≥ 2 s m i \frac{A_j-A_k}{sm_j-sm_k} \ge 2sm_i smj​−smk​Aj​−Ak​​≥2smi​
搞定!

(不过还是要注意细节,尤其是推柿子的时候)

代码
#include<cstdio>
#define ll long long int 
using namespace std;
const int N=1e6;
ll sm[N+10],f[N+10];
int q[N+10];
int n;
ll a,b,c;
ll A(int x)
{
	return f[x]+a*sm[x]*sm[x]-b*sm[x];
}
double fnd(int x,int y)
{
	return (double)(A(x)-A(y))/(double)(sm[x]-sm[y]);
}
int main()
{
	scanf("%d%lld%lld%lld",&n,&a,&b,&c);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&sm[i]);
		sm[i]+=sm[i-1];
	}
	int hd=0,tl=0;
	for(int i=1;i<=n;i++)
	{
		while((hd<tl)&&(fnd(q[hd],q[hd+1])>=(double)(2*a*sm[i])))
		{
			hd++;
		}
		f[i]=f[q[hd]]+a*(sm[i]-sm[q[hd]])*(sm[i]-sm[q[hd]])+b*(sm[i]-sm[q[hd]])+c;
		while((hd<tl)&&(fnd(q[tl-1],q[tl])<=fnd(q[tl],i)))
		{
			tl--;
		}
		q[++tl]=i;
	}
	printf("%lld",f[n]);
	return 0;
}

征途

题意

有 n n n 段路程,每一段的长度是 a i a_i ai​ ,将其划分为 m m m 段,求最小方差 × m 2 \times m^2 ×m2

解法

设划分后每段的长度为 b i b_i bi​ , b ‾ \overline{b} b 表示 b b b 序列的平均值,即 ∑ i = 1 m b i m \dfrac{\sum_{i=1}^{m} b_i}{m} m∑i=1m​bi​​

再设最小方差为 v v v

则:
v m 2 = ∑ i = 1 m ( b i − b ‾ ) 2 m m 2 v m 2 = m ( ∑ i = 1 m ( b i 2 + b ‾ 2 − 2 b ‾ b i ) ) v m 2 = m ( ∑ i = 1 m b i 2 + m b ‾ 2 − 2 b ‾ ∑ i = 1 m b i ) v m 2 = m ∑ i = 1 m b i 2 + ( ∑ i = 1 m b i ) 2 − 2 ( ∑ i = 1 m b i ) 2 v m 2 = m ∑ i = 1 m b i 2 − s m n 2 vm^2=\frac{\sum_{i=1}^{m} (b_i-\overline{b})^2}{m}m^2\\ vm^2=m(\sum_{i=1}^{m} (b_i^2+\overline{b}^2-2\overline{b}b_i))\\ vm^2=m(\sum_{i=1}^{m} b_i^2+m\overline{b}^2-2\overline{b}\sum_{i=1}^{m} b_i)\\ vm^2=m\sum_{i=1}^{m} b_i^2+(\sum_{i=1}^{m}b_i)^2-2(\sum_{i=1}^{m} b_i)^2\\ vm^2=m\sum_{i=1}^{m} b_i^2-sm_n^2 vm2=m∑i=1m​(bi​−b)2​m2vm2=m(i=1∑m​(bi2​+b2−2bbi​))vm2=m(i=1∑m​bi2​+mb2−2bi=1∑m​bi​)vm2=mi=1∑m​bi2​+(i=1∑m​bi​)2−2(i=1∑m​bi​)2vm2=mi=1∑m​bi2​−smn2​

m m m 是已知的, b i b_i bi​ 也已知,那么当下目标就是使得 ∑ i = 1 m b i 2 \sum_{i=1}^{m} b_i^2 ∑i=1m​bi2​ 最小

表示第 i i i 段的结尾为 j j j 个数的最小平方和

可得转移方程
f i , j = min ⁡ ( f i − 1 , k + ( s m j − s m k ) 2 ) f_{i,j}=\min(f_{i-1,k}+(sm_j-sm_k)^2) fi,j​=min(fi−1,k​+(smj​−smk​)2)
展开,得
f i , j = f i − 1 , k + s m j 2 + s m k 2 − 2 s m j s m k f_{i,j}=f_{i-1,k}+sm_j^2+sm_k^2-2sm_jsm_k fi,j​=fi−1,k​+smj2​+smk2​−2smj​smk​
把与 k k k 无关的项移至左边,得
f i , j − s m j 2 = f i − 1 , k + s m k 2 − 2 s m j s m k f_{i,j}-sm_j^2=f_{i-1,k}+sm_k^2-2sm_jsm_k fi,j​−smj2​=fi−1,k​+smk2​−2smj​smk​
考虑由 k k k 转移比由 l l l 转移更优需要满足的条件
f i − 1 , k + s m k 2 − 2 s m j s m k ≤ f i − 1 , l + s m l 2 − 2 s m j s m l f_{i-1,k}+sm_k^2-2sm_jsm_k \le f_{i-1,l}+sm_l^2-2sm_jsm_l fi−1,k​+smk2​−2smj​smk​≤fi−1,l​+sml2​−2smj​sml​
惯常套路,浅浅移一下项
( f i − 1 , k + s m k 2 ) − ( f i − 1 , l + s m l 2 ) ≤ 2 s m j s m k − 2 s m j s m l (f_{i-1,k}+sm_k^2)-(f_{i-1,l}+sm_l^2) \le 2sm_jsm_k-2sm_jsm_l (fi−1,k​+smk2​)−(fi−1,l​+sml2​)≤2smj​smk​−2smj​sml​
令 A j = f i − 1 , j + s m j 2 A_j=f_{i-1,j}+sm_j^2 Aj​=fi−1,j​+smj2​
A k − A l ≤ 2 s m j ( s m k − s m l ) A_k-A_l \le 2sm_j(sm_k-sm_l) Ak​−Al​≤2smj​(smk​−sml​)
最后
A k − A l s m k − s m l ≤ 2 s m j \frac{A_k-A_l}{sm_k-sm_l} \le 2sm_j smk​−sml​Ak​−Al​​≤2smj​

然后依此斜率优化即可

代码
#include<cstdio>
#include<iostream>
#define ll long long int 
using namespace std;
const ll Inf=1e18;
const int N=3e3;
ll sm[N+10],f[N+10][N+10];
int q[N+10];
double A(int x,int y)
{
	return (double)f[x][y]+sm[y]*sm[y];
}
double fnd(int x,int y,int z)
{
	return (A(x,y)-A(x,z))/(double)(sm[y]-sm[z]);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			f[i][j]=Inf;
		}
	}
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		sm[i]=sm[i-1]+x;
	}
	for(int i=1;i<=m;i++)
	{
		int hd=0,tl=0;
		for(int j=1;j<=n;j++)
		{
			while((hd<tl)&&(fnd(i-1,q[tl],q[tl-1])>fnd(i-1,j,q[tl])))
			{
				tl--;
			}
			q[++tl]=j;
			while((hd<tl)&&(fnd(i-1,q[hd+1],q[hd])<(double)(sm[j]<<1)))
			{
				hd++;
			}
			f[i][j]=f[i-1][q[hd]]+(sm[j]-sm[q[hd]])*(sm[j]-sm[q[hd]]);
		}
	}
	printf("%lld",f[m][n]*m-(sm[n]*sm[n]));
	return 0;
}

注意,根据我们上面推出的柿子,答案是 m f m , n − s m n 2 mf_{m,n}-sm_n^2 mfm,n​−smn2​

一些疑惑

Q1:什么时候可以用斜优啊?

A1:一般来讲,如果这道题你推出的 dp 式形为 f i = min ⁡ / max ⁡ ( f j + a j + b i c j ) f_i=\min / \max(f_j+a_j+b_ic_j) fi​=min/max(fj​+aj​+bi​cj​) ,也就是说同时含有 i , j i,j i,j 的项,此时很难找到最优决策点,多半是斜率优化。

Q2:可以讲下一般怎么推柿子吗?

A2:当然。以作者的个人习惯,会分为一下几个步骤:

  1. 一般只把含有转移项的项留在右边,其余的挪去左边(比如说,用 j j j 来转移 i i i ,就只把含有 j j j 的项留在右边)
  2. 考虑怎样转移更优(例:考虑由 j j j 转移到 i i i 比 k k k 转移更优),列出不等式
  3. 然后无所不用其极努力来化简这个不等式,使柿子的左边化成类似斜率的形式 a y − b y a x − b x \dfrac{a_y-b_y}{a_x-b_x} ax​−bx​ay​−by​​ 。在过程中可以适当引入一些表示方式来使柿子更简洁。

Q2:刚说只有斜率具有单调性的时候才能单调队列优化,那如果不具有单调性呢?

A2:这个时候就需要用一些恶心复杂的数据结构,比如平衡树之类的来寻找最优决策点,或者使用 CDQ 分治实现。

Q3+:为什么这篇文章不写呢?

A3+:这就非常惭愧了,因为作者本身是一名初中 OIer。啊不过这不是重点,重点是作者实在是太蒻了,这一部分也还在学习中,学会了再来和大家分享。

后记

这是我在 csdn 的第二篇博客啦

希望讲的能让大家看的清楚

博客中有错误或是遗漏的话也请各位不吝指出

有不太能理解的地方也可以在评论区发出来,我会解答的。

这篇真的打的超久超用心的

大家多多支持,一键三连哦。

谢谢啦

标签:rp,int,sum,斜率,2A,sm,行动队,fi,例题
From: https://blog.csdn.net/L_Aria/article/details/141389391

相关文章

  • 数列(贪心思维题)(很有意思哦)(读者 rp +++++++)
    数列(贪心思维题)(很有意思哦)(读者rp+++++++)序这是前段时间做的一道题,蛮有思维含量的,而且对于代码实现能力也有一定要求。作者也交了好多发......
  • 怎么实现用frp搭建一个自己的内网穿透服务
    使用frp搭建一个自己的内网穿透服务包括以下几个步骤:配置frp服务器(服务端)和frp客户端。Frp是什么:frp(FastReverseProxy)是一款高性能的反向代理应用,广泛用于内网穿透、跨网络访问等场景。以下是frp的一些常见应用场景:1.内网服务的外网访问frp可以将内网中的Web......
  • GO中的RPC
    RPC是什么RPC是远程过程调用的简称,是分布式系统中不同节点间流行的通信方式。它允许客户端程序调用位于远程计算机上的服务器程序上的方法或函数,就像调用本地程序一样。简单使用服务端RPC方法只能有两个可序列化的参数,其中第二个参数是指针类型,并且返回一个error类型,同时......
  • 十五、OpenCVSharp实现相机标定
    文章目录简介一、相机模型1.针孔相机模型2.畸变模型(径向畸变、切向畸变)二、标定板的设计和使用1.常见的标定板类型(如棋盘格、圆形标定板)2.标定板图像的采集要求三、相机标定的步骤1.角点检测和提取2.求解相机内参和外参3.标定结果的评估和优......
  • trie 树详解 + 例题
    看这篇做的笔记la~ほら、もうすぐ晴れますよ!字典树字典树(trie树)是一种用于实现字符串快速检索的多叉树结构。trie树的每个节点都拥有若干个字符指针,若在插入或检索字符串时扫描到一个字符c,就沿着当前节点的c字符指针,走向该指针指向的节点。下图即为一个简易版字典树,存......
  • 彩度战队运行故障:Assembly-CSharp.dll文件缺失原因及修复方法
    一、缺失原因Assembly-CSharp.dll文件是Unity游戏引擎在编译C#脚本时生成的一个动态链接库(DLL)文件,它包含了游戏或软件的核心逻辑和控制代码,是游戏或软件能够正常运行的关键部分。在彩度战队游戏中,Assembly-CSharp.dll文件缺失可能由以下原因造成:安装不完整或损坏:游戏在安......
  • C#/asp.net-智能制造业ERP系统-89973(免费领源码+开发文档)可做计算机毕业设计JAVA、PHP
    C#(asp.net)智能制造业ERP系统摘 要随着互联网趋势的到来,各行各业都在考虑利用互联网将自己推广出去,最好方式就是建立自己的互联网系统,并对其进行维护和管理。在现实运用中,应用软件的工作规则和开发步骤,采用C#技术建设智能制造业ERP系统。本设计主要实现集人性化、高效率......
  • 谭浩强c程序设计例题+习题 第六章 利用数组处理批量数据
    第六章利用数组处理批量数据文章目录第六章利用数组处理批量数据例6.1对10个数组元素依次赋值为0,1,2,3...,9并逆序输出例6.2用数组处理Fibonacci数列问题例6.3有10个地区的面积,要求对它们按照从小到大顺序排序例6.4将一个二维数组行和列互换存到零一个二维数组中......
  • 线段树(2)——懒惰标记Lazy Tag(单运算)及例题
    上一篇文章我们讲了线段树的最基本的操作。如果有一种操作叫做区间加法呢?这个时候显然可以依次单点修改,但是时间复杂度太高了。所以可以考虑优化,由于思考过程可能很长,此处直接引入懒惰标记。懒惰标记就是在对一颗树的所有节点进行某种统一操作时,只对根节点做一个标记表示它的子树......
  • burpsuite xssValidator插件(xss插件)
    安装1.商城安装插件2.安装环境DownloadPhantomJShttps://phantomjs.org/download.htmlGitHub-NetSPI/xssValidator:ThisisaburpintruderextenderthatisdesignedforautomationandvalidationofXSS......