考慮斐波那契數(shù) \(fib_i\) 具有性質(zhì) \(fib_i=fib_{i-1}+fib_{i-2}\)，又考慮到相鄰塊的構(gòu)成字母不同，所以我們不難想到，對(duì)于目前剩余數(shù)最大的字母 \(x\) 來說，我們應(yīng)該用 \(x\) 來形成現(xiàn)在最大的斐波那契數(shù) \(fib_i\)，否則非常明顯的是，如果不這么干，必然 \(fib_i\) 將被拆成 \(fib_{i-1}+fib_{i-2}\)，那么 \(x\) 將形成兩個(gè)相鄰塊，所以我們每次貪心找到與上一個(gè)塊構(gòu)成字母不同的剩余數(shù)最大的字母來形成 \(fib_i\)，如果無法形成大小為 \(fib_i\) 的塊了，那么就不存在合法情況。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
priority_queue<pair<int,int> >q;
int t,k,f[65];
int check(int x){
    int id=-1;
    for(int i=2;i<=60;i++)if(f[i]-1==x){id=i-2;break;}
    return id;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    f[0]=f[1]=1;
    for(int i=2;i<=60;i++)f[i]=f[i-1]+f[i-2];
    cin>>t;
    while(t--){
        while(!q.empty())q.pop();
        cin>>k;
        int sum=0;
        for(int i=0;i<k;i++){int x;cin>>x;q.push({x,i});sum+=x;}
        int st=check(sum);
        if(st==-1){cout<<"NO\n";continue;}
        int la=k;
        bool flag=true;
        for(int i=st;i>=0;i--){
            pair<int,int> u=q.top();
            q.pop();
            if(u.first<f[i]){flag=false;cout<<"NO\n";break;}
            if(u.second==la){
                if(q.empty()){flag=false;cout<<"NO\n";break;}
                pair<int,int> v=q.top();
                q.pop();
                if(v.first<f[i]){flag=false;cout<<"NO\n";break;}
                la=v.second;
                v.first-=f[i];
                if(v.first)q.push(v);
                q.push(u);
            }
            else{
                u.first-=f[i];
                la=u.second;
                if(u.first) q.push(u);
            }
        }
        if(flag)cout<<"YES\n";
    }
    return 0;
}