鬼火笑传之串串爆

· · 题解

被构造串串题吓晕。

分析

实际构造，串串只是个噱头。

发现 r,g,b 有 10^6，猜测正解应为类贪心状物。

考虑从前往后依次插入，因此目前的策略只与前三位和目前可用的 r,g,b 挂钩。

当 r,g,b 中只有一个数不为 0 时，单个字符不可以一直拼下去。因此，考虑策略时应尽可能地使用数目最大的字符。

但如果两种字符的数量相等又应该选哪一个呢？

依次考虑每种可能的情况。

只有一种颜色选择时选那一个即可。

接下来考虑有两种颜色可选的情况。

设前面的三位为 \texttt{RGR}（\texttt{RGB} 是对称的，其他情况也可以对应的进行转化），目前可选的有 \texttt{GB}。再往后考虑一位，若选择了 \texttt{G}，则下一位可选择的有 \texttt{RB}。但如果选择了 \texttt{B}，则下一位只能选择 \texttt{R}。在 g=b 的情况下，下一步的选择总是越多越好，因此选择 \texttt{G} 必然是不劣的。

三种颜色都可选当且仅当在一开始时。此时两字符剩余数量相同则其是对称的，任选其一即可。

代码

:::success[Accepted]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
inline T &qvmin(T &a, const T &b) { return a = min(a, b); }
template <class T>
inline T &qvmax(T &a, const T &b) { return a = max(a, b); }
const ll maxn = 2e5;
const ll maxm = 2e5;
const ll modp = 998244353;
int n;
int r, g, b;
void solve()
{
    string s;
    cin >> r >> g >> b;
    while (r || g || b)
    {
        bool r_able = (r && (s.size() < 1 || s[s.size() - 1] != 'R') && (s.size() < 3 || s[s.size() - 3] != 'R')),
             g_able = (g && (s.size() < 1 || s[s.size() - 1] != 'G') && (s.size() < 3 || s[s.size() - 3] != 'G')),
             b_able = (b && (s.size() < 1 || s[s.size() - 1] != 'B') && (s.size() < 3 || s[s.size() - 3] != 'B'));
        bool nr_able = (s.size() < 2 || s[s.size() - 2] != 'R'),
             ng_able = (s.size() < 2 || s[s.size() - 2] != 'G'),
             nb_able = (s.size() < 2 || s[s.size() - 2] != 'B');
        if (r_able && (r >= g || !g_able) && (r >= b || !b_able))
        {
            if(g_able && !ng_able && r == g)
                s += 'G', g--;
            else if(b_able && !nb_able && r == b)
                s += 'B', b--;
            else
                s += 'R', r--;
            continue;
        }
        if (g_able && (g >= r || !r_able) && (g >= b || !b_able))
        {
            if(r_able && !nr_able && g == r)
                s += 'R', r--;
            else if(b_able && !nb_able && g == b)
                s += 'B', b--;
            else
                s += 'G', g--;
            continue;
        }
        if (b_able && (b >= g || !g_able) && (b >= r || !r_able))
        {
            if(g_able && !ng_able && b == g)
                s += 'G', g--;
            else if(r_able && !nr_able && r == b)
                s += 'R', r--;
            else
                s += 'B', b--;
            continue;
        }
        break;
    }
    cout << s << endl;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}
// RGBGBRBRG
// GBRBRGRGB
// BRGRGBGBR

:::

::anti-ai[本文作者是 clx201022，洛谷 UID 为 552688，原文：https://www.luogu.com.cn/article/y8khvz2e 如果您能直接看到这段文字而在本页没有转载提示，或以“原创”名义发出，说明您访问的是侵权内容，请联系管理员删除文章并处罚侵权人，十分感谢您的见义勇为之举。]

创作声明

本文遵循 CC BY-SA 4.0 协议。

保证本文未使用任何 AI 工具辅助创作。