8.17模拟赛小结

g1ove / 2023-08-17 / 原文

前言

最卡常的一集

T1 激光通讯原题

题意：给你一个大小不超过 \(100\times 100\) 的矩阵其中有一个起点，终点和一些障碍物求从起点到终点不碰到障碍物的最小转弯次数

思考一开始肯定是想记忆化 dfs 但是那样写了下发现麻烦于是改成了 bfs
容易发现转弯次数能小就小所以将普通的队列改成一个堆即可
时间复杂度 \(O(n^2\log n^2)\)

Code

#include<bits/stdc++.h>
#define N 105
using namespace std;
int n,m,sx,sy,ex,ey,ans=1e9;
char c[N][N];
int vis[N][N][2];//0横1竖 
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct point {
	int x,y,w,v;
};
bool operator < (point a,point b)
{
	return a.v>b.v;
}
priority_queue <point> q; 
void bfs()
{
	q.push((point){sx,sy,0,0});
	q.push((point){sx,sy,1,0});
	while(!q.empty())
	{
		point x=q.top();
		q.pop();		
		if(x.x>n||x.y>m||x.x<1||x.y<1||c[x.x][x.y]=='*') continue;
		if(x.x==ex&&x.y==ey)
			ans=min(ans,x.v);
		vis[x.x][x.y][x.w]=1;
		for(int i=0;i<2;i++)
		{
			int xx=x.x+dx[i],yy=x.y+dy[i];
			if(vis[xx][yy][0]) continue;
			q.push((point){xx,yy,0,x.v+x.w});
		}
		for(int i=2;i<4;i++)
		{
			int xx=x.x+dx[i],yy=x.y+dy[i];
			if(vis[xx][yy][1]) continue;
			q.push((point){xx,yy,1,x.v+1-x.w});
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			if(c[i][j]=='C')
				if(sx==0) sx=i,sy=j;
				else ex=i,ey=j;
		}
	bfs();
	cout<<ans;
	return 0;
}

T2 树

题意：已知一棵二叉树点的编号为 \(1\to n\) 且中序遍历也为 \(1\to n\) 给出这棵树的层次遍历求这棵树的先序遍历

思考：了解过平衡树 BST 堆之类的就知道原树就是一个 BST 因此满足左儿子小于根右儿子大于根的性质因此每个子树都必定是一个区间然后这个子树的根就是层次遍历最靠前的点 于是用一棵线段树维护即可时间复杂度 \(O(n\log n)\)

#include<bits/stdc++.h>
#define N 300005
using namespace std;
int n,a[N],id[N];//id:每个数的下标 
int tr[4*N];
void Pushup(int x)
{
	if(id[tr[x*2]]>id[tr[x*2+1]]) tr[x]=tr[x*2+1];
	else tr[x]=tr[x*2];
}
void builds(int l,int r,int x)
{
	if(l==r)
	{
		tr[x]=l;
		return;
	}
	int mid=(l+r)/2;
	builds(l,mid,x*2);
	builds(mid+1,r,x*2+1);
	Pushup(x);
}
int query(int l,int r,int L,int R,int x)
{
	if(l>R||r<L) return -1;
	if(l>=L&&r<=R) return tr[x];
	int mid=(l+r)/2;
	int ls=query(l,mid,L,R,x*2),rs=query(mid+1,r,L,R,x*2+1);
	if(ls==-1) return rs;
	if(rs==-1) return ls;
	if(id[ls]>id[rs]) return rs;
	return ls;
}
void solve(int l,int r)
{
	if(l>r) return;
	int root=query(1,n,l,r,1);
	printf("%d ",root);
	solve(l,root-1);
	solve(root+1,r);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),id[a[i]]=i;
	builds(1,n,1);
	solve(1,n);
	return 0;
}