LOJ538 - 「LibreOJ NOIP Round #1」数列递推

2017/11/05

题面

全是公式不想打

做法

打表猜结论。

一个明显的东西是如果数列前两项同号的话数列单调。

如果前两项异号,可以发现它在波动,但我们可以断言这个数列在一定项后单调。

官方题解里的证明

胡写居然 A 了,欧气很足(flag)。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace istream {
    const int L = 1<<16;
    char buf[L], *S, *T;
    char c; bool uneof = true;

    inline char readch() {
        if(S==T) {
            T=(S=buf) + fread(buf, 1, L, stdin);
            if(S==T) { uneof = false; return EOF; }
        }
        return *S++;
    }

    void readint(register int &x) {
        x = 0; bool flag = 0;
        while((c < '0' || c > '9') && uneof) {
            flag = flag || (c == '-');
            c = readch();
        }
        if(!uneof) return;
        while(c >= '0' && c <= '9') {
            x = (x<<1) + (x<<3) + (c - '0'); c = readch();
        }
        x = flag ? -x : x;
    }
};
#define rint(x) (istream::readint(x))

typedef long long LL;
const int SIZ = 1e5 + 2007;
int N, M;
LL F[SIZ];
int S[SIZ];

LL sgn(LL x) {
    if(x > 0) return 1;
    else if(x < 0) return -1;
    else return 0;
}

LL calc(int a0, int a1, int k, int b, int sg) {
    if(b > 1100) return sg * 1e18;
   
    LL t, x=a0, y=a1;
    for(int i=2;i<=b;i++) {
        t = y;
        y = k * y + x;
        x = t;

        if(abs(y) > 1e12) return y;
    }

    return y;
}

void solve(int a0, int a1, int k) {
    F[0] = a0;
    F[1] = a1;

    int q;
    for(q=2;q<100;q++) {
        F[q] = k * F[q-1] + F[q-2];
        if(abs(F[q]) > 1e12) break;
    }

    /*
    for(int i=0;i<=q;i++)
        printf("%lld ", F[i]);
    puts("");
    */

    LL dif1 = F[q] - F[q-1];
    LL dif2 = F[q-1] - F[q-2];
    LL dif3 = F[q-2] - F[q-3];

    int mxai = S[1], mnai = S[1];
//    if(sgn(dif1) * sgn(dif2) > 0 && sgn(dif2) * sgn(dif3) > 0) {
        int i;
        for(i=2;i<=M;i++) {
            if(S[i] >= q) break;
            if(F[S[i]] > F[mxai])
                mxai = S[i];
            if(F[S[i]] < F[mnai])
                mnai = S[i];
        }

        if(sgn(dif1) > 0 && sgn(dif2 > 0)) {
            if(calc(a0, a1, k, S[M], 1) > F[mxai]) {
                mxai = S[M];
            }
        } else if(sgn(dif1) < 0 && sgn(dif2 < 0)) {
            if(calc(a0, a1, k, S[M],-1) < F[mnai])
                mnai = S[M];
        }
        printf("%d %d\n", mxai, mnai);
//    }
}

int main() {
    rint(M);

    for(int i=1;i<=M;i++)
        rint(S[i]);

    rint(N);
    int a0, a1, k;
    while(N--) {
        rint(a0); rint(a1); rint(k);
        solve(a0, a1, k);
    }
}