344

A - Spoiler

输出两个 | 字符外面的字符串

void solve() {
    string s;cin >> s;
    int j = 1;
    for (int i = 0;i < s.size();i++) {
        if (s[i] != '|')cout << s[i];
        else {
            j = i;
            break;
        }
    }
    for (int i = j + 1;i < s.size();i++) {
        if (s[i] == '|') {
            j = i;
            break;
        }
    }
    for (int i = j + 1;i < s.size();i++) {
        cout << s[i];
    }
}

B - Delimiter

将输入的反向输出

void solve() {
    int x;
    vector<int>a;
    while (cin >> x)a.push_back(x);
    for (int i = a.size() - 1;i >= 0;i--)cout << a[i] << '\n';
}

C - A+B+C

看看是否能在 $a, b, c$ 数组里面各选一个组成 $x$ 的数字

int a[110], b[110], c[110], x[200010];
void solve() {
    int na, nb, nc, nx;
    cin >> na;
    for (int i = 1;i <= na;i++)cin >> a[i];
    cin >> nb;
    for (int i = 1;i <= nb;i++)cin >> b[i];
    cin >> nc;
    for (int i = 1;i <= nc;i++)cin >> c[i];
    cin >> nx;
    for (int i = 1;i <= nx;i++)cin >> x[i];
    map<int, int> num;
    for (int i = 1;i <= na;i++) {
        for (int j = 1;j <= nb;j++) {
            for (int k = 1;k <= nc;k++) {
                num[a[i] + b[j] + c[k]] = 1;
            }
        }
    }
    for (int i = 1;i <= nx;i++) {
        if (num[x[i]] == 1) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

D - String Bags

给出 $n$ 袋(每袋 $a_{i}$ 个字符串) 字符串，每袋可以选择 $0 - 1$ 个字符串，看能组成 $T$ 字符串所选择的最少的袋子个数。若无解输出-1

Solution

DP 没太看懂，也不太会(待更 $\dots$ )

$d p [i] [j]$ 代表在处理了前 $i$ 个袋子的情况下，匹配了 $T$ 字符串的前 $j$ 个字符，只需要看 $d p [n] [T . s i z e ()]$ 即可。

我们定义 $d p [$ 处理了多少个袋子 $] [$ 接头部与 $T$ 的匹配情况 $]$ = {达到所需的最小金额}。

考虑将第 $i + 1$ 个袋子中的字符串 $X$ 连接到 $S$ 的末尾。这时，为了从 $d p [i] [| S |]$ 迁移到 $d p [i + 1] [| S | + | X |]$ ，需要判断 $T$ 的第 $| S | + 1$ 个字符到第 $| S | + | X |$ 个字符的子字符串是否与 $X$ 匹配。在当前的约束条件下，可以采用直接判断的方法。

此外，不做任何处理对应着从 $d p [i] [j]$ 迁移到 $d p [i + 1] [j]$ 。

#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int main() {
    for (int i = 0;i < 105;i++) {
        for (int j = 0;j < 105;j++) {
            dp[i][j] = 1e9;
        }
    }
    dp[0][0] = 0;

    string t;
    cin >> t;
    int tl = t.size();
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < 105;j++) {
            dp[i + 1][j] = dp[i][j];
        }
        int m;
        cin >> m;
        while (m--) {
            string s;
            cin >> s;
            int sl = s.size();
            for (int j = 0;j + sl <= tl;j++) {
                bool ok = true;
                for (int k = 0;k < sl;k++) {
                    if (t[j + k] != s[k]) {
                        ok = false;break;
                    }
                }

                if (ok) {//当s字符串是T字符串的一部分的时候
                    dp[i + 1][j + sl] = min(dp[i + 1][j + sl], dp[i][j] + 1);
                }
            }
        }
    }

    if (dp[n][tl] == 1e9) dp[n][tl] = -1;
    cout << dp[n][tl] << "\n";
}

E - Insert or Erase

给你一个长度为 $N$ 的序列 $A = (A_{1}, \dots, A_{N})$ 。 $A$ 中的元素是不同的。

请按照给出的顺序处理 $Q$ 个查询。每个查询属于以下两种类型之一：

1 x y：在 $A$ 中元素 $x$ 后面紧接着插入 $y$ 。当给出此查询时，保证 $x$ 存在于 $A$ 中。
2 x：从 $A$ 中删除元素 $x$ 。当给出此查询时，保证 $x$ 存在于 $A$ 中。

保证在处理完每一个查询后， $A$ 都不是空的，并且其元素都是不同的。

处理完所有查询后，打印 $A$ 。

Solution

链表
不懂(待更 $\dots$ )

void solve() {
    int n;cin >> n;
    list<int> a;
    map<int, list<int>::iterator> mp;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;a.push_back(x);mp[x] = prev(a.end());
    }
    int q;cin >> q;
    while (q--) {
        int op;cin >> op;
        if (op == 1) {
            int x, y;cin >> x >> y;
            mp[y] = a.insert(next(mp[x]), y);
        } else {
            int x;cin >> x;
            a.erase(mp[x]);
        }
    }
    for (auto i : a)cout << i << " ";
}

F - Earn to Advance

四维 DP