计蒜客 28319.Interesting Integers-类似斐波那契数列-递推思维题 (Benelux Algorithm Programming Contest 2014 Final ACM-ICPC Asia Training League 暑假第一阶段第二场 I)
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给忘了,然后改了之后就过了。简直是智障,智障写了好久的智障题。。。
代码:
//I-斐波那契数列打表
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int inf=0x3f3f3f3f;
int fi[];
void fibonacci()
{
fi[]=,fi[]=;fi[]=;
for(int i=;i<=;i++)
fi[i]=fi[i-]+fi[i-];
}
int main()
{
int t,n;
fibonacci();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
{
int flag=;
for(int i=;i>=;i--)
{
int a=fi[i],b=fi[i-]+fi[i];
int cnt=n/a;
for(int y=;y<=cnt+;y++)
{
if((n-b*y)%a==&&(n-b*y)>)
{
int x=(n-b*y)/a;
if(x<=y&&x!=)
{
flag=;
printf("%d %d\n",x,y);
break;
}
}
if(flag==)break;
}
if(flag==)break;
}
}
}
return ;
}
感谢思力酱,嘲笑我的智障行为并且锤了我的脑壳,让我机灵一下发现是初始值设错了,思力酱是真的严格呢。
就先这样吧,其他题等补了再写题解。
最新文章
- 【Oracle 集群】Linux下Oracle RAC集群搭建之Oracle DataBase安装(八)
- 如何在 ASP.NET 4.6 与 IIS10 中运用 HTTP/2 ?
- Ubuntu一路填坑...
- mysql5.1升级到mysql5.6
- Win8电脑蓝屏并提示dpc_watchdog_violation
- EBS中后台AP发票审批脚本
- touches, targetTouches, changedTouches 区别
- CSS鼠标样式整理
- Python标准库02 时间与日期 (time, datetime包)
- 7.Composer的安装和使用
- 报表中的Excel操作之Aspose.Cells(Excel模板)
- WPF中控件ListView和DataGrid典型属性介绍
- 【转】Robot Framework 快速入门
- Day1作业要求
- MacBook 经常使用快捷键
- Cinder组件
- JavaSE基础知识(7)—常用类
- Rancher3----安装部署rancher
- python--递归(附利用栈和队列模拟递归)
- python 文件读写模式r,r+,w,w+,a,a+的区别(附代码示例)
热门文章
- 虚拟机中如何挂载物理磁盘(VMware操作)
- 途牛banner自动轮播
- Delphi中的关键字与保留字
- NOIP 2018 总结
- Codeforces 1093G题解(线段树维护k维空间最大曼哈顿距离)
- centos下vsftpd登录后无法看见文件,无法创建文件及文件夹
- LINQ to Entities 不识别方法“System.Guid Parse(System.String)”,因此该方法无法转换为存储表达式。
- Nginx主要模块常用指令说明
- SystemTap 用法
- P3456 [POI2007]GRZ-Ridges and Valleys