规律神器OEIS
标签: 机试攻略 - 高分篇
学习人数: 70.7k


高清播放
赞赏支持

下面给大家隆重介绍一个神器,所有的考生,看这里:OEIS

对,就是它,考试必备神器,你值得拥有。有了它,你可以变得更自信,你可以满怀信心的走进考场,你可以飞快解出那些所谓推公式的规律难题。

它的网址:http://oeis.org/

它究竟有多变态,只要你输入前几项,它就可以给你找出规律来,并且自动给你推出公式。所以对于找规律的题目,你只需要手动计算出前几项的值,或者暴力打表求出前几项的值,然后输入OEIS,他就可以告诉你公式是什么。
怎么样,超级有用吧!妈妈再也不用担心我的数学了^_^

 

What!你说它考试的时候没用?难道如何优雅的上厕所也需要教?

 

所有的考生,一定要学会,用它!用它!一定要用它!

 

只用花一分钟你就学会用这个东西了,如果你不会用,而你的竞争对手会用,那你就惨了,说不定你推到死都推不出来的公式,别人几秒钟就搞定了。反之,你学会了用这个东西,而你的竞争对手不会,到时候你会感觉爽翻天(*^▽^*)

 

快来用这个神器做一下下面这个题练练手吧
 

01字符串
题目描述:
给你一串长度为n的全为0的字符串,你可以进行一个压缩操作,将两个相邻的0压缩成一个1。请问最多会有多少种组合出现?
例如n为3则有下面3种组合:
000
10
01
输入描述:
输入一个正整数n(1<=n<=10000)。
输出描述:
输出最多有多少种组合出现,由于结果可能过大,请将答案对2333333取模。
输入样例#:
3
输出样例#:
3
题目来源:
DreamJudge 1479

题目解析:对于这类让我们去找有多少种情况的题目,第一反应就是他是有规律的,它的规律可能简单,也可能很难。这时候我们先推出它的前几项值,n为1时答案等于1,n为2时答案等于2,n为3时答案等于3,n为4时答案等于5。然后我们将这前几项值1,2,3,5输入到OEIS中,它立马告诉我们这个规律是斐波那契数列,f[i]=f[i-1]+f[i-2]。

 

参考代码

#include <stdio.h>  
  
long long f[10005] = {0};  
int main(){  
    int n;  
    scanf("%d", &n);  
    f[0] = 1; f[1] = 1;  
    for (int i = 2; i <= n; i++) {  
        f[i] = f[i-1] + f[i-2];  
        f[i] %= 2333333;  
    }  
    printf("%lld\n", f[n]);  
    return 0;  
}  

 

上面这个题目规律很简单,可能你不借助OEIS都能推出来,但是很多时候规律的公式很复杂,涉及到组合数之类的,手推是非常难推出来的。既然能几秒钟解决的问题,为什么要花大量时间去手推公式呢?多留点时间做其他题不好吗?

登录查看完整内容


课后作业

学会使用规律神器OEIS


登录后开始许愿

暂无评论,来抢沙发