这道大递归我一开始就找对了方向,不过了MLE,然后从网上搜索到了一个贼有用的概念——尾递归,即如果递归的下一句就是return且没有返回值或者返回值不含有递归函数则编译器会做优化,不会压入新的函数而是直接把用新函数覆盖原函数,从而大大减少MLE的可能性。这样直接就把125MB+ 的东西变成了0.5MB左右,使得此前减少递归函数的几个int变量以及把int变成short int的这种常量级优化显得毫无意义喽。
所以尾递归真的太有用了,在递归后直接加一句“return;”就直接把问题解决了。特别是对于我这种特喜欢写递归的人,写递归简直太容易了,比循环容易多了。有了尾递归,便是解决了一大隐患。
但是,解决了MLE的问题后变成TLE了仍只有56分,不只下一步怎么做了
TLE-Code
#include <iostream>
using namespace std;
#define mx ((ax+bx-1)>>1)
#define my ((ay+by-1)>>1)
int x,y,k;
void dfsf(int ax,int ay,int bx,int by,int status)
{
if(bx<=ax)
return;
if(bx-ax==1)
{
switch(status)
{
case 1:printf("%d %d %d\n",bx,by,status);break;
case 2:printf("%d %d %d\n",bx,ay,status);break;
case 3:printf("%d %d %d\n",ax,by,status);break;
case 4:printf("%d %d %d\n",ax,ay,status);break;
}
return;
}
dfsf(((ax+mx-1)>>1)+1,((ay+my-1)>>1)+1,(mx+bx)>>1,(my+by)>>1,status);
if(status!=1)dfsf(ax,ay,mx,my,4);
if(status!=2)dfsf(ax,my+1,mx,by,3);
if(status!=3)dfsf(mx+1,ay,bx,my,2);
if(status!=4)dfsf(mx+1,my+1,bx,by,1);
return;
}
void dfsg(int ax,int ay,int bx,int by)
{
if(ax>=bx&&bx>=by)return;
if(x>mx&&y>my)
{
dfsf(ax,ay,bx,by,4);
dfsg(mx+1,my+1,bx,by);
return;
}
else if(x>mx&&y<=my)
{
dfsf(ax,ay,bx,by,2);
dfsg(ax,my+1,mx,by);
return;
}
else if(x<=mx&&y>my)
{
dfsf(ax,ay,bx,by,3);
dfsg(ax,my+1,mx,by);
return;
}
else
{
dfsf(ax,ay,bx,by,1);
dfsg(ax,ay,mx,my);
return;
}
}
int main()
{
scanf("%d%d%d",&k,&x,&y);
dfsg(1,1,1<<k,1<<k);
return 0;
}