CSP-S 模拟赛34

T1

考虑对原序列将 \(k\) 的左右分成两个序列。simple 的想法是分别从 \(1\) 开始跑前缀和，每一次总跑到下一个小于它的点，然后依次类推。发现这样做碰到序列最小值之后难以继续。

然而我们发现这样跑点的过程从前往后和从后往前是等价的。这样考虑的原因是发现这样的选数问题不具有方向性。于是时间复杂度 \(O(n)\)。

代码：

#include <bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int T;
int n, k;
int a[N];
int a1[N], a2[N];
int ct1, ct2;
int sm1[N], sm2[N];
int nx1[N], nx2[N];
void sve() {
	memset(sm1, 0, sizeof sm1);
	memset(sm2, 0, sizeof sm2);
	memset(nx1, 0, sizeof nx1);
	memset(nx2, 0, sizeof nx2);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	ct1 = ct2 = 1;
	a1[1] = a2[1] = 0;
	for (int i = k; i > 1; i--)
		a1[++ct1] = a[i];
	for (int i = k + 1; i <= n; i++)
		a2[++ct2] = a[i];
	for (int i = 1; i <= ct1; i++)
		sm1[i] = sm1[i - 1] + a1[i];
	for (int i = 1; i <= ct2; i++)
		sm2[i] = sm2[i - 1] + a2[i];
	int mn = sm1[1], nw = 1;
	for (int i = 2; i <= ct1; i++)
		if (sm1[i] <= mn) {
			nx1[nw] = i;
			nw = i;
			mn = sm1[i];
		}
	mn = sm1[ct1], nw = ct1;
	for (int i = ct1 - 1; i >= 1; i--)
		if (sm1[i] < mn) {
			nx1[nw] = i;
			nw = i;
			mn = sm1[i];
		}
	mn = sm2[1], nw = 1;
	for (int i = 2; i <= ct2; i++)
		if (sm2[i] <= mn) {
			nx2[nw] = i;
			nw = i;
			mn = sm2[i];
		}
	mn = sm2[ct2], nw = ct2;
	for (int i = ct2 - 1; i >= 1; i--)
		if (sm2[i] < mn) {
			nx2[nw] = i;
			nw = i;
			mn = sm2[i];
		}
	if (sm1[ct1] + sm2[ct2] > 0)
		return puts("No"), void();
	int p1 = 1, p2 = 1;
	while (nx1[p1] || nx2[p2]) {
		if (!nx1[p1]) {
			for (int j = p2 + 1; j <= nx2[p2]; j++)
				if (sm1[p1] + sm2[j] > 0) {
					puts("No");
					return;
				}
			p2 = nx2[p2];
			continue;
		}
		if (!nx2[p2]) {
			for (int j = p1 + 1; j <= nx1[p1]; j++)
				if (sm1[j] + sm2[p2] > 0) {
					puts("No");
					return;
				}
			p1 = nx2[p1];
			continue;
		}
		int fg = 0;
		for (int i = p1 + 1; i <= nx1[p1]; i++)
			if (sm1[i] + sm2[p2] > 0) {
				fg = 1;
				break;
			}
		if (!fg) {
			p1 = nx1[p1];
			continue;
		}
		for (int j = p2 + 1; j <= nx2[p2]; j++)
			if (sm1[p1] + sm2[j] > 0) {
				puts("No");
			return;
		}
		p2 = nx2[p2];
	}
	p1 = ct1, p2 = ct2;
	while (nx1[p1] || nx2[p2]) {
		if (!nx1[p1]) {
			for (int j = p2 - 1; j >= nx2[p2]; j--)
				if (sm1[p1] + sm2[j] > 0) {
					puts("No");
					return;
				}
			p2 = nx2[p2];
			continue;			
		}
		if (!nx2[p2]) {
			for (int j = p1 - 1; j >= nx1[p1]; j--)
				if (sm1[j] + sm2[p2] > 0) {
					puts("No");
					return;
				}
			p1 = nx2[p1];
			continue;			
		}
		int fg = 0;
		for (int i = p1 - 1; i >= nx1[p1]; i--)
			if (sm1[i] + sm2[p2] > 0) {
				fg = 1;
				break;
			}
		if (!fg) {
			p1 = nx1[p1];
			continue;
		}
		for (int j = p2 - 1; j >= nx2[p2]; j--)
			if (sm1[p1] + sm2[j] > 0) {
				puts("No");
			return;
		}
		p2 = nx2[p2];
	}
	puts("Yes");
}

signed main() {
	freopen("game.in", "r", stdin);
	freopen("game.out", "w", stdout);
	cin >> T;
	for (int i = 1; i <= T; i++)
		sve();
	return 0;
}

T2

显然考虑 \(O(n^2)\) 的 dp。

朴素的 dp 定义是 \(dp_{i,j}\) 表示长度为 \(i\) 的序列，\(j\) 次消除的方案数。然而发现这样转移的复杂度难以接受，需要分别枚举左右区间的消除次数。

考虑某一个位置 \(x\) 的消除次数由什么决定。对于只有某一边有 \(>a_x\) 的，则这个位置的消除次数一定是 \(j-1\)。对于两边都有 \(>a_x\) 的，两边的消除次数有一个是 \(j-1\)。那么就考虑前缀和优化这个 dp，则定义 \(dp_{i,j,0/1}\) 表示长度为 \(i\) 的序列，至多 \(j\) 次消除，有一边 / 两边 \(>a_x\) 的方案数，那么 \(j\) 便由 \(j,j-1\) 转移而来。

时间复杂度大抵是 \(O(n^2\log^2n)\)。