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

A – Misdelivery

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<string> s(n);
    for (auto &x : s)
        cin >> x;

    int x;
    string t;
    cin >> x >> t;

    if (s[x - 1] == t)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

B – Fibonacci Reversed

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    vector<ll> dp(11);

    cin >> dp[1] >> dp[2];

    for (int i = 3; i <= 10; ++i)
    {
        string s = to_string(dp[i - 1] + dp[i - 2]);
        ranges::reverse(s);
        dp[i] = stoll(s);
    }

    cout << dp[10] << endl;
}

C – Alternated

算法：

    贪心。

思路：

    字符串最后只会有两种情况

• \(ABAB……\)
• \(BABA……\)

    考虑将字符串转换成这两种的最少次数即可。

    将所有位置与最终序列不相同的位置存储下来，交换两个字符所需的最小次数为下标之差，既 \(abs(j – i)\)。

关键代码：

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

    string t1, t2;
    for (int i = 0; i < n; ++i)
    {
        t1 += "AB";
        t2 += "BA";
    }

    vector<int> A, B;
    for (int i = 0; i < n + n; ++i)
    {
        if (s[i] != t1[i])
        {
            if (s[i] == 'A')
                A.push_back(i);
            else
                B.push_back(i);
        }
    }

    ll ans1 = 0;
    for (int i = 0; i < A.size(); ++i)
        ans1 += abs(A[i] - B[i]);

    A.clear(), B.clear();
    for (int i = 0; i < n + n; ++i)
    {
        if (s[i] != t2[i])
        {
            if (s[i] == 'A')
                A.push_back(i);
            else
                B.push_back(i);
        }
    }

    ll ans2 = 0;
    for (int i = 0; i < A.size(); ++i)
        ans2 += abs(A[i] - B[i]);

    cout << min(ans1, ans2) << endl;
}

D – RLE Moving

    还没补。

E – Yacht

    还没补。

F – Erase between X and Y

算法：

    模拟，链表。

思路：

    模板。

关键代码：

int head, e[N], ne[N], idx = 1;
int val[N];

void init()
{
    head = idx;
    e[idx] = 0;
    val[0] = idx;
    ne[idx++] = -1;
}

void add(int x, int i)
{
    e[idx] = i;
    val[i] = idx;
    ne[idx] = ne[val[x]];
    ne[val[x]] = idx++;
}

ll erase(int x, int y)
{
    if (x == y)
        return 0;

    int i = ne[val[x]];
    int j = ne[val[y]];
    bool ok1 = 0, ok2 = 0;

    while (i != -1 || j != -1)
    {
        if (i != -1)
        {
            if (e[i] == y)
            {
                ok1 = true;
                break;
            }
            i = ne[i];
        }
        if (j != -1)
        {
            if (e[j] == x)
            {
                ok2 = true;
                break;
            }
            j = ne[j];
        }
    }

    ll sum = 0;

    if (ok1)
    {
        int en = val[y];
        for (int i = ne[val[x]]; i != en; i = ne[i])
            sum += e[i];
        ne[val[x]] = val[y];
    }
    else
    {
        int en = val[x];
        for (int i = ne[val[y]]; i != en; i = ne[i])
            sum += e[i];
        ne[val[y]] = val[x];
    }
    return sum;
}

void solve()
{
    init();

    int Q;
    cin >> Q;

    for (int i = 1; i <= Q; ++i)
    {
        int op, x, y;
        cin >> op;

        if (op == 1)
        {
            cin >> x;
            add(x, i);
        }
        else
        {
            cin >> x >> y;
            cout << erase(x, y) << endl;
        }
    }
}

G – Increase to make it Increasing

    还没补。