专栏文章

题解：CF1718B Fibonacci Strings

ccogimyun
CF1718B题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mingcm79
此快照首次捕获于
2025/12/02 01:57
3 个月前
此快照最后确认于
2025/12/02 01:57
3 个月前
查看原文
考虑斐波那契数 fibifib_i 具有性质 fibi=fibi−1+fibi−2fib_i=fib_{i-1}+fib_{i-2}，又考虑到相邻块的构成字母不同，所以我们不难想到，对于目前剩余数最大的字母 xx 来说，我们应该用 xx 来形成现在最大的斐波那契数 fibifib_i，否则非常明显的是，如果不这么干，必然 fibifib_i 将被拆成 fibi−1+fibi−2fib_{i-1}+fib_{i-2}，那么 xx 将形成两个相邻块，所以我们每次贪心找到与上一个块构成字母不同的剩余数最大的字母来形成 fibifib_i，如果无法形成大小为 fibifib_i 的块了，那么就不存在合法情况。

CODE

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...