[TS-A1488][2013中国国家集训队第二次作业]魔法波[高斯消元]
2024-10-01 01:49:01
暴力直接解异或方程组,O(n^6)无法接受,那么我们考虑把格子分块,横着和竖着分别分为互不影响的块,这样因为障碍物最多不超过200个,那么块的个数最多为2*(800+200)=2000个,最后用bitset优化即可。
#include <bits/stdc++.h> using namespace std; int n,cnt,Pos[],Right[],Left[];
int Crs[][],Dwn[][],MID;
char str[][]; bitset<>eq[]; void Gauss()
{
int i,j;
for(i=;i<=cnt;++i)
{
j=i;
while(!eq[j][i] && j<=cnt)j++;
if(j==cnt+)continue;
if(j!=i)swap(eq[j],eq[i]);
for(j=;j<=cnt;++j)
if(j!=i && eq[j][i])eq[j]^=eq[i];
}
return ;
} int main()
{
int i,j,temp; scanf("%d",&n); for(i=;i<=n;++i)
scanf("%s",str[i]+); for(i=;i<=n;++i)
str[][i]=str[i][]=str[i][n+]=str[n+][i]='X'; cnt=; for(j=;j<=n;++j) for(i=;i<=n+;++i)
{
if(str[i][j]!='X')Crs[i][j]=cnt;
if(str[i-][j]=='X' && str[i][j]!='X')Left[cnt]=i,Pos[cnt]=j;
if(str[i+][j]=='X' && str[i][j]!='X')Right[cnt]=i,cnt++;
} MID=cnt-; for(i=;i<=n;++i) for(j=;j<=n+;++j)
{
if(str[i][j]!='X')Dwn[i][j]=cnt;
if(str[i][j-]=='X' && str[i][j]!='X')Left[cnt]=j,Pos[cnt]=i;
if(str[i][j+]=='X' && str[i][j]!='X')Right[cnt]=j,cnt++;
} cnt--; for(i=;i<=MID;++i)
{
temp=;
eq[i].set(i); for(j=Left[i];j<=Right[i];++j)
{
eq[i][Crs[j][Pos[i]]]=eq[i][Crs[j][Pos[i]]]^;
eq[i][Dwn[j][Pos[i]]]=eq[i][Dwn[j][Pos[i]]]^;
temp^=(str[j][Pos[i]]=='X'?:str[j][Pos[i]]-);
temp^=;
} eq[i][cnt+]=temp;
#ifdef Debug
cerr << eq[i] << endl;
#endif
} for(i=MID+;i<=cnt;++i)
{
temp=;
eq[i].set(i); for(j=Left[i];j<=Right[i];++j)
{
eq[i][Crs[Pos[i]][j]]=eq[i][Crs[Pos[i]][j]]^;
eq[i][Dwn[Pos[i]][j]]=eq[i][Dwn[Pos[i]][j]]^;
temp^=(str[Pos[i]][j]=='X'?:str[Pos[i]][j]-);
temp^=;
} eq[i][cnt+]=temp;
#ifdef Debug
cerr << eq[i] << endl;
#endif
} Gauss(); #ifdef Debug
cerr << endl;
for(i=;i<=cnt;++i)
cerr << eq[i] << endl;
cerr << endl;
#endif for(i=;i<=n;++i)
{
for(j=;j<=n;++j)
{
printf("%d",str[i][j]=='X'?:(^eq[Crs[i][j]][cnt+]^eq[Dwn[i][j]][cnt+]
^(str[i][j]-)));
}
printf("\n");
} return ;
}
最新文章
- linux查看是什么操作系统是什么命令
- alphaBlend
- SVN安装配置和使用教程
- sql 流水号
- js_sl 延迟菜单
- OC: Block回调的使用demo
- 判断Featureclass的类型
- 飞行器的Pitch Yaw Roll概念图解
- 嵌入式Linux启动过程中的问题积累
- The Class Loader Hierarchy--转载
- hdu1166树状数组
- NgRx/Store 4 + Angular 5使用教程
- Spring Security 入门(1-2)Spring Security - 从 配置例子例子 开始我们的学习历程
- Activity、Fragment、Dialog基类简单整理
- Solrcloud(Solr集群)
- Rose 2003使用的问题
- thinkphp 3.2.1 URL 大小写问题 下面有具体说明
- 【转】七牛免费SSL证书,配置自定义域名CDN加速
- adb shell命令行
- 用css写出下拉框(代码转自wq群)