CF1811D题解

ncwzdlsd · 2023-10-24 23:01:50 · 题解

一个结论：

对于题目要求的 F_n\times F_{n+1} 的矩形，考虑将其不断拆分掉一个正方形，剩余矩形可以按照之前的方式继续操作。观察到此时的划分方案即为题目要求的。

如果某时刻（设定长大于宽）的 y\in(F_{siz-1},F_{siz}]，那么无论如何它一定会被一个完整的正方形切割掉，此时不存在方案。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long

int F[45],n,x,y;

void init()
{
    F[0]=1,F[1]=1;
    for(int i=2;i<=44;i++) F[i]=F[i-1]+F[i-2];
}

bool cut(int siz,int x,int y)
{
    if(siz==1) return 1;
    if(y<=F[siz-1]) return cut(siz-1,y,x);//(x,y)在左
    else if(y>F[siz]) return cut(siz-1,y-F[siz],x);//(x,y)在右
    return 0;
}

void solve()
{
    cin>>n>>x>>y;
    if(cut(n,x,y)) cout<<"YES\n";
    else cout<<"NO\n";
}

signed main()
{
    int t;cin>>t;
    init();
    while(t--) solve();
    return 0;
}