1 条题解
-
1
这道题主要还是考一个想法。
##算法分析:逆序操作+并查集
首先考虑按照题意模拟整个过程。单次
PAINT
指令时间复杂度为 ,一共有 个指令,总复杂度为 ,显然不能承受。期间有SAVE
指令,单次时空复杂度均为 ,总时空复杂度为 ,在时空上均不能承受。按原题数据范围,暴力做法预计得分 50pts。首先考虑优化空间。
我们回顾一道题 Poj-2528 Mayor's posters,这道题是说在一个展板上依次贴海报,问最后能看到的海报有哪些。在这道题中,我们采用了按时间从后往前操作的技巧。因为后贴的一定在上面,因此不必改变。在贴较早的海报时,只需考虑是否存在空位即可。
在本题中,我们同样可以采用从后往前染色的方法逆序操作。事先储存所有的指令,并记录每一个
SAVE
指令的位置。遇到LOAD
指令时,直接跳过中间的所有步骤,从对应的SAVE
指令开始往前操作。这样就无需用 的空间存下之前SAVE
的状态,只需记录当前的状态。最后直接输出即可。在优化完空间后,时间复杂度仍为 。接下来我们考虑优化时间。
事实上,可优化的仅有
PAINT
这一个指令。前面说过,逆序操作时,已经被染色的格子不会再次被染色,因此在执行PAINT
指令时,可以考虑跳过已经被染过色的格子。这里提供一种利用并查集的做法。首先为每一行建立一个并查集。染色时,将染色区域第 个格子与第 个格子并到一起。当再次扫描到 时,直接从 开始染色。这样就直接跳过了 这一部分的格子。需要注意的时,在合并时,需要将右侧的格子作为新的根,即将 合并到 中,这样才能在下一次操作时定位到正确的位置。
另外,可以用链表或者
STL_set
来替代并查集的作用。但综合分析三者优缺点,链表的开始位置不易寻找,且代码调试难度相对较大,STL-set
查询的时间复杂度为 ,比前两者都大,容易超出时间限制。因此无论从码量或是时间上并查集都是较为合适的选择。##code:
#include<bits/stdc++.h> #define reg register #define F(i,a,b) for(reg int i=a;i<=b;++i) using namespace std; inline int read(); const int N=1e3+10,M=1e5+1; int n,k,m,a[N][N],sav[M],cnt; struct Union_set {//并查集 int fa[N]; Union_set(){ F(i,1,N-1)fa[i]=i; } int find(int x) {//找代表元 return fa[x]==x?x:fa[x]=find(fa[x]); } inline void add(int u,int v){ u=find(u),v=find(v),fa[u]=v; }//将 u 合并到 v 下 } f[N]; struct Comd {//储存指令 char c[10]; int k,x1,x2,y1,y2; inline void inp() { scanf("%s",c+1); if(c[1]!='S')k=read(); if(c[1]=='P')x1=read()+1,y1=read()+1,x2=read()+1,y2=read()+1; } } Com[M]; inline void paint(Comd cur){//染色 reg int y; F(i,cur.x1,cur.x2){ y=cur.y1+((i-cur.x1)&1); //y 为本行开始染色的位置 for(reg int k=f[i].find(y);k<=cur.y2;k=f[i].find(k)){ a[i][k]=cur.k;//染色 f[i].add(k,k+2);//向右合并 } } } int main() { n=read(),k=read(),m=read(); F(i,1,n)F(j,1,n)a[i][j]=1; F(i,1,m) { Com[i].inp(); if(Com[i].c[1]=='S')sav[++cnt]=i;//储存 SAVE 指令的位置 } for(reg int i=m;i;--i){ Comd& cur=Com[i]; if(cur.c[1]=='S')continue; if(cur.c[1]=='L')i=sav[cur.k]; if(cur.c[1]=='P')paint(cur); } F(i,1,n){ F(j,1,n)printf("%d ",a[i][j]); putchar('\n'); } return 0; } inline int read() { reg int x=0; reg char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; }
欢迎交流讨论,请点个赞哦~
- 1
信息
- ID
- 3189
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 4
- 已通过
- 3
- 上传者