题解：CF2111B Fibonacci Cubes

· · 题解

首先，对于一个正方体，它的上下左右有一边若可以继续装，一定能同时包容并排的两个比它小的最大的正方体，因为对于斐波那契数列，f_i=f_{i-1}+f_{i-2}，换句话说，若第 i 个和第 i-1 个正方体能装下，那么第 i-2 个也能装下，于是根据结论逐个从大到小放，可以观察到只需要判断最大的两个正方体可不可以同时放，以及第 n 个正方体能否完全放进去即可，只要满足以上条件，就全部可以放。

代码

#include<bits/stdc++.h>
#define ll long long
#define R register
#define il inline
using namespace std;
#define rep(x,l,r) for(R int x=l;x<=r;++x)
#define per(x,l,r) for(R int x=l;x>=r;--x)
#define inf INT_MAX
#define linf LLONG_MAX
#define N 20
il ll read() {
    ll k=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') {k=(k<<1)+(k<<3)+(c^48);c=getchar();}return f*k;
}int n,m,dp[N];
int main() {
    int T=read();
    while(T--){
        n=read();m=read();
        dp[1]=1;dp[2]=2;
        rep(i,3,n+1) dp[i]=dp[i-1]+dp[i-2]; 
        rep(i,1,m){
            int w=read(),l=read(),h=read();
            if((dp[n+1]<=l||dp[n+1]<=w||dp[n+1]<=h)&&(dp[n]<=w&&dp[n]<=l&&dp[n]<=h))printf("1");
            else printf("0");
        }printf("\n");
    }

    return 0;
}