最近手感有点差,所以做点水题来锻炼一下信心。
下周的南京区域赛估计就是我的退役赛了,bless all。
Revenge of Fibonacci
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 204800/204800 K (Java/Others)
Total Submission(s): 1582 Accepted Submission(s): 356
Here we regard n as the index of the Fibonacci number F(n).
This sequence has been studied since the publication of Fibonacci's book Liber Abaci. So far, many properties of this sequence have been introduced.
You had been interested in this sequence, while after reading lots of papers about it. You think there’s no need to research in it anymore because of the lack of its unrevealed properties. Yesterday, you decided to study some other sequences like Lucas sequence instead.
Fibonacci came into your dream last night. “Stupid human beings. Lots of important properties of Fibonacci sequence have not been studied by anyone, for example, from the Fibonacci number 347746739…”
You woke up and couldn’t remember the whole number except the first few digits Fibonacci told you. You decided to write a program to find this number out in order to continue your research on Fibonacci sequence.
For each test case, there is a single line containing one non-empty string made up of at most 40 digits. And there won’t be any unnecessary leading zeroes.
分析:
刚刚搜了一下,发现大家的做法都是直接存取高位前50位,这题能过。但是对于这种数据:1,9...9的话就无能为力了吧 - -
所以我们比赛时的做法是:我们用java试了一下10w时的斐波那契数,长度大概为2w多。因此我们用大数做,用C++压了10位,那么最大的数的长度大概为2000多,复杂度也就O(n*n)。然后对于前40个存到trie里面,只有当创建节点时才更新信息。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <complex>
#include <iostream>
#include <algorithm> using namespace std; typedef long long ll;
typedef unsigned long long ull; #define debug puts("here")
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)
#define pb push_back
#define RD(n) scanf("%d",&n)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define All(vec) vec.begin(),vec.end()
#define MP make_pair
#define PII pair<int,int>
#define PQ priority_queue
#define cmax(x,y) x = max(x,y)
#define cmin(x,y) x = min(x,y)
#define Clear(x) memset(x,0,sizeof(x))
#define lson rt<<1
#define rson rt<<1|1
#define SZ(x) x.size() /* #pragma comment(linker, "/STACK:1024000000,1024000000") int ssize = 256 << 20; // 256MB
char *ppp = (char*)malloc(ssize) + ssize;
__asm__("movl %0, %%esp\n" :: "r"(ppp) ); */ char IN;
bool NEG;
inline void Int(int &x){
NEG = 0;
while(!isdigit(IN=getchar()))
if(IN=='-')NEG = 1;
x = IN-'0';
while(isdigit(IN=getchar()))
x = x*10+IN-'0';
if(NEG)x = -x;
}
inline void LL(ll &x){
NEG = 0;
while(!isdigit(IN=getchar()))
if(IN=='-')NEG = 1;
x = IN-'0';
while(isdigit(IN=getchar()))
x = x*10+IN-'0';
if(NEG)x = -x;
} /******** program ********************/ const int MAXN = 2500;
const int kind = 10;
const ll INF = 1e10; char s[50]; struct node{
node *ch[kind];
int id; node(){
Clear(ch);
id = -1;
}
node(int _id):id(_id){
Clear(ch);
}
}*rt; struct Big{ // 大数,压了十位
ll a[MAXN];
int len; Big(){
Clear(a);
len = 0;
} void add(Big now){ // this > now
int in = 0;
for(int i=0;i<len;i++){
a[i] += now.a[i]+in;
if(a[i]>=INF){
in = 1;
a[i] -= INF;
}else in = 0;
}
if(in)a[len++] = in;
}
void out(){
for(int i=len-1;i>=0;i--)
cout<<a[i]<<" ";
cout<<endl;
}
}a,b,c; int p[52],len; void ins(node *root,int id){ // 插入到trie
rep(i,len){
int c = p[i];
if(root->ch[c]==NULL)
root->ch[c] = new node(id);
root = root->ch[c];
}
} void cal(){ // 把当前的大数前40位取出
len = 0;
int top = a.len-1;
ll now = a.a[top]; while(now){
p[len++] = now%10;
now /= 10;
}
reverse(p,p+len); for(int i=top-1;i>=0;i--){
now = a.a[i];
int t = len;
for(int j=0;j<10;j++){
p[len++] = now%10;
now /= 10;
}
reverse(p+t,p+len);
if(len>=40)break;
}
cmin(len,40);
} void init(){ // 预处理出前10w个, 存到trie中
Clear(a.a);
a.a[0] = a.len = 1; Clear(b.a);
b.len = 0; p[0] = len = 1;
ins(rt,0); for(int i=1;i<100000;i++){
c = a;
a.add(b); b = c;
cal();
ins(rt,i);
}
} int ask(node *root){ // 询问
scanf("%s",s);
for(int i=0;s[i];i++){
int now = s[i]-'0';
if(root->ch[now]==NULL)
return -1;
root = root->ch[now];
}
return root->id;
} int main(){ #ifndef ONLINE_JUDGE
freopen("sum.in","r",stdin);
//freopen("sum.out","w",stdout);
#endif rt = new node();
init();
int ncase,Ncase = 0;
RD(ncase);
while(ncase--)
printf("Case #%d: %d\n",++Ncase,ask(rt)); return 0;
}
hdu 4099 Revenge of Fibonacci 大数+压位+trie的更多相关文章
-
hdu 4099 Revenge of Fibonacci Trie树与模拟数位加法
Revenge of Fibonacci 题意:给定fibonacci数列的前100000项的前n位(n<=40);问你这是fibonacci数列第几项的前缀?如若不在前100000项范围内,输 ...
-
HDU 4099 Revenge of Fibonacci Trie+高精度
Revenge of Fibonacci Problem Description The well-known Fibonacci sequence is defined as following: ...
-
hdu 4099 Revenge of Fibonacci 字典树+大数
将斐波那契的前100000个,每个的前40位都插入到字典树里(其他位数删掉),然后直接查询字典树就行. 此题坑点在于 1.字典树的深度不能太大,事实上,超过40在hdu就会MLE…… 2.若大数加法时 ...
-
HDU 4099 Revenge of Fibonacci (数学+字典数)
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4099 这个题目就是一个坑或. 题意:给你不超过40的一串数字,问你这串数字是Fibonacci多少的开头 ...
-
HDU 4099 Revenge of Fibonacci(高精度+字典树)
题意:对给定前缀(长度不超过40),找到一个最小的n,使得Fibonacci(n)前缀与给定前缀相同,如果在[0,99999]内找不到解,输出-1. 思路:用高精度加法计算斐波那契数列,因为给定前缀长 ...
-
HDOJ/HDU 1250 Hat&#39;s Fibonacci(大数~斐波拉契)
Problem Description A Fibonacci sequence is calculated by adding the previous two members the sequen ...
-
TZOJ 3820 Revenge of Fibonacci(大数+trie)
描述 The well-known Fibonacci sequence is defined as following: Here we regard n as the index of the F ...
-
hdu 5018 Revenge of Fibonacci
大水题 #include<time.h> #include <cstdio> #include <iostream> #include<algorithm&g ...
-
HDU 4099 大数+Trie
Revenge of Fibonacci Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 204800/204800 K (Java/ ...
随机推荐
-
mybatis Result Maps collection already contains value for com.ebways.dictionary.dao.impl.PtInfoDaoImpl.beanMap
java.lang.IllegalStateException: Failed to load ApplicationContext at org.springframework.test.conte ...
-
最简单的视音频播放示例9:SDL2播放PCM
本文记录SDL播放音频的技术.在这里使用的版本是SDL2.实际上SDL本身并不提供视音频播放的功能,它只是封装了视音频播放的底层API.在Windows平台下,SDL封装了Direct3D这类的API ...
-
Eclipse 实现关键字自动补全功能 (转)
一般默认情况下,Eclipse ,MyEclipse 的代码提示功能是比Microsoft Visual Studio的差很多的,主要是Eclipse ,MyEclipse本身有很多选项是默认关闭的, ...
-
分享下mac安装xamarin跨平台开发环境的坑
之前在vs2015上安装好了xamarin环境,考虑到调试IOS仍然需要mac机,昨天决定直接在mac上安装xamarin. 安装完所有的效果如上图,此时已经可以创建安卓和IOS环境. 我安装过程中, ...
-
POJ1275 Cashier Employment 二分、差分约束
传送门 题意太长 为了叙述方便,将题意中的$0$点看作$1$点,$23$点看做$24$点 考虑二分答案(其实从小到大枚举也是可以的) 设$x_i$是我们选的雇员第$i$小时开始工作的人数,$s_i$是 ...
-
RHEL 6.5系统安装配置图解教程(rhel-server-6.5)
转自:http://www.jb51.NET/os/128752.html 说明: 截止目前RHEL 6.x最新版本为RHEL 6.5,下面介绍RHEL 6.5的具体安装配置过程 服务器相关设置如下: ...
-
ESLint 规则详解(二)
接上篇 ESLint 规则详解(一) 前端界大神 Nicholas C. Zakas 在 2013 年开发的 ESLint,极大地方便了大家对 Javascript 代码进行代码规范检查.这个工具包含 ...
-
python使用递归实现一个分形图形
代码如下: import turtle def main(): t = turtle.Turtle() t.hideturtle() t.speed(10) level = 12 fract(t,-8 ...
-
TensorFlow Activation Function 1
部分转自:https://blog.csdn.net/caicaiatnbu/article/details/72745156 激活函数(Activation Function)运行时激活神经网络中某 ...
-
android中反射机制
本文介绍Android反射机制实现与原理,在介绍之前,要和Java进行比较,所以先看下Java中的反射相关知识: 一.反射的概念及在Java中的类反射 反射主要是指程序可以访问.检测和修改它本身状态或 ...