Description
Input
Output
Sample Input
Sample Input1
8
1 2 3 4 5 6 7 8
2
10 -6 1
0 0 1
Sample Input2
3
0 1 2
2
-2 3 1
3 -2 2
Sample Output
Sample Output1
2 1
1 1
Sample Output2
1 0
0 1
【更多的样例】
更多的样例见下发文件。其中除了前 3 个样例外还有约定分别和测试点 1, 9, 14 相同的样例各一个。
Data Constraint
Solution
分类讨论，考虑到k为正，处理较为简单。
若当两个相邻的a同号，那么数列后面的数一定会快速增大或减小。
否则就会一正一负地交替，且慢慢接近0。
图像如下：
最大值或最小值一定在交替的前面，或单调地最后面。
由于单调区间增速很大，我们只需要在它大于开头或小于开头的值算出来比较大小即可。
Code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 300003
using namespace std;
ll n,T,s[N],f[N],k,mn,mx,bz1,bz2,dw,up;
char c;
void R(ll &x){
x=0;I w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=w;
}
I main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
R(n);
F(i,1,n) R(s[i]);
R(T);
while(T--){
bz1=bz2=dw=up=0;mx=mn=-1;
R(f[0]),R(f[1]),R(k);
if(!f[0]&&!f[1]){printf("%d %d\n",s[1],s[1]);continue;}
if(f[0]>=0&&f[1]>=0){
printf("%d ",s[n]);
if(s[1]==0&&s[2]==1){
if(f[0]<=f[1]) printf("0\n");
else printf("1\n");
}
else printf("%d\n",s[1]);
continue;
}
if(f[0]<=0&&f[1]<=0){
if(s[1]==0&&s[2]==1){
if(f[0]>=f[1]) printf("0 ");
else printf("1 ");
}
else printf("%d ",s[1]);
printf("%d\n",s[n]);
continue;
}
I j=0;
F(i,0,1){
if(s[j+1]==i){
j++;
if(mx==-1||f[s[j]]>f[mx]) mx=s[j];
if(mn==-1||f[s[j]]<f[mn]) mn=s[j];
}
}
F(i,2,s[n]){
f[i]=f[i-1]*k+f[i-2];
if(s[j+1]==i){
j++;
if(mx==-1||f[s[j]]>f[mx]) mx=s[j];
if(mn==-1||f[s[j]]<f[mn]) mn=s[j];
}
if(f[i]>0&&f[i-1]>0) bz1=1;
if(f[i]<0&&f[i-1]<0) bz2=1;
if(bz1&&f[i]>f[0]&&f[i]>f[1]){up=1;break;}
if(bz2&&f[i]<f[0]&&f[i]<f[1]){dw=1;break;}
}
if(up) mx=s[n];
if(dw) mn=s[n];
if(mx<0) mx=s[1];if(mn<0) mn=s[1];
printf("%d %d\n",mx,mn);
}
return 0;
}
