埃森哲杯第十六届上海大学程序设计联赛春季赛暨上海高校金马五校赛 F题 1+2=3 ？

题目链接https://www.nowcoder.com/acm/contest/91/F

思路：打表找规律。可以发现n其实是斐波拉契数列构成的

官方题解是数位dp和找规律

AC代码

 1 #include<iostream>
 2 #include<bits/stdc++.h>
 3 #define ll  long long
 4 using namespace std;
 5 ll  a[100];
 6 ll ans;
 7 int  main(){
 8     a[0]=1;
 9     a[1]=2;
10     for(int i=2;i<64;i++){
11         a[i]=a[i-1]+a[i-2];
12     }
13     ll  T;
14     cin>>T;
15     while(T--){
16         ll  n;
17         cin>>n;
18         ans=0;
19         while(n>0){
20             for(int i=0;i<63;i++){
21                 if(n>=a[i]&&n<a[i+1]){
22                     ll t=1;
23                     ans+=(t<<i);
24                     n=n-a[i];
25                 }
26             }
27         }
28         cout<<ans<<endl;
29     }
30     return 0;
31 }