您的位置: 首页  >  IT文章  >  计蒜客 28319.Interesting Integers-类似斐波那契数列-递推思维题 (Benelux Algorithm Programming Contest 2014 Final ACM-ICPC Asia Training League 暑假第一阶段第二场 I)

计蒜客 28319.Interesting Integers-类似斐波那契数列-递推思维题 (Benelux Algorithm Programming Contest 2014 Final ACM-ICPC Asia Training League 暑假第一阶段第二场 I)

分类: IT文章 • 2023-03-18 00:27:35

I. Interesting Integers

传送门

应该是叫思维题吧，反正敲一下脑壳才知道自己哪里写错了。要敢于暴力。

这个题的题意就是给你一个数，让你逆推出递推的最开始的两个数(假设一开始的两个数为x和y)，而且要求x<=y。

通过找规律可以发现,这个题就是求解a*x+b*y=k这个方程的x和y的值，并且要x和y为最小满足条件的解。可以找规律出一个公式fi[i]*x+(fi[i-1]+fi[i])*y=n。因为不知道n具体是在第几步推出来的，所以for循环跑一遍预处理出来的斐波那契数列(存到fi数组中)，最多不超过50个数，否则会爆1e9。

因为是求解a*x+b*y=k这个方程的x和y的值，并且要x和y为最小满足条件的解，当时脑子一热就说，这不是扩展欧几里得吗，然后突然发现，斐波那契数列相邻两个数是互质的，他们的exgcd为1，并没有什么用，打扰了，所以还是老老实实去写暴力。

通过该方程，可以大体确定y的范围，y=1;y<=cnt+1，因为要求在满足a<=b的条件下的最小值，所以斐波那契数列中的数作为两个数的系数，只有系数尽可能大，这两个数才会尽可能小，所以斐波那契数列的遍历从大到小遍历，因为要求y尽量小的前提下x小且x<=y，所以从小到大遍历y，找到第一个满足条件:x<=y的就是结果。如果都是从大到小或者从小到大遍历或者怎么遍历，会超时，所以找到结果直接输出就可以了。

自己写的时候，2和4的结果输不出来，然后特判2和4水过去了，仔细想了一下，发现是斐波那契数列初始值设错了，把0给忘了，然后改了之后就过了。简直是智障，智障写了好久的智障题。。。

代码:

 1 //I-斐波那契数列打表
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<map>
 9 #include<algorithm>
10 using namespace std;
11 typedef long long ll;
12 const int maxn=1e5+10;
13 const int inf=0x3f3f3f3f;
14 int fi[50];
15 void fibonacci()
16 {
17     fi[0]=0,fi[1]=1;fi[2]=1;
18     for(int i=3;i<=45;i++)
19         fi[i]=fi[i-1]+fi[i-2];
20 }
21 int main()
22 {
23     int t,n;
24     fibonacci();
25     scanf("%d",&t);
26     while(t--)
27     {
28         scanf("%d",&n);
29         {
30             int flag=0;
31             for(int i=45;i>=0;i--)
32             {
33                 int a=fi[i],b=fi[i-1]+fi[i];
34                 int cnt=n/a;
35                 for(int y=1;y<=cnt+1;y++)
36                 {
37                     if((n-b*y)%a==0&&(n-b*y)>0)
38                     {
39                         int x=(n-b*y)/a;
40                         if(x<=y&&x!=0)
41                         {
42                             flag=1;
43                             printf("%d %d
",x,y);
44                             break;
45                         }
46                     }
47                     if(flag==1)break;
48                 }
49                 if(flag==1)break;
50             }
51         }
52     }
53     return 0;
54 }

感谢思力酱，嘲笑我的智障行为并且锤了我的脑壳，让我机灵一下发现是初始值设错了，思力酱是真的严格呢。

就先这样吧，其他题等补了再写题解。

相关推荐