CF715D Create a Maze 题解
Moya_Rao
·
·
题解
放一个基于 Fibonacci 序列的做法 qwq。
同时是本喵的第三篇黑题题解，写的不好还请各位大神谅解喵。
首先我们可以通过用 Fibonacci 序列的每项上、下连放两个的性质，构造出这样一个网格：
由[齐肯多夫定理](https://baike.baidu.com/item/%E9%BD%90%E8%82%AF%E5%A4%9A%E5%A4%AB%E5%AE%9A%E7%90%86/7612155)，任何正整数都能被表示为**若干个不相邻的 $f_i$ 的和**。于是构造这样的网格，维护两条路（黄色格子）：
右下角留白的格子是终点，紫色格子是我们要完全堵死的部分（不允许存在任何一条经过紫色格子的路抵达终点）。
**用墙壁隔开任意两种相邻颜色**（白色除外），这样整个就成了一条死路。我们为了在黄色路径部分造出恰好为 $n$ 的方案数，考虑对 $n$ 进行 Fibonacci 拆分，打开对应蓝格子与黄色路径部分的墙即可。
比如随便举个例，$n = 215 = 144+55+13+3$，那么在下图中画红色线段的部分就是打开的墙：
构造结束！这样你就可以把这题过掉了……吗？
并非，随便写个程序跑一下，或者你挨个算一下（当做红线段只有 $1$ 条的情况），会发现最坏情况下需要 $350$ 左右个墙，即使计算时存在部分重复为 $340$ 个，也是不满足题目要求 $\le 300$ 个的。
怎么办，难道思路完全错了吗？没有。思考我们在哪里的开销最大，会发现，紫色与黄色的交界处每一小块都得挡住，非常浪费，而我们的目标只是不让经过紫色格子的路径成为最终路径而已。
那能优化吗？当然能，发现只需用下图绿色线段做墙，就可以将这部分的开销直接减半：
为什么这样也能挡住啊？以左下角部分举例，发现一旦进入紫色区域，想出去只能往上走绕过去，但是题目要求只能往右或往下走，所以是不可能的。右上角部分同理。
于是你再重新算一下，发现节省了 $88$ 左右个墙壁的开销，最终墙壁个数控制在 $260$ 左右，肯定满足题目 $\le 300$ 的要求。
于是就做完了。
::::success[code && [submission](https://codeforces.com/contest/715/submission/378202008)]
```cpp
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 105;
LL T,n=46,m=47,cnt;
LL f[N],fup=88;
bool vD[N][N],vR[N][N];
LL read(){
LL su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
int main(){
T=read();
f[1]=1,f[2]=1;
for(LL i=3;i<=fup;i++)f[i]=f[i-1]+f[i-2];
for(LL i=3,j=1;i<=n;((i%2)==(j%2)?i++:j++))
if((i%2)==(j%2))vD[i-1][j]=1,vR[i][j]=1;
else vD[i][j]=1;
for(LL i=1,j=4;j<=m;((i%2)==(j%2)?i++:j++))
if((i%2)==(j%2))vR[i][j]=1;
else vR[i][j-1]=1,vD[i][j]=1;
vD[n-1][m-2]=1,vD[n-1][m-1]=1,vR[n-1][m-1]=1;
for(LL i=fup;i>=1;i--){
if(T<f[i])continue;
T-=f[i];
if(i%2)vD[(i+1)/2+1][(i+1)/2]=0;
else vR[i/2][i/2+2]=0;
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
cnt+=vD[i][j],cnt+=vR[i][j];
cout<<n<<" "<<m<<"\n"<<cnt<<"\n";
for(int i=1;i<n;i++)
for(int j=1;j<m;j++){
if(vD[i][j])cout<<i<<" "<<j<<" "<<i+1<<" "<<j<<"\n";
if(vR[i][j])cout<<i<<" "<<j<<" "<<i<<" "<<j+1<<"\n";
}
return 0;
}
```
::::
是 Ad-hoc 高质量好题喵，值得一做。
还有拆进制的做法，也挺巧的，大家都太强啦 /bx。
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！