前言

没想到我出的 C、D 题，竟成为全场通过数最少的两题！

请注意，本篇题解采用 HTML 中 <details> 标签特性，因而大家可以点击标题以展开查看详细内容。

大家在设计网页的时候，也可利用该特性防止 “剧透”：

<details>
<summary>标题</summary>

内容
</details>

展示效果如下：

标题

内容

C. 书中自有______

提示

点击查看

黄金屋举世难觅，而颜如玉随处可见，此因黄金屋（gold）之判断标准较为严苛，而颜如玉（girl）之判断标准较为宽松。亦如 “备注” 所言：“寻物而不得，非物之稀，实择之过苛也。”

题解

点击查看

设字符串 长度为 。定义 “ 中 作为子序串出现次数” 是指从 中选择 个字符删除，得到 ，这样的操作方法的数量；定义 “ 中 作为无序子串出现次数” 是指从 中选择 个字符，使之按某顺序排列后能组成 ，这样的操作方法的数量。

设输入字符串为 。观察样例可知，设 中 “gold” 作为子序串出现次数为 ，“girl” 作为无序子串出现次数为 ，则答案为 。

要求出 的值，可以利用动态规划（DP）技巧解决。定义 表示 的前 个字符所组成字符串中 “gold” 的前 个字符所组成字符串作为子序串出现次数，则：

  • 当 时，。
  • 当 时，。
  • 当 且 时，。其中，当 的第 个字符等于 “gold” 的第 个字符时，；否则，。

于是， 即为 的值。

要求出 的值，只需统计 中字符 “g” 出现次数、字符 “i” 出现次数、字符 “r” 出现次数、字符 “l” 出现次数，计算这四个数的乘积即可。

时间复杂度：每个测试用例 。

代码（C++）：

#include <iostream>
#include <string>
#include <vector>

using namespace std;
using LL = long long;

const LL MOD = 998'244'353;

LL gold(const string& s)
{
    LL results[5]{};
    results[0] = 1;
    for (LL i = 0; i < (LL)s.length(); ++i)
        for (LL j = 0; j < 4; ++j)
            if (s[i] == "gold"[j])
            {
                results[j + 1] += results[j];
                results[j + 1] %= MOD;
            }
    return results[4];
}

LL girl(const string& s)
{
    LL counts[4]{};
    LL result = 0;
    for (char c : s)
        for (LL j = 0; j < 4; ++j)
            if (c == "girl"[j])
                ++counts[j];
    result = 1;
    for (LL j = 0; j < 4; ++j)
    {
        result *= counts[j];
        result %= MOD;
    }
    return result;
}

void test_case()
{
    LL result = 0;
    string s;
    cin >> s;
    result = gold(s) * girl(s) % MOD;
    cout << result << '\n';
}

int main()
{
    LL tests = 0;
    cin >> tests;
    while (tests > 0)
    {
        test_case();
        --tests;
    }
}

D. 谁是说谎者

提示 1

点击查看

注意到说谎组有 位选手，但输入只给出了前 位选手所说的话。

还少一位选手，是谁呢？好难猜啊……

提示 2

点击查看

等等……“已知说谎组中至少有 位选手说谎了”……难道说……

题解

点击查看

这道题的描述存在叙述性诡计。题中 “说谎组中至少有 位选手说谎了” 并不是已知条件，而是第 位选手所说的话。

令 。为了侦破说谎选手的编号，我们可以先假定每位选手是否说谎了，再检查这一假定是否成立。

每位选手可能说谎，也可能不说谎，有 种状态，那么所有选手是否说谎就有 种状态。枚举这 种状态，对于每种状态检查是否对于一切 都有 “第 位选手没有说谎” 和 “说谎组中至少有 位选手说谎了” 这两个命题真假性相同。一旦发现满足条件，就说明该状态是正确答案。当然，如果没有状态满足条件，就说明我们被骗了。

时间复杂度：。

代码（C++）：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    a[n] = 3;
    ++n;
    for (int x = 0; x < 1 << n; ++x)
    {
        int p = 0;
        bool fail = false;
        for (int i = 0; i < n; ++i)
            if (((x >> i) & 1) != 0)
                ++p;
        for (int i = 0; i < n; ++i)
            if ((((x >> i) & 1) == 0) != (p >= a[i]))
            {
                fail = true;
                break;
            }
        if (fail)
            continue;
        cout << p;
        for (int i = 0; i < n; ++i)
            if (((x >> i) & 1) != 0)
                cout << ' ' << i + 1;
        cout << '\n';
        return 0;
    }
    cout << "-1\n";
}