首页 > 分享 > 洛谷 P4667 Switch the Lamp On

洛谷 P4667 Switch the Lamp On

花匠小妙招
2024-12-09 09:56

传送门：洛谷 P4667 Switch the Lamp On
重题（弱化版）：洛谷 P2243 电路维修
题目描述：

每条电线可旋转 (90^circ)指向另一方向，则求从左上角到右下角最少要旋转的次数

算法分析：

前言：为了测试算法速度，本题没有谜の卡常

(BFS ?) 貌似对我这样的蒟蒻不太友好。该题本质上是沿对角线有一条路径，只不过其中顺着原电线方向的权值为(0)，反之为(1)，这样跑一遍(Dijkstra)即可。（自从过于不友好的 P4779 单源最短路径（标准版）后就转用(Dijkstra)）果断套堆优化模板——

突然发现：N*M=250000 ???
那前面的(WA)呢？经过深思熟虑，突然发现：对角线的连线是(N*M)，这就意味着图是以点的形式呈现时，应是((N+1)times(M+1))，果断套堆优化模板（第一次用(class)还有点小激动）——

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #define in(x) x=read(); using namespace std; const int maxN=1000001,maxM=1000001,maxQ=500; class algorithm { public: int dis[maxN+1]; void addedge(int x,int y,int value) { tot++; edge[tot].from=x;edge[tot].to=y; edge[tot].value=value; edge[tot].next=head[x]; head[x]=tot; } void addtwo(int x,int y,int value) { addedge(x,y,value); addedge(y,x,value); } void clear() { memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(head,0,sizeof(head)); tot=0; } void dijkstra(int s) { dis[s]=0; q.push(make_pair(0,s)); while(q.size()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=true; for(int i=head[x];i;i=edge[i].next) { if(dis[edge[i].to]>dis[x]+edge[i].value) { dis[edge[i].to]=dis[x]+edge[i].value; q.push(make_pair(-dis[edge[i].to],edge[i].to)); } } } } private: struct Node { int value,from,to,next; }edge[maxM+1]; int head[maxN+1],tot; bool vis[maxN+1]; priority_queue<pair<int,int> > q; }; int n,m,x,y,z; char map[maxQ+1][maxQ+1]; algorithm task; void subtask(); inline int read(); int main() { subtask(); return 0; } void subtask() { task.clear(); in(n); in(m); n++; m++; for(int i=1;i<n;i++) scanf("%s",map[i]+1); for(int i=1;i<n;i++) for(int j=1;j<m;j++) if(map[i][j]==92) { task.addtwo(i*m-m+j,i*m+j+1,0); task.addtwo(i*m-m+j+1,i*m+j,1); } else { task.addtwo(i*m-m+j,i*m+j+1,1); task.addtwo(i*m-m+j+1,i*m+j,0); } task.dijkstra(1); if(task.dis[n*m]==0x3f3f3f3f) printf("NO SOLUTIONn"); else printf("%dn",task.dis[n*m]); } inline int read() { char ch=getchar(); int num=0,f=1; while((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();} while(ch>='0' && ch<='9') { num=num*10+ch-'0'; ch=getchar(); } return num*f; }

——然而并不是(AC)。那几个TLE是什么意思！
经过认真观察，突然发现：

时空限制 150ms / 128MB

显然，用(priority queue)是不够快的（然而吸氧过了），那当然是要用线段树优化了（堆：？？？），然后就去了解了一下线段树优化 (Dijkstra)

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #define ls k<<1 #define rs k<<1|1 #define mid ((l+r)>>1) #define in(x) x=read(); using namespace std; const int maxN=500001,maxM=1000001; const int inf=0x3f3f3f3f,maxQ=500; class algorithm { public: int dis[maxN+1]; void addedge(int x,int y,int value) { tot++; edge[tot].from=x;edge[tot].to=y; edge[tot].value=value; edge[tot].next=head[x]; head[x]=tot; } void addtwo(int x,int y,int value) { addedge(x,y,value); addedge(y,x,value); } void clear() { memset(dis,0x3f,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(head,0,sizeof(head)); memset(sum,0x3f,sizeof(sum)); tot=0; } void update(int k,int l,int r,int u,int w) { if(l==r) {sum[k]=w; return;} if(u<=mid) update(ls,l,mid,u,w); else update(rs,mid+1,r,u,w); pushup(k); } int query(int k,int l,int r) { if(l==r) return l; if(sum[ls]<sum[rs]) return query(ls,l,mid); else return query(rs,mid+1,r); } void dijkstra(int s,int n) { dis[s]=0; update(1,1,n,s,0); while(sum[1]^inf) { int x=query(1,1,n); update(1,1,n,x,inf); for(int i=head[x];i;i=edge[i].next) if(dis[edge[i].to]>dis[x]+edge[i].value) { dis[edge[i].to]=dis[x]+edge[i].value; update(1,1,n,edge[i].to,dis[edge[i].to]); } } } private: struct Node { int value,from,to,next; }edge[maxM+1]; int head[maxN+1],tot,sum[4*maxN+1]; bool vis[maxN+1]; void pushup(int k) {sum[k]=min(sum[ls],sum[rs]);} }; int n,m,x,y,z; char map[maxQ+1][maxQ+1]; algorithm task; void subtask(); inline int read(); int main() { subtask(); return 0; } void subtask() { task.clear(); in(n); in(m); n++; m++; for(int i=1;i<n;i++) scanf("%s",map[i]+1); for(int i=1;i<n;i++) for(int j=1;j<m;j++) if(map[i][j]==92) { task.addtwo(i*m-m+j,i*m+j+1,0); task.addtwo(i*m-m+j+1,i*m+j,1); } else { task.addtwo(i*m-m+j,i*m+j+1,1); task.addtwo(i*m-m+j+1,i*m+j,0); } task.dijkstra(1,n*m); if(task.dis[n*m]==0x3f3f3f3f) printf("NO SOLUTIONn"); else printf("%dn",task.dis[n*m]); } inline int read() { char ch=getchar(); int num=0,f=1; while((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();} while(ch>='0' && ch<='9') { num=num*10+ch-'0'; ch=getchar(); } return num*f; }

令人欣慰的绿色：

然而并没有（逃）
普通线段树同学不够优秀（然而吸氧又过了），那当然是要用zkw线段树优化了（线段树：？？？），然后就又去借(chao)鉴(lai)了一下zkw线段树优化 (Dijkstra)

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define ls x<<1 #define rs x<<1|1 #define in(x) x=read(); using namespace std; const int maxN=500001,maxM=1000001; const int inf=0x7fffffff,maxQ=500; class algorithm { public: int dis[maxN+1],ans[maxN+1]; inline void build(int size) { for(leaf=1;leaf<=size;leaf<<=1); leaf--; for(int i=1;i<=size;++i) tree[leaf+i]=i; } void update(int x,int y) { dis[x]=y; x+=leaf; x>>=1; while(x) { tree[x]=(dis[tree[ls]]<dis[tree[rs]])?tree[ls]:tree[rs]; x>>=1; } } inline void addedge(int x,int y,int value) { edge[++tot].from=x;edge[tot].to=y; edge[tot].value=value; edge[tot].next=head[x]; head[x]=tot; } inline void addtwo(int x,int y,int value) { addedge(x,y,value); addedge(y,x,value); } inline void clear() { memset(dis,0x3f,sizeof(dis)); memset(tree,0,sizeof(tree)); memset(ans,0x3f,sizeof(ans)); tot=0; } void dijkstra(int s,int size) { build(size); dis[s]=0;int x=s,dist; for(int i=1;i<=size;++i) { dist=ans[x]=dis[x]; update(x,inf); for(int i=head[x];i;i=edge[i].next) if(dis[edge[i].to]<inf && dis[edge[i].to]>dist+edge[i].value) update(edge[i].to,dist+edge[i].value); x=tree[1]; } } private: struct Node { int value,from,to,next; }edge[maxM+1]; int head[maxN+1],tot,tree[maxN<<2],leaf; }; int n,m,x,y,z; char map[maxQ+1][maxQ+1]; algorithm task; void subtask(); inline int read(); int main() { subtask(); return 0; } void subtask() { task.clear(); in(n); in(m); n++; m++; for(int i=1;i<n;i++) scanf("%s",map[i]+1); for(int i=1;i<n;i++) for(int j=1;j<m;j++) if(map[i][j]==92) { task.addtwo(i*m-m+j,i*m+j+1,0); task.addtwo(i*m-m+j+1,i*m+j,1); } else { task.addtwo(i*m-m+j,i*m+j+1,1); task.addtwo(i*m-m+j+1,i*m+j,0); } task.dijkstra(1,n*m); if(task.ans[n*m]!=0x3f3f3f3f) printf("%d",task.ans[n*m]); else printf("NO SOLUTION"); } inline int read() { char ch=getchar(); int num=0,f=1; while((ch<'0' || ch>'9') && ch!='-') ch=getchar(); if(ch=='-') {f=-1; ch=getchar();} while(ch>='0' && ch<='9') { num=num*10+ch-'0'; ch=getchar(); } return num*f; }

真 · 令人欣慰的绿色（无吸氧）：