JZOJ100048 【NOIP2017提高A组模拟7.14】紧急撤离
题目
题目大意
给你一个01矩阵，每次询问从一个点是否可以走到另一个点。
每次走只能往右或者往下。
思考历程
这题啊，我想的时候真的是脑洞大开……
首先，我一眼看下去，既然要询问是否联通，那么能不能求出它们的最短路，看看是不是它们的曼哈顿距离？
看到数据范围之后这个想法彻底凉凉……
然后就开始考虑一些正经的方法……
首先，考虑如何扫描线……类似扫描线的，扫一扫，维护一下，说不定就可以了呢？
然后，我发现无论如何，我都难以逃脱O(n2m2)O(n^2m^2)O(n2m2)，就算是使用bitset也不行。
这样不行啊，我就考虑分治？
如何分治？
每次在中间的这一条线上开始，向两边进行转移。转移什么？转移每个点到这条线上连通的状态……
用bitset可以优化一下。
但是又感觉，这个方法好像过不去，所以，我又继续向其他的做法。
然后就想到了分块！
如何分块呢？设块的行数为KKK，那么我们在每个块的边界那里，搞一搞类似上面的转移。
然后我们在所有的边界之间，求出它们的连通性。
推了一波复杂度，好想很优秀！
好开心好开心……
然后打了几行，突然发现：时间复杂度好像算错了！
非常不爽，又算了一遍。发现还是算错了，再算一遍……
什么，这么慢，连分治都不如？
又看看时间，似乎不多了……
我绝望地打了个暴力，用bitset随便优化了一下……
正解
其实正解在比赛时已经想到了。
只不过觉得过不了……
这题的正解就是分治，和上面说的一模一样！
非常不爽……
这次说详细一些：
按行或列分治（其实应该按列分治，具体原因……），下面一行为准。
我们将矩阵分成上下两个部分。
对于上面，我们设fi,jf_{i,j}fi,j表示点(i,j)(i,j)(i,j)到中间的这一行上每个点的状态。
对于下面，我们设gi,jg_{i,j}gi,j表示中间这一行上的每个点到(i,j)(i,j)(i,j)的状态。
其实两个是相反的，具体怎么转移显然。
那么对于询问的两个点，如果它们之间的路径上会经过这一行，那就枚举经过行上的哪一个点，计算一下是否联通就好了。至于没有经过的，直接递归分治下去。
然后分析一下时间复杂度。
首先我们知道，很显然的，分治只有lgn\lg nlgn层。
对于每一层，我们需要处理nm2nm^2nm2次，因为我们考虑同一列上的点，它们转移所耗费的时间为nmnmnm，即为整个平面。由于每一行有mmm个东西，所以就是nm2nm^2nm2次。
综上，转移的总时间是O(nm2lgn)O(nm^2\lg n)O(nm2lgn)。
然后就是处理询问的时间。
我们首先将询问全部列在一起，然后在处理的时候，将左边的区间放左边，将右边的区间放右边，穿过中间行的区间直接处理。时间复杂度可以这么理解：对于每一个询问，它相当于在这棵分治所形成的的二叉树上面往下走，那么每个的时间为O(lgn)O(\lg n)O(lgn)。然后我们一共有qqq个询问，所以时间复杂度为O(qlgn)O(q\lg n)O(qlgn)。还有每次处理一个询问都需要O(qm)O(qm)O(qm)的时间
为什么时间复杂度好像和题解不一样，难道是我分析错了？还是lgn\lg nlgn太小以至于题解不屑于注意？
综上所述，时间复杂度是O(nm2lgn+q(m+lgn))O(nm^2\lg n+q(m+\lg n))O(nm2lgn+q(m+lgn))。
这个时间复杂度似乎过不去，然而，由于有bitset优化，会快很多。
这题的正解就是这么简单……
数据上的问题
我要吐槽一下，这题的数据太可恶了！
我打出来之后，发现自己TLE！怎么可能？
然后，就是疯狂的卡常数历程……最终以990+的好时间卡了过去。
我不禁深思，为什么我的程序这么慢？我是不是该重修卡常技能？
看看别人的程序，似乎没有什么特别的地方啊！
在我绝望之际，忽然，我发现了惊天的秘密！
为什么他们是按列分治的？我翻遍所有的程序，发现AC的都是按列分治的。有一个按行分治的人过了，但开了O2。
按理来说，按列分治和按行分治的时间复杂度是一样的。因为它们本质上都是同一个道理。
并且，在枚举的过程中，按行分治和按列分治在常数上的差异其实不大。
（我们可以想一想，不管是按行分治还是按列分治，都是将矩阵分为两个部分。这两个部分都是一个矩形，从右下角枚举到左上角，所以说常熟还是差不多的。卡过常数的人们都知道，在枚举的过程中，尽量一个接一个地枚举，不要跳着来。可问题是，都是一个接一个地枚举啊！）
所以说，原因只能归结于数据。
数据害死人！！！
然后我就脑补了一下出数据的场景：
出题人：这题要卡常才能过！所以我的数据要出大一些！
然后出了各种大数据，将标程可以过的留下来……
然而标程是按列分治的，并没有按行分治的，所以按行分治的不一定能过……
这只能怪出题人了。
另外的吐槽
我还发现，这题可以锻炼我的卡常技巧！
如何在卡常的情况下，依然能保持程序的美观？
~~众所周知，~~我的程序是很美观的……
然后请看看我的代码。
代码
这代码可能有点神仙，毕竟，美观与常数不可兼得！
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500
#define Q 600000
struct bitset{/手打bitset
unsigned long long b[8];
inline void reset(){//清空
memset(b,0,sizeof b);
}
inline bool operator[](int y){//查询某一个位上的值
return b[y>>6]>>(y&63)&1;
}
inline void set(int y){
b[y>>6]|=1ll<<(y&63);//将某一个位上的值的值赋为1
}
inline void getor(bitset *ano){//将当前的bitset和其它bitset取or赋给自己
b[0]|=ano->b[0];
b[1]|=ano->b[1];
b[2]|=ano->b[2];
b[3]|=ano->b[3];
b[4]|=ano->b[4];
b[5]|=ano->b[5];
b[6]|=ano->b[6];
b[7]|=ano->b[7];
}
inline void get(bitset *x,bitset *y){//将自己的值赋为两个bitset的or值
b[0]=x->b[0]|y->b[0];
b[1]=x->b[1]|y->b[1];
b[2]=x->b[2]|y->b[2];
b[3]=x->b[3]|y->b[3];
b[4]=x->b[4]|y->b[4];
b[5]=x->b[5]|y->b[5];
b[6]=x->b[6]|y->b[6];
b[7]=x->b[7]|y->b[7];
}
} bs[N*N+1];
int cnt;
inline int input(){//读入优化
char ch=getchar();
while (ch<'0' || '9'<ch)
ch=getchar();
int res=0;
do{
res=res*10+ch-'0';
ch=getchar();
}
while ('0'<=ch && ch<='9');
return res;
}
int n,m;
char mat[N+1][N+1];
int q;
struct Question{
int a,b,c,d;
int num;
} _t[Q+1],_tmp[Q+1],*t,*tmp;
bitset *f[N][N],*g[N][N];//为什么用指针呢？因为我们很容易发现，有时只会从一个转移，那么指针就可以大大地加快速度。具体见下面。
void dfs(int,int,int,int);
bool ans[Q+1];
int main(){
n=input(),m=input();
for (int i=0;i<n;++i)
scanf("%s",mat[i]);
q=input();
int tmpq=q;
q=0;
t=_t,tmp=_tmp;
for (int i=1;i<=tmpq;++i){
++q;
t[q].a=input()-1,t[q].b=input()-1,t[q].c=input()-1,t[q].d=input()-1;
t[q].num=i;
if (t[q].a>t[q].c || t[q].b>t[q].d)
q--;
}
dfs(0,n-1,1,q);
for (int i=1;i<=q;++i)
if (ans[i])
printf("Safe\n");
else
printf("Dangerous\n");
return 0;
}
void dfs(int l,int r,int x,int y){//[l,r]表示行的区间，[x,y]表示询问的区间
if (l>r || x>y)
return;
int mid=l+r>>1;
cnt=0;
if (mat[mid][m-1]=='0'){
bs[++cnt].reset();
bs[cnt].set(m-1);
f[mid][m-1]=bs+cnt;
}
else
f[mid][m-1]=bs;
for (int i=m-2;i>=0;--i)
if (mat[mid][i]=='0'){
++cnt;
bs[cnt].reset();
bs[cnt].set(i);
if (mat[mid][i+1]=='0')
bs[cnt].getor(f[mid][i+1]);
f[mid][i]=bs+cnt;
}
else
f[mid][i]=bs;
for (int i=mid-1;i>=l;--i)
if (mat[i][m-1]=='0' && mat[i+1][m-1]=='0')
f[i][m-1]=f[i+1][m-1];
else
for (;i>=l;--i)
f[i][m-1]=bs;//在转移最后一列的时候，我们发现，如果当中有一个断了，后面的就全断了
for (int i=mid-1;i>=l;--i)
for (int j=m-2;j>=0;--j)
if (mat[i][j]=='0')
if (mat[i][j+1]=='0'){
if (mat[i+1][j]=='0'){
bs[++cnt].get(f[i][j+1],f[i+1][j]);
f[i][j]=bs+cnt;
}
else
f[i][j]=f[i][j+1];
}
else{
if (mat[i+1][j]=='0')
f[i][j]=f[i+1][j];
else
f[i][j]=bs;
}
if (mat[mid][0]=='0'){
bs[++cnt].reset();
bs[cnt].set(0);
g[mid][0]=bs+cnt;
}
else
g[mid][0]=bs;
for (int i=1;i<=m-1;++i)
if (mat[mid][i]=='0'){
bs[++cnt].reset();
bs[cnt].set(i);
if (mat[mid][i-1]=='0')
bs[cnt].getor(g[mid][i-1]);
g[mid][i]=bs+cnt;
}
else
g[mid][i]=bs;
for (int i=mid+1;i<=r;++i)
if (mat[i-1][0]=='0' && mat[i-1][0]=='0')
g[i][0]=g[i-1][0];
else
for (;i<=r;++i)
g[i][0]=bs;
for (int i=mid+1;i<=r;++i)
for (int j=1;j<=m-1;++j)
if (mat[i][j]=='0')
if (mat[i][j-1]=='0'){
if (mat[i-1][j]=='0'){
bs[++cnt].get(g[i][j-1],g[i-1][j]);
g[i][j]=bs+cnt;
}
else
g[i][j]=g[i][j-1];
}
else{
if (mat[i-1][j]=='0')
g[i][j]=g[i-1][j];
else
g[i][j]=bs;
}
swap(t,tmp);//tmp表示原数组，t表示新数组，在这里交换只会交换指针
int i=x-1,j=y+1;
for (int k=x;k<=y;++k)
if (tmp[k].c<mid)//将在中间线上边和下边的区间分开，分别放在一块
t[++i]=tmp[k];
else if (tmp[k].a>mid)
t[--j]=tmp[k];
else
for (int l=tmp[k].b;l<=tmp[k].d;++l)
if (mat[mid][l]=='0' && (*f[tmp[k].a][tmp[k].b])[l] && (*g[tmp[k].c][tmp[k].d])[l]){
ans[tmp[k].num]=1;
break;
}
dfs(l,mid-1,x,i);
dfs(mid+1,r,j,y);
swap(t,tmp);//仔细想想可以发现，由下一层之间不会互相造成影响，所以这样做不会影响它的正确性。
}
简略地说一说我的各种优化
结合代码更加清晰易懂（清晰易懂个鬼啊！）
1、我们发现在DP转移的时候，经常会出现只转移一个或者是不转移的现象。那我们想一想，如果再用一个bitset将其存下，是不是一种浪费呢？因此，我们可以让几个转态共享一个结果。我们在一开始开好一个bitset内存池，在使用的时候，如果要开新值，那就在内存池里面分配一个，计算之后将当前的指针指向它。如果不用开新值，那就将当前的指针指向这个旧值的位置。
2、询问连成块。其实这个是本来就要做的，算不得优化。如果询问连成块，那就比较好处理，在枚举过程中就不会枚举到当前区间外的询问。我们可以用另一个数组，然后扫一扫区间内的所有询问，将其放在那个数组中，分成两边。然后在递归下去的时候，将两个数组交换（其实这样的正确性是很好保证的。因为处理完大区间后，小区间不会对大区间产生影响，并且小区间也不会互相产生影响，所以是正确的。还有，我发现了一直以来，我都犯了个错误：实际上，C++中的swap是交换数组里面的值，而不是交换指针。所以，直接用指针来指向数组就好了。）
3、特殊情况分开考虑，少一个if语句就少一个if语句，宁可码量大一些。
4、手打bitset。自己打的总感觉常数会小一些，并且可以直接压646464位！还有实际上bitset很好打。
5、读入优化：不解释。
6、各种剪枝判断……
7、开O2（这个优化就可以顶的过所有的优化）
说实在的，我的卡常技术已经大不如前了。
总结
首先，要信任你的时间复杂度……
如果时间复杂度是在10810^8108次方以内的，恭喜你，一般都可以过。
如果差不多的就要卡卡常数……
最后，保持信仰，在正式比赛的时候出题人不会出这样的数据……
最新文章
- 队列Queue
- Codeforces Round #338 (Div. 2)
- JAVA基于缓冲的文件读写操作
- 微软BI 之SSIS 系列 - ETL 转换时关于 Code Page (1252 and 936) 转换错误的原因和解决方法
- jquery eq 用法
- 转：Java实现几种常见排序方法
- break 和 continue
- phantomjs + selenium headless test
- SignalTap II逻辑分析仪的使用
- android学习日记12--布局管理器
- 标准程序员系列－Github篇－初始化一个代码仓库
- openstack私有云布署实践【13.2 网络Neutron-compute节点配置（办公网环境）】
- gen_create_syn.sql
- Spring Cloud下微服务权限方案
- 大前端的自动化工厂（5）—— 基于Karma+Mocha+Chai的单元测试和接口测试
- openlayers3 基础（常见方法，类及实现）
- 如何看待淘宝二手交易APP“闲鱼”推出的新功能“闲鱼小法庭”？
- [转]来扯点ionic3[7] LocalStorage的使用—以登录和注销为例
- 大数据离线分析平台 JSSDK数据收集引擎编写
- React-Native 之 FlexBox介绍和使用