LOJ 538. 「LibreOJ NOIP Round #1」数列递推（找规律+结论）

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

题目大意

• 给出递推式$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
", 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
", mx, mi);
	}
	return 0;
}