其他算法()-其他

发表于： 3月 19, 2023 3月 19, 2023
分类：其他
标签：其他

其他算法()

ST表

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+110;
int st[N][21],m,n,k[N];
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void build(){
	for(int i=1;i<=17;i++)
		for(int j=1;j<=n;j++)
			st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);//数组开大点防止越界
	return;
}
int l,r;
int main(){
//	cout<<(1<<17);可以先看看应该开多大
	n=read(),m=read();
	for(int i=1;i<=n;i++)st[i][0]=read();
	build();int now=0;
	for(int i=1;i<=n;i++){if((1<<now+1)<=i)now++;k[i]=now;}//预处理完后可以O(1)查询了。
	for(int i=1;i<=m;i++){
		l=read(),r=read();
		printf("%d\n",max(st[l][k[r-l+1]],st[r-(1<<k[r-l+1])+1][k[r-l+1]]));
	} 
	return 0;
}

模拟退火

#include<bits/stdc++.h>
using namespace std;
const int N=1011;
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,x[N],y[N],w[N];
double nowx,nowy,ans,ansx,ansy;
double work(double tx,double ty){
	double energy=0;
	for(int i=1;i<=n;i++)
		energy+=sqrt((x[i]-tx)*(x[i]-tx)+(y[i]-ty)*(y[i]-ty))*w[i];
	return energy;
}
void SA(){
	nowx=ansx,nowy=ansy;//初始位置（继承上次最优解）YCE说：这里应该重新开始搜，否则容易陷入局部最优解。（正在验证）
	double T=3000;//初始温度 （影响搜索范围） 
	while(T>1e-16){//结束温度 
		double tx=nowx+(rand()*2-RAND_MAX)*T;
		double ty=nowy+(rand()*2-RAND_MAX)*T;//自己猜答案，温度越低越稳定
		double nwans=work(tx,ty);
		double de=nwans-ans;
		if(de<0){ansx=nowx=tx;ansy=nowy=ty;ans=nwans;}//更优解 
		else if(exp(-de/T)*RAND_MAX>rand()){//反正exp的范围为0~1，且越接近正解，越容易选，温度越低，越不容易选。
			nowx=tx,nowy=ty;
		}
		T*=0.995;//徐徐降温（影响搜索正确率） 
	}
	return;
}
void solve(){
	ansx=0,ansy=0,ans=work(nowx,nowy);//初始答案
	while((double)clock()/CLOCKS_PER_SEC<0.7)SA();//富贵TLE中求 
//	SA();SA();SA();
	return;
}
int main(){
	srand('F'+'J'+'L'+'o'+'v'+'e'+'J'+'C');
	n=read();for(int i=1;i<=n;i++){x[i]=read(),y[i]=read(),w[i]=read();}
	solve();
	printf("%.3lf %.3lf",ansx,ansy);
	return 0;
}

内存爆炸

你该检查一下自己是否MLE了。

#include<bits/stdc++.h>
using namespace std;
bool alarm1;//边界1（最上方）
const int N=1e6+110;
int st[N][210],m,n,k[N];
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void build(){
	for(int i=1;i<=17;i++)
		for(int j=1;j<=n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
			if(st[j+(1<<i-1)][i-1]==1e9+1)
				cout<<j<<" "<<i-1<<endl;
		}
	return;
}
int l,r;
bool alarm2;//边界2（最下方）
int main(){
	fprintf(stderr,"%0.3lf\n",abs(&alarm1-&alarm2)/1048576.0);//这是为了防止你没注释它（1048576=1024*1024）
//	cout<<(1<<17);
	n=read(),m=read();
	for(int i=1;i<=n;i++)st[i][0]=read();
	for(int i=n+1;i<=1e6;i++)st[i][0]=1e9+1;
	build();int now=0;
	for(int i=1;i<=n;i++){if((1<<now+1)<=i)now++;k[i]=now;}
	for(int i=1;i<=m;i++){
		l=read(),r=read();
		printf("%d\n",max(st[l][k[r-l+1]],st[r-(1<<k[r-l+1])+1][k[r-l+1]]));
	} 
	return 0;
}

手动开栈

**东西让我考场费时1h（另一个**东西是树剖，我再打树剖我就是狗！！！）

工具->编译选项->"-Wl,--stack=998244353"

反悔贪心

反悔自动机：

即设计一种反悔策略，使得随便一种贪心策略都可以得到正解。

基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略。（这就是自动机的意思）

具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。

反悔堆：

即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。

由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。

（摘自这里）

（例题见这里）

模拟费用流

好东西

代码风格

重载运算符：

MAT operator*(const MAT &A)const{
	MAT C;C.clear();
	for(int i=0;i<=4;i++)
		for(int j=0;j<=4;j++)
			for(int k=0;k<=4;k++)
				C.m[i][j]=min(C.m[i][j],A.m[i][k]+m[k][j]);
	return C;
}
bool operator<(const node &A)const{
	return A.dis<dis;
}

清晰的结构体包函数。

struct SegmentTree{
	struct node{ int l, r; Matrix val; } T[N<<2];
	void build(int p, int l, int r){
		T[p].l = l, T[p].r = r;
		if(l == r){
			for(int i = 0; i < 5; ++ i) T[p].val.a[i][i] = 0;
			if(s[l] == '2') T[p].val.a[0][0] = 1, T[p].val.a[0][1] = 0;
			if(s[l] == '0') T[p].val.a[1][1] = 1, T[p].val.a[1][2] = 0;
			if(s[l] == '1') T[p].val.a[2][2] = 1, T[p].val.a[2][3] = 0;
			if(s[l] == '7') T[p].val.a[3][3] = 1, T[p].val.a[3][4] = 0;
			if(s[l] == '6') T[p].val.a[3][3] = 1, T[p].val.a[4][4] = 1;
		} else {
			int mid = l + r >> 1;
			build(p<<1, l, mid); build(p<<1|1, mid+1, r);
			T[p].val = T[p<<1].val * T[p<<1|1].val; 
		}
	}
	Matrix query(int p, int l, int r){
		if(l <= T[p].l && T[p].r <= r) return T[p].val;
		int mid = T[p].l + T[p].r >> 1;
		if(r <= mid) return query(p<<1, l, r);
		if(mid < l) return query(p<<1|1, l, r);
		return query(p<<1, l, r) * query(p<<1|1, l, r);
	}
} Solver;

sqrt精度问题

long long x=sqrt((long long)n);
while((x+1)*(x+1)<=n)++x;
while(x*x>n)--x;

离散化

越是基础，越能决定成败

for(int i=1;i<=n;i++)lsh[i]=num[i]=read();
sort(lsh+1,lsh+n+1);
cnt=unique(lsg+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++){
	num[i]=lower_bound(lsh+1,lsh+cnt+1,num[i])-lsh;
}

————————

ST表

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+110;
int st[N][21],m,n,k[N];
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void build(){
	for(int i=1;i<=17;i++)
		for(int j=1;j<=n;j++)
			st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);//数组开大点防止越界
	return;
}
int l,r;
int main(){
//	cout<<(1<<17);可以先看看应该开多大
	n=read(),m=read();
	for(int i=1;i<=n;i++)st[i][0]=read();
	build();int now=0;
	for(int i=1;i<=n;i++){if((1<<now+1)<=i)now++;k[i]=now;}//预处理完后可以O(1)查询了。
	for(int i=1;i<=m;i++){
		l=read(),r=read();
		printf("%d\n",max(st[l][k[r-l+1]],st[r-(1<<k[r-l+1])+1][k[r-l+1]]));
	} 
	return 0;
}

模拟退火

#include<bits/stdc++.h>
using namespace std;
const int N=1011;
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
int n,x[N],y[N],w[N];
double nowx,nowy,ans,ansx,ansy;
double work(double tx,double ty){
	double energy=0;
	for(int i=1;i<=n;i++)
		energy+=sqrt((x[i]-tx)*(x[i]-tx)+(y[i]-ty)*(y[i]-ty))*w[i];
	return energy;
}
void SA(){
	nowx=ansx,nowy=ansy;//初始位置（继承上次最优解）YCE说：这里应该重新开始搜，否则容易陷入局部最优解。（正在验证）
	double T=3000;//初始温度 （影响搜索范围） 
	while(T>1e-16){//结束温度 
		double tx=nowx+(rand()*2-RAND_MAX)*T;
		double ty=nowy+(rand()*2-RAND_MAX)*T;//自己猜答案，温度越低越稳定
		double nwans=work(tx,ty);
		double de=nwans-ans;
		if(de<0){ansx=nowx=tx;ansy=nowy=ty;ans=nwans;}//更优解 
		else if(exp(-de/T)*RAND_MAX>rand()){//反正exp的范围为0~1，且越接近正解，越容易选，温度越低，越不容易选。
			nowx=tx,nowy=ty;
		}
		T*=0.995;//徐徐降温（影响搜索正确率） 
	}
	return;
}
void solve(){
	ansx=0,ansy=0,ans=work(nowx,nowy);//初始答案
	while((double)clock()/CLOCKS_PER_SEC<0.7)SA();//富贵TLE中求 
//	SA();SA();SA();
	return;
}
int main(){
	srand('F'+'J'+'L'+'o'+'v'+'e'+'J'+'C');
	n=read();for(int i=1;i<=n;i++){x[i]=read(),y[i]=read(),w[i]=read();}
	solve();
	printf("%.3lf %.3lf",ansx,ansy);
	return 0;
}

内存爆炸

你该检查一下自己是否MLE了。

#include<bits/stdc++.h>
using namespace std;
bool alarm1;//边界1（最上方）
const int N=1e6+110;
int st[N][210],m,n,k[N];
int read(){
	int x=0,f=1;char c=getchar();
	while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}
void build(){
	for(int i=1;i<=17;i++)
		for(int j=1;j<=n;j++){
			st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
			if(st[j+(1<<i-1)][i-1]==1e9+1)
				cout<<j<<" "<<i-1<<endl;
		}
	return;
}
int l,r;
bool alarm2;//边界2（最下方）
int main(){
	fprintf(stderr,"%0.3lf\n",abs(&alarm1-&alarm2)/1048576.0);//这是为了防止你没注释它（1048576=1024*1024）
//	cout<<(1<<17);
	n=read(),m=read();
	for(int i=1;i<=n;i++)st[i][0]=read();
	for(int i=n+1;i<=1e6;i++)st[i][0]=1e9+1;
	build();int now=0;
	for(int i=1;i<=n;i++){if((1<<now+1)<=i)now++;k[i]=now;}
	for(int i=1;i<=m;i++){
		l=read(),r=read();
		printf("%d\n",max(st[l][k[r-l+1]],st[r-(1<<k[r-l+1])+1][k[r-l+1]]));
	} 
	return 0;
}

手动开栈

**东西让我考场费时1h（另一个**东西是树剖，我再打树剖我就是狗！！！）

工具->编译选项->"-Wl,--stack=998244353"

反悔贪心

反悔自动机：

即设计一种反悔策略，使得随便一种贪心策略都可以得到正解。

基本的设计思路是：每次选择直观上最接近全局最优解的贪心策略，若发现最优解不对，就想办法自动支持反悔策略。（这就是自动机的意思）

具体题目具体分析。一般需要反悔自动机的题都是通过差值巧妙达到反悔的目的。

反悔堆：

即通过堆（大根堆、小根堆）来维护当前贪心策略的最优解，若发现最优解不对，就退回上一步，更新最优解。

由于堆的性质，使得堆的首数据一定是最优的，这就可以实现快速更新最优解。

（摘自这里）

（例题见这里）

模拟费用流

好东西

代码风格

重载运算符：

MAT operator*(const MAT &A)const{
	MAT C;C.clear();
	for(int i=0;i<=4;i++)
		for(int j=0;j<=4;j++)
			for(int k=0;k<=4;k++)
				C.m[i][j]=min(C.m[i][j],A.m[i][k]+m[k][j]);
	return C;
}
bool operator<(const node &A)const{
	return A.dis<dis;
}

清晰的结构体包函数。

struct SegmentTree{
	struct node{ int l, r; Matrix val; } T[N<<2];
	void build(int p, int l, int r){
		T[p].l = l, T[p].r = r;
		if(l == r){
			for(int i = 0; i < 5; ++ i) T[p].val.a[i][i] = 0;
			if(s[l] == '2') T[p].val.a[0][0] = 1, T[p].val.a[0][1] = 0;
			if(s[l] == '0') T[p].val.a[1][1] = 1, T[p].val.a[1][2] = 0;
			if(s[l] == '1') T[p].val.a[2][2] = 1, T[p].val.a[2][3] = 0;
			if(s[l] == '7') T[p].val.a[3][3] = 1, T[p].val.a[3][4] = 0;
			if(s[l] == '6') T[p].val.a[3][3] = 1, T[p].val.a[4][4] = 1;
		} else {
			int mid = l + r >> 1;
			build(p<<1, l, mid); build(p<<1|1, mid+1, r);
			T[p].val = T[p<<1].val * T[p<<1|1].val; 
		}
	}
	Matrix query(int p, int l, int r){
		if(l <= T[p].l && T[p].r <= r) return T[p].val;
		int mid = T[p].l + T[p].r >> 1;
		if(r <= mid) return query(p<<1, l, r);
		if(mid < l) return query(p<<1|1, l, r);
		return query(p<<1, l, r) * query(p<<1|1, l, r);
	}
} Solver;

sqrt精度问题

long long x=sqrt((long long)n);
while((x+1)*(x+1)<=n)++x;
while(x*x>n)--x;

离散化

越是基础，越能决定成败

for(int i=1;i<=n;i++)lsh[i]=num[i]=read();
sort(lsh+1,lsh+n+1);
cnt=unique(lsg+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++){
	num[i]=lower_bound(lsh+1,lsh+cnt+1,num[i])-lsh;
}