前言
最卡常的一集
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;
}
T3 石头剪刀布
\(n\leq 2000\)
很毒瘤
错误的思路：前\(i\)个数最长上升序列长度为\(j\) 钦定每次最后取的数是 \(k\) 的方案数
因为这道题要求的是全局 所以不能钦定