题解：P12036 [USTCPC 2025] 摩拉

kimino_tree · 2025-04-05 21:09:53 · 题解

思路

这道题主要用到的是斐波那契数列。
第一天赚 p 个摩拉，第二天赚 p+1 个摩拉，接下来每天所赚的摩拉是前两天赚的摩拉之和，那么第三天就赚到 2p+1 个摩拉，第四天可以赚到 3p+2 个摩拉。以此类推，就可以找到规律。

找规律

可以用列表法寻找规律。

若把每一天的钱数看为 kp+b ，则 b 是斐波那契数列中 k 前的一个数。再看数据范围，a,b≤20 ,可以枚举斐波那契数列的前 20 个数，然后再解一元一次方程解出 p ，最后把 b 代入天数算出 ans 。

AC Code

代码中 kkk[i][1] 用于记录第 i 天的 k 值，kkk[i][1] 用于记录第 i 天的 b 值。

#include<bits/stdc++.h>
#define kkkzuikeai return 0;//kkk最可爱!
using namespace std;
long long t,a,x,b,k[1314520],kkk[1314][1314],p;
int main(){
    cin>>t;
    memset(k,0,sizeof(k));
    k[1]=1,k[2]=2;
    for(int i=3;i<=100;i++){
        k[i]=k[i-1]+k[i-2];//斐波那契数列
    }
    kkk[1][1]=1,kkk[1][2]=0,kkk[2][1]=1,kkk[2][2]=1;//用于记录 p=0和p=1时的结果
    for(int i=3;i<=50;i++){
        kkk[i][1]=k[i-1],kkk[i][2]=k[i-2];//转换
    }
    while(t--){
        cin>>a>>x>>b;
        if((x-kkk[a][2])%kkk[a][1]==0)p=(x-kkk[a][2])/kkk[a][1];//解一元一次方程
        else{
            cout<<"-1\n";//解出来为小数输出-1
            continue;
        }
        cout<<p*kkk[b][1]+kkk[b][2]<<'\n';//将p代入天数算出答案
    } 
    kkkzuikeai
}