【AGC009C】Division into Two

【AGC009C】Division into Two

题面

洛谷

题解

首先有一个比较显然的(n^2)算法：

设(f_{i,j})表示(A)序列当前在第(i)个，(B)序列当前在第(j)个的方案数，发现(i,j)大小没有限制不是很好转移，于是再设一个(g_{i,j})表示(B)序列当前在第(i)个，(A)序列当前在第(j)个的方案数的，这样子我们就可以钦定(i>j)了，转移会方便许多。

转移如下：

[left{ egin{aligned} f_{i+1,j}leftarrow f_{i,j}(a_{i+1}-a_igeq A)\ g_{i+1,i}leftarrow f_{i,j}(a_{i+1}-a_jgeq B)\ g_{i+1,j}leftarrow g_{i,j}(a_{i+1}-a_igeq B)\ f_{i+1,i}leftarrow g_{i,j}(a_{i+1}-a_jgeq A) end{aligned} ight. ]

---

然后让我们想一想怎么优化这个东西。

不妨设(A<B)，则对于(forall igeq 3,a_i-a_{i-2}geq A)，对于不符合的我们直接判掉。

设(f_i)表示当前(B)序列在(i)的方案数，我们对于可以转移过来的(j)，必须要满足(a_i-a_jgeq B)，而对于(forall kin [j+1,i-1])，则要满足(a_k-a_{k-1}geq A)，考虑到这样的(j)是一个区间，而区间左右端点单调，我们把这个区间搞出来然后前缀和优化即可。

复杂度(O(n))。

代码

\O(n^2)
int main () { 
	scanf("%d %lld %lld", &N, &A, &B); 
	if (A > B) swap(A, B); 
	for (int i = 1; i <= N; i++) scanf("%lld", a + i); 
	for (int i = 3; i <= N; i++) if (a[i] - a[i - 2] < A) return puts("0") & 0; 
	a[0] = -1e18; 
	int ans = 0; 
	f[1][0] = 1, g[1][0] = 1; 
	for (int i = 1; i <= N; i++) 
		for (int j = 0; j < i; j++) { 
			if (a[i + 1] - a[i] >= A) f[i + 1][j] = (f[i + 1][j] + f[i][j]) % Mod; 
			if (a[i + 1] - a[j] >= B) g[i + 1][i] = (g[i + 1][i] + f[i][j]) % Mod; 
			if (a[i + 1] - a[i] >= B) g[i + 1][j] = (g[i + 1][j] + g[i][j]) % Mod; 
			if (a[i + 1] - a[j] >= A) f[i + 1][i] = (f[i + 1][i] + g[i][j]) % Mod; 
		} 
	for (int i = 0; i < N; i++) ans = (ans + (f[N][i] + g[N][i]) % Mod) % Mod; 
	printf("%d
", ans); 
    return 0; 
} 

\O(n)
int main () { 
	scanf("%d %lld %lld", &N, &A, &B); 
	for (int i = 1; i <= N; i++) scanf("%lld", a + i);
	if (A > B) swap(A, B); 
	for (int i = 3; i <= N; i++) if (a[i] - a[i - 2] < A) return puts("0") & 0;
	f[0] = s[0] = 1;
	int l = 0, r = 0; 
	for (int i = 1; i <= N; i++) { 
		while (r < i - 1 && a[i] - a[r + 1] >= B) ++r; 
		if (l <= r) f[i] = (s[r] - (l ? s[l - 1] : 0) + Mod) % Mod; 
		s[i] = (s[i - 1] + f[i]) % Mod; 
		if (i != 1 && a[i] - a[i - 1] < A) l = i - 1; 
	} 
	int ans = 0; 
	for (int i = N; ~i; i--) { 
		ans = (ans + f[i]) % Mod; 
		if (i != N && a[i + 1] - a[i] < A) break; 
	} 
	printf("%d
", ans); 
    return 0; 
}