题解：P3333 [ZJOI2013] 丽洁体

· · 题解

纪念校内模拟赛场切紫（虽然是水紫）

Solution

我们先考虑一些必要的操作。由于我们并不好操作单词的匹配，所以想到把单词映射处理，这里哈希完全可以用 map 来代替。处理时只需要把每个单词加进 map 里即可。

现在我们把问题转化为了：

给定某四个个正整数序列 T、A、B、C，删除 T 中的一些数，使 T 变为 A^{*}B^{*}C 的形式，也就是 A、B、C 与某些字符串 S 按顺序拼接而成的 T^{'}，求删除的最小次数，保证答案一定存在。

这样，我们把问题转化成了三个子问题：

  1. 将 T 的左边变成 A 的最小操作次数。
  2. 将 T 的右边变成 C 的最小操作次数。
  3. 将 1、2 操作完后的 T^{'} 中间删出一个 B 的最小操作次数。

对于 1、2，我们很容易得到能删尽量删，能匹配尽量匹配为最优的结论，因为 A 或 C 的某一个字符出现在前面或者后面的影响是一样的，都是得确保 T^{'} 的最左和最右一定是 A 和 C。

但是对于 3，我们的策略便失效了。因为很可能利用现在的左端点 l 不如接下来的某个左端点 l^{'} 优。一个很好的例子是这样：

I can love you as love myself forever
I
love myself
forever

这样答案是 0，但是能删尽量删，能匹配尽量匹配得到的答案是 3。

所以我们考虑更换策略。

值得注意的是，当存在端点 l < r 使得 B \subset T_{l\sim r}，那么答案可以用 r - l + 1 - |B| 来更新，而无需考虑具体的删除情况，所以我们将问题 2 转化为寻求最优的左、右端点 l、r。

一个很好的想法是双指针，这样复杂度能做到绝妙的 O(n)。但是很遗憾，我们不能很好的、简单的去维护 T_{l\sim r} 中 B 的出现情况。所以，我们退而求其次，转而只枚举左端点 l 并每次扫描最近的、合法的 r。这样我们的理论复杂度变为了 O(n^2)，这里 n 为单词数。

看到数据范围 |T| \le 50000，我们很慌啊！但是我们看下很重要的每个单词出现的次数不超过 500。也就是合法的左端点不超过 500 个，所以实际的复杂度应为 O(n)，常数只有很小的 500，可以通过本题。

于是我们就这样通过了本题。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 514;

namespace Otakus
{
    string T, A, B, C, str;
    unordered_map<string, int> dict;

    int a[N], b[N], c[N], t[N], cnt;
    int atp, btp, ctp, ttp;
    int vis[N], minn, Justin = N;
    vector<int> nxt[N];

    void solve()
    {
        int len, ans = 0, i = 1, j = ttp; // and i is the left, j is the right

        // for A
        len = 0;
        while (len < atp)
        {
            if (t[i] == a[len + 1])
                len++;
            else
                ans++;
            i++;
        }

        // for C
        len = ctp;
        while (len)
        {
            if (t[j] == c[len])
                len--;
            else
                ans++;
            j--;
        }

        // now, i ~ j to find B

        for (int l = i, r = i; (l <= j - btp + 1 && r <= j); l++) {
            if (t[l] != b[1])
                continue;
            len = 0, r = l;
            while (len < btp && r <= j)
            {
                if (t[r] == b[len + 1])
                    len++;
                r++;
            }
            if (len == btp)
                Justin = min(Justin, r - l - btp);
            else
                break;
        }

        cout << ans + Justin;
    }

    void init()
    {
        getline(cin, T);
        getline(cin, A);
        getline(cin, B);
        getline(cin, C);

        str = "";
        for (int i = 0; i < T.length(); i++)
        {
            if (T[i] == ' ') {
                if (!dict.count(str))
                    dict[str] = ++cnt;
                t[++ttp] = dict[str];
                str = "";
            }
            else if (T[i] - 'a' >= 0 && T[i] - 'a' < 26)
                str += T[i];
        }
        if (!dict.count(str))
            dict[str] = ++cnt;
        t[++ttp] = dict[str];

        str = "";
        for (int i = 0; i < A.length(); i++)
        {
            if (A[i] == ' ')
                a[++atp] = dict[str], str = "";
            else if (A[i] - 'a' >= 0 && A[i] - 'a' < 26)
                str += A[i];
        }
        a[++atp] = dict[str];

        str = "";
        for (int i = 0; i < B.length(); i++)
        {
            if (B[i] == ' ')
                b[++btp] = dict[str], str = "";
            else if (B[i] - 'a' >= 0 && B[i] - 'a' < 26)
                str += B[i];
        }
        b[++btp] = dict[str];

        str = "";
        for (int i = 0; i < C.length(); i++)
        {
            if (C[i] == ' ')
                c[++ctp] = dict[str], str = "";
            else if (C[i] - 'a' >= 0 && C[i] - 'a' < 26)
                str += C[i];
        }
        c[++ctp] = dict[str];

        solve();
    }
} // namespace Otakus

int main()
{

    // freopen("main.in", "r", stdin);
    // freopen("main.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Otakus::init();
    return 0;
}

最后，我认为降绿，理由如下：

1.此题的难度仅在于 STL 的运用以及字符串的读入。

2.数据不够强。如果真的卡到适当的、只允许双指针的精妙做法过那么紫就无可置疑。