BZOJ3189 : [Coci2011]Slika
2024-10-18 18:28:06
通过离线将操作建树,即可得到最终存在的操作。
然后逆着操作的顺序,倒着进行染色,对于每行维护一个并查集即可。
时间复杂度$O(n(n+m))$。
#include<cstdio>
const int N=1010,M=100010;
int n,m,i,j,x,C,X1,Y1,X2,Y2,f[M],cnt,pos[M],e[M][5],col[N][N];char ch;
struct DSU{
int f[N];
void init(){for(int i=0;i<=n+1;i++)f[i]=i;}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
}g[N];
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
int main(){
read(n),read(m),read(m);
for(i=1;i<=m;i++){
while((ch=getchar())!='P'&&ch!='S'&&ch!='L');
if(ch=='P'){
f[i]=x;x=i;
for(j=0;j<5;j++)read(e[i][j]);
}
if(ch=='S')pos[++cnt]=x;
if(ch=='L')read(x),x=pos[x];
}
for(i=0;i<n;i++)for(j=0;j<n;j++)col[i][j]=1;
for(i=0;i<n;i++)g[i].init();
while(x){
C=e[x][0],X1=e[x][1],Y1=e[x][2],X2=e[x][3],Y2=e[x][4];
for(i=X1;i<=X2;i+=2)for(j=g[i].F(Y1);j<=Y2;j=g[i].F(j+2))g[i].f[j]=j+2,col[i][j]=C;
for(i=X1+1;i<=X2;i+=2)for(j=g[i].F(Y1+1);j<=Y2;j=g[i].F(j+2))g[i].f[j]=j+2,col[i][j]=C;
x=f[x];
}
for(i=0;i<n;puts(""),i++)for(j=0;j<n;j++)printf("%d ",col[i][j]);
return 0;
}
最新文章
- Git使用详细教程(二)
- loadrunner数据库MySQL参数化列表乱码问题
- C++程序结构---1
- Delphi中nil和null的区别
- Windows Phone 同步方式获取网络类型
- java:高速排序算法与冒泡排序算法
- Ext.ux.form.SuperBoxSelect
- FZU 2089 数字游戏
- PKU-1704-Georgia and Bob
- 【技术干货】听阿里云CDN安防技术专家金九讲SystemTap使用技巧
- linux下Tomcat 安装后执行startup.sh,出现– Cannot find …bin/catalina.sh
- vue2.0项目引入element-ui
- Python_FTP通讯软件
- .NET快速信息化系统开发框架 V3.2 ->; WinForm“组织机构管理”界面组织机构权限管理采用新的界面,操作权限按模块进行展示
- WPF-------依赖项属性
- chrome 下 input[file] 元素cursor设置pointer不生效的解决
- “一切都是消息”--iMSF(即时消息服务框架)之【发布-订阅】模式
- Linux设置和查看环境变量的方法 详解
- Html5多媒体相关的API---video
- PLsql登录数据库提示密码即将过期-
热门文章
- postgresql导入及导出
- win7下python3.4 ImportError: No module named &#39;MySQLdb&#39;错误解决方法
- bootstrap的验证和确认对话框
- JustSniffer
- Sexagenary Cycle(天干地支法表示农历年份)
- Big Data, MapReduce, Hadoop, and Spark with Python
- Java代码实现excel数据导入到Oracle
- OGG异常处理
- hdu 3032 sg打表找规律 *
- Linux下常用命令