「LOJ 538」「LibreOJ NOIP Round #1」数列递推
阅读原文时间:2021年09月07日阅读:1

description

  • sosusosu 虐爆 OI 之后成为了一名文化课选手。一天,他做作业碰到了一堆数列问题,每道题给出的数列都是以下形式:

给定一个下标从\(0\)开始,无限长的整数列\({a_{i}}\),\(i \in N\) ,已知\(a_{0},a_{1}\) 的值,以及递推式\(a_{i+2}=ka_{i+1}+a_{i}\),\(i \in N\) ,\(k \in N^+\)。

  • sosusosu 研究了这些数列,发现它们十分优美充满人类智慧,于是决定出一道 OI 题。
  • sosusosu 给了你一个集合 \(S\subset N\),他想问你对于\(S\)中的每个数\(s_i\),使得\(a_{s_{i}}\)最大的\(s_{i}\)使得\(a_{s_{i}}\)最小的\(s_{i}\)分别是多少。如果这样的\(s_{i}\)有多个,请你回答最小的一个。
  • 另外,sosusosu 准备对他作业中碰到的每个数列都让你回答一次,不过每次的集合\(S\)是一样的。
  • 数列数量\(n\le3*10^5\),\(S\)中的元素个数\(m\le 10^5\)

solution

  • 手玩几组样例,可以得到一个结论:序列在经过某一个临界点之后会变成单调递增或单调递减,且最多只有前\(log_2{k}\)个数是不单调的,请读者自证我太菜了不会证明
  • 故暴力判断前\(log_2{k}\)个数,然后根据序列的单调性判断\(S\)中最大的一个数是最大值还是最小值即可
  • 注意如果前\(log_2{k}\)个数中没有任何一个在\(S\)中,那么答案就会是\(S_1\),需要特判

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=3e5+10;
const int M=1e5+10;
int m,n,s[M],w[M];
ll a[N];
int main(){
//    freopen("ex_seq4.in","r",stdin);
    m=read();
    for(int i=1;i<=m;++i){
        s[i]=read();
    }
    n=read();
    while(n--){
        a[0]=read();a[1]=read();
        int k=read();
        int fi=min(100,s[m]);
        ll mx=-1e16,mn=1e16;
        int mxp=-1,mnp=-1;
        for(int i=2;i<=fi;++i){
            a[i]=1ll*k*a[i-1]+a[i-2];
            if(a[i]>1e15&&a[i-1]>=0&&a[i-2]>=0&&a[i]>=0){fi=i;break;}
            if(a[i]<-1e15&&a[i-1]<=0&&a[i-2]<=0&&a[i]<=0){fi=i;break;}
        }
        for(int i=1;i<=m;++i){
            if(s[i]<fi){
                if(a[s[i]]>mx) mx=a[s[i]],mxp=s[i];
                if(a[s[i]]<mn) mn=a[s[i]],mnp=s[i];
            }
            else break;
        }
        if(a[fi]>mx&&a[fi]>0)mxp=s[m];
        if(a[fi]<mn&&a[fi]<0)mnp=s[m];
        if(mxp==-1)mxp=s[1];
        if(mnp==-1)mnp=s[1];
        printf("%d %d\n",mxp,mnp);
    }
    return 0;

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章