【LibreOJ】#538. 「LibreOJ NOIP Round #1」数列递推

时间：2023-02-09 03:50:46

【题意】LibreOJ

【算法】乱搞

【题解】容易发现数列最后一定单调，最后单调递增则最大值赋为最后一个，反之最小值赋为最后一个，然后处理一些细节就可以AC，要注意以下几点：

1.数列连续三项以及数列最后一项>10^7时退出。

2.可能第一要求项就比你枚举的大，需要特判。

3.要求项的枚举不能等于最大项，不然会无法正常指向最后一个。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

#include<algorithm>

#define ll long long

#define lowbit(x) x&-x

using namespace std;

int read(){

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

int min(int a,int b){return a<b?a:b;}

int max(int a,int b){return a<b?b:a;}

int ab(int x){return x>?x:-x;}

//int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

//int MO(int x){return x>=MOD?x-MOD:x;}

//void insert(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

/*------------------------------------------------------------*/

const int inf=0x3f3f3f3f,maxn=;

const ll MAXS=1e15;

int n,m,k,s[maxn];

ll a[maxn];

int main(){

//    freopen("seq8.in","r",stdin);

//    freopen("hi.out","w",stdout);

    int mx=;

    m=read();

    for(int i=;i<=m;i++)s[i]=read(),mx=max(s[i],mx);

    n=read();

    int N=min(,mx);

    for(int i=;i<=n;i++){

        int now=N;

        a[]=read();a[]=read();k=read();

        for(int j=;j<=N;j++){

            a[j]=1ll*k*a[j-]+a[j-];

            if((a[j]>=&&a[j-]>=&&a[j-]>=&&a[j]>MAXS)||(a[j]<=&&a[j-]<=&&a[j-]<=&&a[j]<-MAXS)){now=j;break;}

        }

        ll mins=1ll<<,maxs=-(1ll<<);

        int maxi=-,mini=-;

        for(int j=;j<=m;j++)if(s[j]<now){

            if(a[s[j]]>maxs)maxs=a[s[j]],maxi=s[j];

            if(a[s[j]]<mins)mins=a[s[j]],mini=s[j];

        }else break;

        if(maxi==-)maxi=s[];

        if(mini==-)mini=s[];

        if(a[now]>&&a[now]>maxs)maxi=mx;

        if(a[now]<&&a[now]<mins)mini=mx;

        printf("%d %d\n",maxi,mini);

    }

    return ;

}

相关文章