纯属玄学做法，要学正解的请跳过这篇
有一次集训模拟赛，直接拿了NOIp原题卷当试卷。我看到这道题，就打了个纯BFS暴力，交洛谷60分，结果真正评测的时候我以最后一个点1.000s的时间获得了100分的好成绩。
于是我意识到这可以是一道卡常练习题。所谓卡常，就是通过优化复杂度中的常数因子使原本超出时间或空间限制（本题是时间）的算法能通过。
普通暴力
我们可以考虑在搜索时用下面的的结构来存储状态：
struct Status{ int ex,ey,sx,sy; // ex,ey是空格的位置，sx,sy是当前绿色棋子的位置。 signed step; // 记录步骤数 inline signed toInt() { return (ex<<15)|(ey<<10)|(sx<<5)|sy; } // 使用这个toInt函数，可以将当前状态转化为一个整数，这样就可以使用一个数组来判重。 // 由于n和m只有30，显然用32做进制非常好。不难证明只需一个1048576大小的数组 }
搜索时我们枚举空白格子周边的4个格子，并考虑将空白格子移动到这4个格子（即，将这个棋子移到空白格子中）。
如果枚举到的周边的格子坐标是(sx,sy)，那么要交换sx和ex，sy和ey。否则只需移动ex和ey即可。
然后bfs就很容易写出来了。这是我们最初的纯暴力版本。
#include<bits/stdc++.h> using namespace std; int n,m,q; int a[31][31]; struct Status{ int ex,ey,sx,sy; int step; Status() { } Status(int _ex,int _ey,int _sx,int _sy): ex(_ex),ey(_ey),sx(_sx),sy(_sy) { } int toInt() { return ex*31*31*31+ ey*31*31+ sx*31+ sy; } }que[810010]; //数组模拟队列 int tx,ty; int h,t; //首尾下标 bool vis[1048576]; //定义“相邻的4个格子”相对当前格子的位置 int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int bfs() { while(h<t) { h++; if(que[h].sx==tx && que[h].sy==ty) { return que[h].step; } for(int i=0;i<4;i++) { int ex2=que[h].ex+dx[i]; int ey2=que[h].ey+dy[i]; if(ex2<1 || ex2>n || ey2<1 || ey2>m) continue; if(a[ex2][ey2]==0) continue; Status tmp; tmp.ex=ex2; tmp.ey=ey2; tmp.sx=que[h].sx; tmp.sy=que[h].sy; tmp.step=que[h].step+1; if(ex2==que[h].sx && ey2==que[h].sy) { tmp.sx=que[h].ex; tmp.sy=que[h].ey; } if(vis[tmp.toInt()]) continue; vis[tmp.toInt()]=1; t++; que[t]=tmp; if(que[t].sx==tx && que[t].sy==ty) { return que[t].step; } } } return -1; } int main() { //freopen("puzzle.in","r",stdin); //freopen("puzzle.out","w",stdout); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } for(int i=1;i<=q;i++) { scanf("%d%d%d%d%d%d", &que[1].ex,&que[1].ey,&que[1].sx,&que[1].sy, &tx,&ty); que[1].step=0; h=0; t=1; for(int i=0;i<=1048575;i++) { vis[i]=0; } printf("%d\n",bfs()); } }
这个程序能够获得60分的成绩。
很容易发现，进行一次bfs的时间复杂度为ReferenceError: katex is not defined，因为最多有ReferenceError: katex is not defined种状态，此时最坏时间复杂度为ReferenceError: katex is not defined，即ReferenceError: katex is not defined。再乘上ReferenceError: katex is not defined，就是ReferenceError: katex is not defined。再加上bfs有较大的常数，不死就怪。
但是显然ReferenceError: katex is not defined是跑不满的，因此只需优化一下常数，就能获得更好的成绩。
进行常数优化
仔细观察程序，不难发现，很多地方可以优化常数。
手动O3+Ofast
%:pragma GCC optimize("inline,Ofast",3) 或 #pragma GCC optimize("inline,Ofast",3)
一定要加载头文件前面！
避免初始化清空vis数组
显然vis数组很大，清空浪费时间。
我们考虑维护当前在进行第几次BFS。如果vis数组中的值等于当前次数，才认为这个状态出现过。同样，标记vis时标记为当前次数。
这样就可以不清空vis数组。
使用快读快写。
inline void read(int &ret) { ret=0; register char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) {ret=ret*10+(c-'0');c=getchar();} } void __write(signed x) { if(!x) return; __write(x/10); putchar('0'+x%10); } inline void write(const signed &x,char e='\0') { if(x>0) __write(x); else if(x==0) putchar('0'); else {putchar('-');__write(-x);} if(e) putchar(e); } 主程序中： read(n);read(m);read(q); write(bfs(),'\n'); 等等...
使用指针来完成队列操作
实际上，指针比数组下标访问更快。假设有一个int数组arr，那么我们可以定义一个指针int *ptr = arr，此时ptr指向arr[0]，ptr+1指向arr[1]，以此类推。
取值： cout<<(*ptr)<<endl; 赋值： (*ptr) = 25 假设ptr指向的是Status类型，对其step赋值和取值 ptr->size = 12 cout<<(ptr->size)<<endl
我们可以将队列的首尾下标变成首尾指针。那么我们仍然可以使用++h，++t这种方式进行队列模拟。
加register, inline
inline可以用在非递归函数的类型前，防止不必要的进栈操作。
register可以用在局部变量的类型前，这样可以定义将变量存在寄存器中，加快访问速度。但是寄存器容量小，不宜使用太多register，否则系统会花时间将较早定义的元素扔出寄存器，放入内存，造成负优化。
修改dx, dy数组，防止搜索时单步回退
我们注意到，BFS扩展（转移）部分常数较大
int dx[4]={0,1,-1,0}; int dy[4]={-1,0,0,1};
这样定义的dx,dy有个性质，即，dx和dy中分别取下标相加等于3的两个元素，相加必等于0。
我们可以给Status结构添加一个属性tp，即，上次使用的dx和dy中的哪个元素。
下一次扩展时，若枚举的i与上次的tp相加得3，说明这样扩展必将退回到上一个状态。显然这个状态是没用的（判重时会continue掉）
对于初始化，只需初始化tp=-1即可（因为没有任何i会与-1相加为3）
最后的代码长这样
// status: [status_undefined] // oj: [luogu] %:pragma GCC optimize("inline,Ofast",3) #include<stdio.h> #include<ctype.h> #define int short // short卡常 int n,m,q; int a[31][31]; struct Status{ int ex,ey,sx,sy; signed step; // 步骤数等地方不可以使用short，可能会爆 int tp; inline signed toInt() { return (ex<<15)|(ey<<10)|(sx<<5)|sy; } }que[810010]; int tx,ty; Status *h,*t; //用指针 int vis[1048576]; int vis_t=0; int dx[4]={0,1,-1,0}; int dy[4]={-1,0,0,1}; inline signed bfs() { ++vis_t; while(h!=t) { ++h; if(h->sx==tx && h->sy==ty) { return h->step; } for(register int i=0;i<4;i++) { if(i+h->tp==3) continue; //相加等于3的优化 register int ex2=h->ex+dx[i]; register int ey2=h->ey+dy[i]; if(ex2<1 || ex2>n || ey2<1 || ey2>m) continue; if(!a[ex2][ey2]) continue; ++t; t->ex=ex2; t->ey=ey2; t->sx=h->sx; t->sy=h->sy; if(ex2==h->sx && ey2==h->sy) { t->sx=h->ex; t->sy=h->ey; } register signed _t=t->toInt(); if(vis[_t]==vis_t) {--t;continue;} t->step=h->step+1; t->tp=i; vis[_t]=vis_t; if(t->sx==tx && t->sy==ty) { return t->step; } } } return -1; } inline void read(int &ret) { ret=0; register char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) {ret=ret*10+(c-'0');c=getchar();} } void __write(signed x) { if(!x) return; __write(x/10); putchar('0'+x%10); } inline void write(const signed &x,char e='\0') { if(x>0) __write(x); else if(x==0) putchar('0'); else {putchar('-');__write(-x);} if(e) putchar(e); } signed main() { read(n);read(m);read(q); for(int i=1;i<=n;i++) { register int *tt = a[i]; for(int j=1;j<=m;j++) { ++tt; read(*tt); } } t=que+1; t->tp = -1; t->step = 0; // 无需每次初始化的东西放到循环外 for(register int i=1;i<=q;i++) { h=que; t=que+1; read(t->ex);read(t->ey);read(t->sx);read(t->sy); read(tx);read(ty); write(bfs(),'\n'); } }
Comments | NOTHING