基本情况

ABCE 秒了，D小细节处理出错（太久没写dp）+4。

D - String Bags

https://atcoder.jp/contests/abc344/tasks/abc344_d

分组背包，但是字符串的细节要注意

signed main() {
    int n;
    std::string T, str[110][15];
    int F[110][110], a[110];
    std::cin >> T >> n;
    int m(sz(T));
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        for (int j = 1; j <= a[i]; j++) {
            std::cin >> str[i][j];
        }
    }
    std::memset(F, 0x3f, sizeof F);
    F[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++)  {
            F[i][j] = F[i - 1][j];
            for (int k = 1; k <= a[i]; k++) {
                if (j >= sz(str[i][k]) and T.substr(j - sz(str[i][k]), sz(str[i][k])) == str[i][k]) {
                    F[i][j] = std::min(F[i][j], F[i - 1][j - sz(str[i][k])] + 1);
                }
            }
        }
    }
    if (F[n][m] == 0x3f3f3f3f) {
        F[n][m] = -1;
    }
    std::cout << F[n][m] << '\n';
    return 0;
}

E - Insert or Erase

https://atcoder.jp/contests/abc344/tasks/abc344_e

思路很直接，用 \(map\) 映射双链表的下标即可。

\(MyCode\)

signed main() {
    
    std::map<int, int> l, r;

    r[0] = INT_MAX;
    l[INT_MAX] = 0;

    int n, q;

    std::cin >> n;

    auto add = [&](int x, int y) -> void {//把y插入到x右边
        r[y] = r[x];
        l[r[x]] = y;
        r[x] = y;
        l[y] = x;
    };

    auto del = [&](int x) -> void {//删除x元素
        r[l[x]] = r[x];
        l[r[x]] = l[x];
    };  


    for (int i = 0, x = 0, y; i < n; i++) {//读入初始元素
        std::cin >> y;
        add(x, y);
        x = y;
    }

    std::cin >> q;

    for (int i = 0, op, x, y; i < q; i++) {
        std::cin >> op;
        if (op == 1) {
            std::cin >> x >> y;
            add(x, y);
        }
        else {
            std::cin >> x;
            del(x);
        }
    }   

    for (int x = r[0]; x != INT_MAX; x = r[x]) {
        std::cout << x << ' ';
    }
    
    return 0;
}

\(\texttt{STLcode}\)

signed main(){
    std::list<int> L;
    int n, q;
    std::cin >> n;
    std::map<int, std::list<int>::iterator> itMap;//存元素x对应的迭代器
    for (int i = 0, x; i < n; i++) {
        std::cin >> x;
        L.emplace_back(x);
        itMap[x] = (--L.end());
    }
    std::cin >> q;
    while(q--) {
        int o; std::cin >> o;
        if (o == 1) {
            int x, y; std::cin >> x >> y;
            auto it(itMap[x]);
            ++it;//所以it要自增
            L.emplace(it, y);//emplace在it之前插入
            itMap[y] = --it; 
        }
        else {
            int y; std::cin >> y;
            L.erase(itMap[y]);
        }
    }
    for (auto x : L) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}