题解：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. 代码：

#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;
}