链接：https://atcoder.jp/contests/abc418

A – I’m a teapot

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n;
    string s;
    cin >> n >> s;

    if (n < 3)
        cout << "No" << endl;
    else
    {
        if (s.substr(n - 3) == "tea")
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}

---

B – You’re a teapot

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    string s;
    cin >> s;

    int n = s.size();

    double ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            if (s[i] == 't' && s[j] == 't' && j - i + 1 >= 3)
            {
                ll cnt = 0;
                for (int k = i; k <= j; ++k)
                {
                    if (s[k] == 't')
                        ++cnt;
                }

                double now = (double(cnt) - 2.0) / (double(j) - i - 1.0);

                ans = max(ans, now);
            }
        }
    }

    printf("%.13lf\n", ans);
}

---

C – Flush

算法：

    博弈论，预处理，推公式，鸽巢原理。

思路：

    将数组 \(A\) 按升序排序，并计算前缀和数组 \(S\)，其中 \(S[i]\) 表示前 \(i\) 个元素的和。

    预处理所有可能的 \(b\) 的答案：

    对于每个 \(b\)，计算最小的 \(x = \sum \min(A_i, b-1) + 1\)，确保任意选 \(x\) 个茶包后，至少有一种口味出现 \(b\) 次（根据鸽巢原理，庄家最多能选 \(\sum \min(A_i, b-1)\) 个茶包避免此情况）。

    高效计算 \(\sum \min(A_i, b-1)\)：找到满足 \(A[pos] \geq b\) 的位置 \(pos\)，然后计算 \(S[pos-1]\)（较小 \(A_i\)​ 的全部贡献）加上 \((n – pos + 1) \times (b-1)\)（较大 \(A_i\)​ 的受限贡献）。

    对于每个询问 \(B_j\)，若 \(B_j > \max(A_i)\)，输出 \(-1\)；否则输出预处理的 \(x\)。

关键代码：

void solve()
{
    int n, q;
    cin >> n >> q;

    ll maxx = INT_MIN;
    vector<int> a(n + 10);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        maxx = max(maxx, 1ll * a[i]);
    }

    sort(a.begin() + 1, a.begin() + n + 1);

    vector<ll> s(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i];

    ll pos = 1;
    vector<ll> ans(min(1ll * N, s[n] + 10));
    ans[1] = 1;
    for (int i = 2; i <= min(1ll * N - 5, s[n] + 5) && i <= maxx; ++i)
    {
        while (pos < n && i > a[pos])
            ++pos;

        ans[i] = s[pos - 1] + (n - pos + 1) * (i - 1) + 1;
    }

    while (q--)
    {
        int b;
        cin >> b;

        if (b > maxx)
        {
            cout << -1 << endl;
            continue;
        }

        cout << ans[b] << endl;
    }
}

---

D – XNOR Operation

算法：

    模拟，贪心，前缀技巧。

思路：

问题转化：

    不难发现，一个子串要想是 美丽的，它必须包含 偶数个 \(0\)。

    因此，原题就转化为：统计字符串中 \(0\) 的个数为偶数 的子串数量（注意不同位置的相同字符串也要分别计数）。

为什么“偶数个 0”就是美丽的？

    我们仔细分析题目中的合并规则：

• 相同为 \(1\)
• 不同为 \(0\)

    这正是 \(XNOR\)（同或、异或非） 运算的真值表。

    映射到乘法：将 ‘\(0\)‘ 映射为 \(-1\)，’\(1\)‘ 映射为 \(+1\)，可以发现两位合并时的规则，刚好对应数值的乘法：

原位对	数值对	乘积	对应结果
0 0	-1 -1	+1	1
0 1	-1 +1	-1	0
1 0	+1 -1	-1	0
1 1	+1 +1	+1	1

    乘法是结合律成立的，所以不管合并顺序如何，最终的结果就是整个子串中所有映射值的乘积。

    最终乘积为 \(+1\)（即结果为 \(1\)）当且仅当子串中 \(-1\) 的个数为偶数，也就是说 ‘\(0\)‘ 的个数为偶数。

如何统计偶数个 0 的子串数？

    这是一个经典的区间计数问题。

1. 定义 \(pre[i]\) 表示前 \(i\) 个字符中 \(0\) 的个数。
2. 子串 \((l, r)\) 中 \(0\) 的个数为： \(pre[r] – pre[l-1]\)
3. 要这个值是偶数，当且仅当： \(pre[r] \bmod 2 = pre[l-1] \bmod 2\)
4. 也就是说，子串左右端点对应的前缀 \(0\) 个数的奇偶性相同。

    因此，我们只需在遍历字符串时，维护一个 \(cnt[2]\)：

• \(cnt[0]\) 记录当前遇到的偶数奇偶前缀的数量
• \(cnt[1]\) 记录当前遇到的奇数奇偶前缀的数量

    每次到一个新前缀，假设它的奇偶性是 \(p\)：

• 答案增加 \(cnt[p]\)（因为与之前所有奇偶性相同的前缀，都能组成一个偶数 \(0\) 的子串）
• 然后 \(cnt[p]++\) 更新计数

关键代码：

void solve()
{
    int n;
    string s;
    cin >> n >> s;

    s = ' ' + s;

    vector<ll> pre(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + (s[i] == '0');

    ll cnt[2] = {0, 0};
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ++cnt[pre[i - 1] & 1];

        ans += cnt[pre[i] & 1];
    }

    cout << ans << endl;
}

E – Trapezium

    几何题就先不补了。