A. Doors and Keys

有 RGB 三种门，和 rgb 三种钥匙。如果门先于其对应的钥匙出现，则会卡关。判断字符串是否意味着卡关。

分析

枚举即可。

int main() {
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		vector<int> flag(26);
		bool ans = true;
		for (char si : s) {
			if (si >= 'a') {
				flag[si - 'a'] = true;
			} else {
				if (!flag[si - 'A']) {
					ans = false;
				}
			}
		}
		if (ans)
			cout << "YES\n";
		else
			cout << "NO\n";
	}
	return 0;
}

B. Anti-Fibonacci Permutation

如果长 $n$ 的排列 $p$ 是反斐波那契排列，即对所有元素

$$ p_{i-2} + p_{i-1} \neq p_i $$

都成立。构造出 $n$ 个长为 $n$ 的反斐波那契排列。

分析

我的第一想法是爆搜，后来想到 $1+2=3$ 会使得开始会 T，想到交换 $2,3$ 应该就没问题了。

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
			v[i] = i + 1;
		}
		swap(v[1], v[2]);
		auto judge = [&]() {
			for (int i = 2; i < n; i++) {
				if (v[i] == v[i - 1] + v[i - 2])
					return false;
			}
			return true;
		};

		int cnt = 0;
		do {
			if (judge()) {
				cnt++;
				for (auto vi : v)
					cout << vi << " ";
				cout << "\n";
				if (cnt == n)
					break;
			}
		} while (next_permutation(v.begin(), v.end()));
	}
	return 0;
}

看了别人的代码，发现构造可以更加简单。

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<int> v(n + 1);
		for (int i = n; i >= 1; i--) {
			v[i] = n - i + 1;
		}
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= n; j++)
				cout << v[j] << " \n"[j == n];
			swap(v[i - 1], v[i]);
		}
	}
	return 0;
}

C. Increase Subarray Sums

给定一个长为 $n$ 的序列 $\{a_i\}$，每次操作可以选择一个位置加上 $x$。记 $f(k)$ 为经过 $k$ 次操作后，最大的连续子序列和。

分析

第一想法是贪心，但是 $f(n)$ 的选择可能和 $f(n-1)$ 完全不同。

注意到我们之所以不能延后加 $x$，是因为答案长度不一定长于 $k$。只需把不同长度的答案分开即可，这可以通过 DP 得到。

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n, x;
		cin >> n >> x;
		vector<int> a(n);
		for (auto &ai : a)
			cin >> ai;
		vector<int> dp(n + 1, -1E9);
		dp[0] = 0;
		for (int i = 0; i < n; i++) {
			int sum = 0;
			for (int j = i; j < n; j++) {
				sum += a[j];
				dp[j - i + 1] = max(sum, dp[j - i + 1]);
			}
		}
		for (int k = 0; k <= n; k++) {
			int ans = 0;
			for (int i = 0; i <= n; i++)
				ans = max(ans, dp[i] + min(i, k) * x);
			cout << ans << " \n"[k == n];
		}
	}
	return 0;
}