OI字符串问题 - 遗忘了他的世界，deque

Question

请教字符串的操作题目：E. 遗忘了它的世界

题目背景

世界正在遗忘它，遗忘它的名字，遗忘它的事迹，遗忘它的足迹，只有你还记得它的名字。

题目描述

一切关于他的事情都被遗忘了，哪怕只是一个小小的字符串。

我们给出$n$和它的名字，表示有$n$个待遗忘字符串。

对于每个待遗忘字符串 $a$ 与它的名字$n$我们将在$a$中所有存在于$n$的字符进行删除操作，处理后的字符串就是遗忘后的字符串。

如果$a$的每个字符都能在$n$中找到位置不重复且$ ASCII $值相等的字符(即 $ch$字符在$n$中出现多少次，在$a$中至少出现同样的次数)。我们称$n$为“遗忘字符串”。

(如 $b$ 为 $abb$，$a1 $为$ baa$，$a2 $为 $bbab$，$a2$是“遗忘字符串”，而 $a1$ 不是)。

输出所有遗忘后的字符串。

对于“遗忘字符串”，我们分别输出遗忘前的字符串与遗忘后的字符串。

如果待遗忘字符串与它的名字相等，输出$equal$.

输入格式

第一行输入$l$代表数据总组数。

对于每组数据：
首先输入字符串总数$a$和他的名字。
然后输入$a$行，每行一个字符串。

输出格式

首先输出$n$行，每行对应一个遗忘的字符串。
如果遗忘的字符串为空串，那么输出一个空行。
然后，对于每个“遗忘字符串”，输出两行。
第一行为 $past：$遗忘前的字符串

第二行为 $now：$遗忘后的字符串或$equal$

样例

样例输入

2
2 zyx
fxl
itzex
4 fxl
iamfxl
ixpxi
ifxli
fxl

样例输出

fl
ite
iam
ipi
ii

past:iamfxl
now:iam
past:ifxli
now:ii
past:fxl
now:equal

数据范围

我的思路

check函数判断、去重；创建deque存储名字和待遗忘字符串，排序后依次pop_front()，然后判断剩下的front哪个大，判别它是不是遗忘字符串。最后输出。

我的代码

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
#include <deque>

using namespace std;

vector <char> except;
vector <string> strs;
deque <char> exc, qname;
string name, tmp, ans;
int n, data;
char nextc;

inline void check(string str, string nam) {
    except.clear();
    pair <int, int> let[27];
    bool flag = false;
    int tmp = 0;
    for (int i = 0; i < nam.length(); ++i) {
        for (int j = 0; j < str.length(); ++j)
            if (name[i] == str[j])
                except.push_back(str[j]);
    }
    for (int i = 0; i < except.size(); ++i) {
        if (except[i] == nextc)
            except[i] = 127;
        else
            nextc = except[i];
    }
    sort(except.begin(), except.end());
    sort(nam.begin(), nam.end());
    for (int i = 0; i < except.size(); ++i) exc.push_back(except[i]);
    for (int i = 0; i < nam.size(); ++i) qname.push_back(nam[i]);
    while (!qname.empty() && !exc.empty()) {
        while (qname.empty() || exc.empty() ? false : qname.front() == exc.front()) {
            qname.pop_front();
            exc.pop_front();
            ++tmp;
        }
        if (qname.empty() || exc.empty() ? false : qname.front() >= exc.front())
            flag = true;
        else
            flag = false;
    }
    if (flag) {
        cout << "past:" << str << "\nnow:";
        for (int i = 0; i < str.length(); ++i) {
            for (int j = 0; j < name.length(); ++j) {
                if (str[i] == name[j])
                    goto nrsame;
            }
            cout << str[i];
        nrsame:;
        }
    }
    else {
        for (int i = 0; i < str.length(); ++i) {
            for (int j = 0; j < name.length(); ++j) {
                if (str[i] == name[j])
                    goto rsame;
            }
            cout << str[i];
        rsame:;
        }
    }
    cout << '\n';
    return;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin >> ::data;
    for (int iakioi = 0; iakioi < ::data; ++iakioi) {
        strs.clear();
        cin >> n >> name;
        for (int i = 0; i < n; ++i) {
            getline(cin, tmp, '\n');
            strs.push_back(tmp);
            if (tmp == name)
                cout << "past:" << tmp << "\nnow:equal\n";
            else if (tmp.length() == 1)
                cout << '\n';
            else
                check(tmp, name);
        }
    }
    system("pause");
    return 0;
}

Answer 1

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

using namespace std;

vector<string> forget(vector<string>& strs, const string& name) {
    unordered_map<char, int> name_chars;
    for (char c : name) {
        name_chars[c]++;
    }

    vector<string> results;
    for (const string& s : strs) {
        unordered_map<char, int> s_chars;
        for (char c : s) {
            s_chars[c]++;
        }

        bool is_forgotten = true;
        string forgotten_s;
        for (char c : s) {
            if (name_chars.count(c) && s_chars[c] >= name_chars[c]) {
                s_chars[c] -= name_chars[c];
            } else {
                is_forgotten = false;
                forgotten_s += c;
            }
        }

        if (is_forgotten) {
            results.push_back(forgotten_s);
        } else {
            results.push_back("");
        }
        cout << "past:" << s << endl;
        if (is_forgotten) {
            cout << "now:" << forgotten_s << endl;
        } else if (s == name) {
            cout << "now:equal" << endl;
        } else {
            cout << "now:" << s << endl;
        }
    }

    return results;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        string name;
        cin >> n >> name;

        vector<string> strs(n);
        for (int i = 0; i < n; i++) {
            cin >> strs[i];
        }

        forget(strs, name);

        if (t > 0) {
            cout << endl;
        }
    }

    return 0;
}

其思路如下：

对于每一个字符串 $s$，用一个哈希表 $s_chars$ 统计其中每个字符的出现次数。

再用一个哈希表 $name_chars$ 统计遗忘字符串 $name$ 中每个字符的出现次数。

对于 $s$ 中的每个字符 $c$，如果 $c$ 在 $name$ 中出现且 $s_chars[c] \geq name_chars[c]$，则说明 $c$ 在 $s$ 中出现次数不少于在 $name$ 中出现的次数，可以进行遗忘操作；否则说明 $c$ 不能被遗忘，此时将它追加到遗忘前的字符串 $forgotten_s$ 中。

如果 $s$ 的每个字符都能被遗忘，那么遗忘后的字符串就是 $forgotten_s$；否则 $s$ 不能被遗忘，遗忘后的字符串就是 $s$ 本身（如果 $s$ 与 $name$ 相等，则遗忘后的字符串为“equal”）。

最后输出所有的遗忘后的字符串。