题解：P12834 [蓝桥杯 2025 国 B] 项链排列

~~一道赤裸裸的贪心+构造题~~

1. 题意：

题意很清楚了~~eee……我太懒了，没写~~

2. 解法：

考虑一个答案串中贡献“变化次数”的子串，要么是

\begin{cases} 以 L 开头的，LQLQLQ \dots\ \\ 以 Q 开头的，QLQLQL \dots\ \end{cases}

我们定义两类贡献子段贡献的变化次数为

C

时，需要

L

和

Q

的数量为：

Lneed_i，Qneed_i(i=1,2表示第几类贡献子段)

容易得

Lneed_1=C/2+1，Qneed_1=(C+1)/2

Lneed_2=(C+1)/2，Qneed_2=C/2+1

显然如果能用第一种就用，不够再用第二种。接下来根据题意构造即可。

3. 代码：

CPP

#include <bits/stdc++.h>
using namespace std;

int a, b, c;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> a >> b >> c;
	if (c == 0) { // 判断是否无解
		if (a > 0 && b > 0) {
			cout << -1 << endl;
			return 0;
		} else { // 否则有解
			for (int i = 1; i <= a; i ++) cout << "L";
			for (int i = 1; i <= b; i ++) cout << "Q";
			cout << endl;
			return 0;
		}
	}
	int Lneed = c / 2 + 1, Rneed = (c + 1) / 2;
	if (a >= Lneed && b >= Rneed) {
		for (int i = 1; i <= a - Lneed; i ++) cout << "L";
		for (int i = 1; i <= Lneed + Rneed - 1; i ++) {
			if (i % 2) cout << "L";
			else cout << "Q";
		}
		if ((Lneed + Rneed) % 2) {
			for (int i = 1; i <= b - Rneed; i ++) cout << "Q";
			cout << "L" << endl;
		} else {
			cout << "Q";
			for (int i = 1; i <= b - Rneed; i ++) cout << "Q";
		}
	} else {
		swap(Lneed, Rneed);
		if (a < Lneed || b < Rneed) {
			cout << -1 << endl;
			return 0;
		}
		for (int i = 1; i <= Lneed + Rneed; i ++) {
			if (i % 2) cout << "Q";
			else cout << "L";
		}
		for (int i = 1; i <= b - Rneed; i ++) cout << "Q";
	}
	return 0;
}

题解：P12834 [蓝桥杯 2025 国 B] 项链排列

文章操作

1. 题意：

2. 解法：

3. 代码：

相关推荐

评论

题解：P12834 [蓝桥杯 2025 国 B] 项链排列