大佬们,这段代码出现了什么问题,测试用例2输出的是YES
查看原帖
大佬们,这段代码出现了什么问题,测试用例2输出的是YES
1160029
ohhhhhdod楼主2024/6/27 17:21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t , n , x , y;
bool check(ll x , vector<bool> & vis , vector<ll> def){
    for(int i = n; i >= 0; i--){
        if(vis[i]) continue;
        if(def[i] <= x){
            vis[i] = true;
            x -= def[i];
        }
    }
    return x == 0;
}
int main(){
    cin >> t;
    vector<ll> def(46);//预处理Fibonacci数列
    def[0] = 1 , def[1] = 1;
    for(int i = 2; i <= 45; i++) def[i] = def[i - 1] + def[i - 2];
    while(t--){
        cin >> n >> x >> y;
        vector<bool> vis(n + 1 , 0);//记录是否存在这样的Fibonacci数列项
        vis[0] = true;
        bool flag = 1;
        flag &= check(x - 1 , vis , def);
        flag &= check(y - 1 , vis , def);
        vector<bool> vis1(n + 1 , 0) , vis2(n + 1 , 0);
        for(int i = 0; i <= n; i++) vis1[i] = vis2[i] = vis[i];
        bool flag1 = 1 , flag2 = 1;
        flag1 &= check(def[n] - x , vis1 , def);
        flag1 &= check(def[n + 1] - y , vis1 , def);
        flag2 &= check(def[n + 1] - x , vis2 , def);
        flag2 &= check(def[n] - y , vis2 , def);
        for(int i = 0; i <= n; i++) flag1 &= vis1[i];
        for(int i = 0; i <= n; i++) flag2 &= vis2[i];
        if((flag1 || flag2) && flag) cout << "YES";
        else cout << "NO";
        cout << '\n';
    }
}
2024/6/27 17:21
加载中...