Codeforces Round 1087 (Div. 2)——CF-2209-D. Ghostfires(奇数的构造可以先枚举多出来的东西)(怎么样凑出最多的 gb,gr,rb?求解方程组)(贪心构造的有问题?就强制多枚举前缀,我们直接给贪心暴力枚举一个长度 为 3 的前缀,这在遇到奇偶性问题的时候尤其有用) · znzryb
## 题目大意
**题面总结**
给定多组数据。每组给出三种幽火数量:红色 `r`、绿色 `g`、蓝色 `b`。
你需要构造一个只由 `R`、`G`、`B` 组成的字符串 `s`,表示按顺序摆放的幽火颜色,要求:
- `R`、`G`、`B` 的使用次数分别不超过 `r`、`g`、`b`。
- 对**任意相邻位置,颜色不能相同**,即 `s_i != s_{i+1}`。
- 对**任意间隔 2 个位置(下标差 3)的位置,颜色也不能相同**,即 `s_i != s_{i+3}`。
- 在满足以上条件下,`|s|` 要尽可能长。
如果有多个最长可行答案,输出任意一个即可。
**输入输出要求**
- 输入第一行为测试组数 `t`。
- 每组输入一行三个整数 `r g b`。
- 对每组输出一行构造出的字符串 `s`。
**数据范围**
- `1 <= t <= 10^4`
- `0 <= r, g, b <= 10^6`
- `r + g + b > 0`
- 所有测试组的 `r + g + b` 总和不超过 `10^6`
**样例**
```
输入
5
0 0 1
1 1 1
0 3 0
2 2 2
2 7 3
输出
B
RGB
G
GBRBRG
GRGRGBGBGBG
```
**样例配合说明**
- 第 1 组:只有 1 个蓝色,输出 `B`,长度为 1 且合法。
- 第 2 组:三种颜色各 1 个,`RGB` 使用了全部 3 个且满足限制。
- 第 3 组:只有绿色 3 个,但相邻不能同色,所以最多只能放 1 个,输出 `G`。
- 第 4 组:`GBRBRG` 长度为 6,刚好把 `2,2,2` 全部用完,并满足相邻与间隔 2 的限制。
- 第 5 组:`GRGRGBGBGBG` 在给定数量下给出一个满足条件的最长构造。
## 思路讲解

不难发现,能够凑的话,肯定是凑出足够的这个 gb,gr,rb 最好。但是怎么样凑出最多的 gb,gr,rb?其实这个就是求解一个线性方程组(如上),我们可以得到 rb 的这个数量。
但你会发现,如果采用数学式方法,去求解这个二元组的数量,然后去做,肯定是能做出来的,但是坑非常多,首先,这个元组是有可能 rb 求出来是一个负数。
这道题目怎么做?如下。

当然,你说为什么就强制给他安一个前缀就对了?其实也没什么神秘的,其实到最后,就是一个**奇偶性问题**,奇偶性问题有的时候一个的改变,就足以改变正确性了。
```cpp
// 强制枚举前缀
for (int i = 0; i < pow3[3]; ++i) {
ll opi = i;
vector<Num_color> rgb = rgb_global;
string ans;
auto push_to_ans = [&](ll i) {
ans.push_back(rgb[i].color);
rgb[i].num--;
};
auto check_ans = [&]() {
for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
if (i - 1 < 0) {
break;
}
if (ans[i] == ans[i - 1]) {
return false;
}
}
for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
if (i - 3 < 0) {
break;
}
if (ans[i] == ans[i - 3]) {
return false;
}
}
return true;
};
auto check_ans_all = [&]() {
for (int i = SZ(ans) - 1; i >= 0; --i) {
if (i - 1 < 0) {
break;
}
if (ans[i] == ans[i - 1]) {
return false;
}
}
for (int i = SZ(ans) - 1; i >= 0; --i) {
if (i - 3 < 0) {
break;
}
if (ans[i] == ans[i - 3]) {
return false;
}
}
return true;
};
while (opi != 0) {
push_to_ans(opi % 3);
opi/=3;
}
if (!check_ans_all()) {
continue;
}
sort(all(rgb), cmp);
if (rgb[2].num < 0) {
continue;
}
while (true) {
sort(all(rgb), cmp);
if (rgb[2].num > 0) {
push_to_ans(0);
push_to_ans(2);
if (!check_ans()) {
swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
if (!check_ans()) {
break;
}
}
// 以后尽量不要这么写 continue,万一漏了很难 debug 出来
continue;
}
if (rgb[1].num > 0) {
push_to_ans(0);
push_to_ans(1);
if (!check_ans()) {
swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
if (!check_ans()) {
break;
}
}
continue;
}
if (rgb[0].num > 0) {
push_to_ans(0);
if (!check_ans()) {
ans.pop_back();
break;
}
}
break;
}
// #ifdef LOCAL
// debug(ans);
// debug(ans_global);
// #endif
if (SZ(ans) > SZ(ans_global)) {
swap(ans, ans_global);
}
}
cout << ans_global << "\n";
```
## AC代码
AC
[https://codeforces.com/contest/2209/submission/367802322](https://codeforces.com/contest/2209/submission/367802322)
::: 源代码
```cpp
/**
* Problem: D. Ghostfires
* Contest: Codeforces Round 1087 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2209/problem/D
* Created: 2026-03-22 22:40:59
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct Num_color {
ll num;
char color;
// ll used;
};
bool cmp(const Num_color &a, const Num_color &b) {
return a.num > b.num;
}
void Solve() {
vector<Num_color> rgb_global(3);
cin >> rgb_global[0].num >> rgb_global[1].num >> rgb_global[2].num;
rgb_global[0].color = 'R';
rgb_global[1].color = 'G';
rgb_global[2].color = 'B';
string ans_global;
vector<ll> pow3(30);
pow3[0] = 1;
for (int i = 1; i <= 25; ++i) {
pow3[i] = pow3[i - 1] * 3;
}
for (int i = 0; i < pow3[3]; ++i) {
ll opi = i;
vector<Num_color> rgb = rgb_global;
string ans;
auto push_to_ans = [&](ll i) {
ans.push_back(rgb[i].color);
rgb[i].num--;
};
auto check_ans = [&]() {
for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
if (i - 1 < 0) {
break;
}
if (ans[i] == ans[i - 1]) {
return false;
}
}
for (int i = SZ(ans) - 1; i >= SZ(ans) - 2; --i) {
if (i - 3 < 0) {
break;
}
if (ans[i] == ans[i - 3]) {
return false;
}
}
return true;
};
auto check_ans_all = [&]() {
for (int i = SZ(ans) - 1; i >= 0; --i) {
if (i - 1 < 0) {
break;
}
if (ans[i] == ans[i - 1]) {
return false;
}
}
for (int i = SZ(ans) - 1; i >= 0; --i) {
if (i - 3 < 0) {
break;
}
if (ans[i] == ans[i - 3]) {
return false;
}
}
return true;
};
while (opi != 0) {
push_to_ans(opi % 3);
opi/=3;
}
if (!check_ans_all()) {
continue;
}
sort(all(rgb), cmp);
if (rgb[2].num < 0) {
continue;
}
while (true) {
sort(all(rgb), cmp);
if (rgb[2].num > 0) {
push_to_ans(0);
push_to_ans(2);
if (!check_ans()) {
swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
if (!check_ans()) {
break;
}
}
continue;
}
if (rgb[1].num > 0) {
push_to_ans(0);
push_to_ans(1);
if (!check_ans()) {
swap(ans[SZ(ans) - 1], ans[SZ(ans) - 2]);
if (!check_ans()) {
break;
}
}
continue;
}
if (rgb[0].num > 0) {
push_to_ans(0);
if (!check_ans()) {
ans.pop_back();
break;
}
}
break;
}
// #ifdef LOCAL
// debug(ans);
// debug(ans_global);
// #endif
if (SZ(ans) > SZ(ans_global)) {
swap(ans, ans_global);
}
}
cout << ans_global << "\n";
#ifdef LOCAL
vector<Num_color> rgb_back = rgb_global;
for (int i = 0; i < SZ(ans_global) - 1; ++i) {
if (ans_global[i] == ans_global[i + 1]) {
cout << "NO\n";
cout << "WA ON " << i << "\n";
return;
}
}
for (int i = 0; i < SZ(ans_global) - 3; ++i) {
if (ans_global[i] == ans_global[i + 3]) {
cout << "NO\n";
cout << "WA ON " << i << "\n";
return;
}
}
string brute;
// ll ans;
auto dfs = [&](auto &&go, string s) -> void {
if (SZ(s) > SZ(brute)) {
brute = s;
}
for (int i = 0; i < 3; ++i) {
if (rgb_back[i].num >= 1) {
if (SZ(s) >= 1) {
if (s.back() == rgb_back[i].color) {
continue;
}
}
if (SZ(s) >= 3) {
if (s[SZ(s) - 3] == rgb_back[i].color) {
continue;
}
}
rgb_back[i].num--;
go(go, s + rgb_back[i].color);
rgb_back[i].num++;
}
}
};
dfs(dfs, "");
if (SZ(brute) != SZ(ans_global)) {
cout << "too small\n";
cout << brute << "\n";
}
#endif
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2209/submission/367802322
_______________[ Stress test, testcase 1 INPUT ]_______________
1
2 7 5
_______________[ Stress test, testcase 1 OUTPUT]_______________
GBGBGBGBGBGRG
too small
RGRGBGBGBGBGBG
*/
```
:::
## 心路历程(WA,TLE,MLE……)
写对拍器的时候,为了防止对拍写的有问题,最好写为不等于,这样子,对拍器生成的字符串过小也可以非常容易的看出来。
```cpp
dfs(dfs, "");
if (SZ(brute) != SZ(ans)) {
cout << "too small\n";
cout << brute << "\n";
}
```