牛客小白月赛 G 异或找规律

系统管理员 2021-03-28 14:19 644阅读 0赞

## 题目描述 ##

从前，Apojacsleam家的水族箱里，养了一群热带鱼。

在这几条热带鱼里，Apojacsleam特别喜欢一条叫做TbGx（请勿人肉）的热带鱼，所以每次都让她第一个吃食物。对于每一条鱼，Apojacsleam都有一个顺序，鱼会按照这个顺序排序，越靠前的地位越高。

吃饱喝足是要睡觉的，这是人的刚需，也是鱼的刚需。

如果TbGx吃了Apojacsleam的食物，她就会睡觉**（睡觉时长远小于一天）**。这时第二条鱼还是饥肠辘辘的，第二条鱼就可以吃掉TbGx，那么第二条鱼又会睡觉......

注意：Apojacsleam养的鱼比Apojacsleam的智商**高到不知道哪里去了，他们都是绝顶聪明的**；而他们又是极其守规矩的，即他们不会多鱼分食一条鱼或者食物，只是按照顺序吃；当某一条鱼前面的鱼睡着以后，他可以选择不吃这条鱼，那么别的鱼（还活着的）也不会吃这条，即按照顺序的吃。

一开始，水族箱里只有TbGx一条鱼（未成年），但是，一条鱼成长两天就会成年，成年后就可以繁殖（无性繁殖？别问我我不知道），一天能繁殖一个后代。小鱼也会吃鱼的偶!

请问在前n天中，TbGx最多多少天可以吃饭？

Apojacsleam不希望TbGx饿着，所以你必须在1s内回答。

## 输入描述: ##

输入数据有多组，每组一个正整数n，意义如“题目描述”

## 输出描述: ##

对于每组输入数据，一行输出：

即前n天中，最多有多少天TbGx可以吃饭。

示例1

## 输入 ##

复制

## 输出 ##

复制

## 说明 ##

第1天，1条鱼，能吃；

第2天，1条鱼，能吃；

第3天，2条鱼，不能吃；

第4天，3条鱼，能吃；

第5天，5条鱼，能吃；

第6天，8条鱼，不能吃；。

![305297_1528508526666_9A337960A1A1922C71A9379BDE79C548][]

从题目的补充说明中不难看出鱼的繁殖符合斐波拉契数列，同时那天有奇数条鱼时鱼那天鱼是可以吃到东西的

然后按照题意打个表找规律就行

最后得吐槽下牛客的评测，同一份代码，第一次交TLE了，第二次就过了。。

#include <map>
    #include <set>
    #include <stack>
    #include <cmath>
    #include <queue>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #define debug(a) cout << #a << " " << a << endl
    using namespace std;
    const int maxn = 107;
    const int mod = 1e9 + 7;
    typedef long long ll;
    int main() {
        /*ll f[20];  //注释掉的是打表的方法
        f[1] = 1, f[2] = 1;
        for( ll i = 3; i <= 15; i ++ ) {
            f[i] = f[i-1] + f[i-2];
        }
        for( ll i = 1; i <= 15; i ++ ) {
            ll cnt = 0;
            for( ll j = 1; j <= i; j ++ ) {
                //debug(j), debug(f[j]);
                if( f[j]&1 ) {
                    cnt ++;
                }
            }
            debug(i), debug(cnt);
        }*/
        ll n;
        while( scanf("%lld",&n) != EOF ) {
            ll t = ( n + 2 ) / 3;
            if( n % 3 == 1 || n % 3 == 0 ) {
                printf("%lld\n",t+(n/3));
            } else {
                printf("%lld\n",t+1+(n/3));
            }
        }
        return 0;
    }

[305297_1528508526666_9A337960A1A1922C71A9379BDE79C548]: /images/20210328/1616941175234.png