JZOJ 6818. 【2020.10.07提高组模拟】数列递推

题目大意

给出递推式$q_i=q_{i-1}\ast K+q_{i-2}$，其中$N$次询问，每次$q_0,q_1,K$给出，求以给定集合$S$中的元素作为下表的$q_{s_i}$的最大和最小值对应的$s_i$，如有多个则最小化$s_i$。$N\le 3\ast 10^5，|S|\le 10^5$$|q_0|,|q_1|\le 10^7，1\le K\le 5000$

题解

有一个结论，当这个数列递推若干项后会出现全是同正/负的情况，那么接下来一直往后就只会递增/减，而且可以通过证明得出所谓“若干项”只有$log$级别，那么前面的直接暴力递推，当出现同号时则直接再更新一次最大/小值，实现起来有些细节可能考虑不到，对着数据改一下就可以过了。细节：1、最后即便同正/负，到最后一项的值也未必大/小于前面的最大/小值，所以前面暴力递推的退出条件改为当前同正/负且当前值大/小于前面所有数的最大/小值；2、有可能一开始就是同号，所以不能只更新符号方向的极值，另一个极值也可能需要修改；3、可能出现$q_0=q_1=0$，需要特判一下。以上是我个人遇到的问题和解决办法，因为写法不同可能有所差异。

代码

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 ll q[N]; int a[N]; int main() { int n, m, i, j; ll k; scanf("%d", &m); for(i = 1; i <= m; i++) scanf("%d", &a[i]); scanf("%d", &n); for(i = 1; i <= n; i++) { scanf("%lld%lld%lld", &q[0], &q[1], &k); if(q[0] == q[1] && q[0] == 0) { printf("%d %d\n", a[1], a[1]); continue; } int mx = -1, mi = -1, l = 1; ll Mx = max(q[0], q[1]), Mi = min(q[0], q[1]); for(j = 2; j; j++) { q[j] = q[j - 1] * k + q[j - 2]; if(q[j] > 0 && q[j - 1] > 0 && q[j] > Mx) break; if(q[j] < 0 && q[j - 1] < 0 && q[j] < Mi) break; Mx = max(Mx, q[j]), Mi = min(Mi, q[j]); } int t = j; for(j = 1; j <= m && a[j] <= t; j++) { if(mx == -1 || q[a[j]] > q[mx]) mx = a[j]; if(mi == -1 || q[a[j]] < q[mi]) mi = a[j]; } if(a[m] > t) { if(q[t] < 0) { if(mx == -1) mx = a[1]; mi = a[m]; } else { if(mi == -1) mi = a[1]; mx = a[m]; } } printf("%d %d\n", mx, mi); } return 0; }