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

A – Doors in the Center

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;

    if (n & 1)
    {
        cout << string(n / 2, '-');
        cout << '=';
        cout << string(n / 2, '-') << endl;
    }
    else
    {
        cout << string((n - 1) / 2, '-');
        cout << '=';
        cout << '=';
        cout << string((n - 1) / 2, '-') << endl;
    }
}

B – Full House 3

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    map<int, int> m;
    for (int i = 0; i < 7; ++i)
    {
        int x;
        cin >> x;
        ++m[x];
    }

    int cnt1 = 0, cnt2 = 0;
    for (auto [_, x] : m)
    {
        if (x >= 3)
            ++cnt1;
        else if (x >= 2)
            ++cnt2;
    }

    if (cnt1 >= 2 || (cnt1 && cnt2))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

C – Uniqueness

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    map<int, vector<int>, greater<>> m;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        m[x].push_back(i);
    }

    ll ans = -2;
    for (auto [x, v] : m)
    {
        if (v.size() == 1 && ans == -2)
            ans = v.back();
    }

    cout << ans + 1 << endl;
}

D – Bonfire

算法：

    思维，前缀和。

思路：

    对于 \(i\)，只要存在一个 \(j\) 使得 \(s[i \text{ ~ } j]\) 移动到 \((R, C)\) 点，那么这一时刻 \(s[i] =\) '1'。

    将 \(N、W、S、E\) 转换成二元组前缀和，此时就将问题转换为了寻找一段区间其和为 \((R, C)\)。

    哈希表 + 前缀和解决即可。

关键代码：

void miyan()
{
    int n, x, y;
    string s;
    cin >> n >> x >> y >> s;

    s = ' ' + s;

    vector<pii> pre(n, {0, 0});
    for (int i = 1; i <= n; ++i)
    {
        pre[i] = pre[i - 1];
        if (s[i] == 'N')
            --pre[i].first;
        else if (s[i] == 'W')
            --pre[i].second;
        else if (s[i] == 'S')
            ++pre[i].first;
        else
            ++pre[i].second;
    }

    string ans;
    map<pii, int> m;
    for (int i = 1; i <= n; ++i)
    {
        ++m[pre[i - 1]];

        int l = pre[i].first - x;
        int r = pre[i].second - y;

        if (m.count({l, r}))
            ans.push_back('1');
        else
            ans.push_back('0');
    }

    cout << ans << endl;
}

E – Tree Game

算法：

    交互，二分图。

思路：

    不存在奇数环等价于是一个二分图。

    最后操作完后，图一定变为一个完全二分图，一个图其完全二分图最大边数 \(= cnt0 * cnt1\)，其中 \(cnt0\) 与 \(cnt1\) 为在二分图上两种不同的染色。

    那么对于一个图其可操作次数为 \(cnt0 * cnt1 – (n – 1)\)，如果可操作奇数条边就选择先手，否者后手，每次输出一个不同染色并且不存在的边。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector st(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v;
        st[u][v] = 1;
        st[v][u] = 1;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> col(n + 1, 0);
    auto dfs = [&](auto &&self, int u, int f) -> void
    {
        for (auto v : g[u])
        {
            if (v == f)
                continue;

            col[v] = col[u] ^ 1;

            self(self, v, u);
        }
    };

    col[1] = 1;
    dfs(dfs, 1, 0);

    int cnt1 = accumulate(all(col), 0ll);
    int cnt0 = n - cnt1;

    int tot = cnt1 * cnt0 - n + 1;

    int u, v;
    if (tot & 1)
        cout << "First" << endl;
    else
    {
        cout << "Second" << endl;
        cin >> u >> v;
        st[u][v] = 1;
    }

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j)
                continue;

            if (!st[i][j] && !st[j][i] && col[i] != col[j])
            {
                cout << i << ' ' << j << endl;
                st[i][j] = st[j][i] = 1;
                cin >> u >> v;
                st[u][v] = st[v][u] = 1;
            }
        }
    }
}

F – ABCBA

算法：

    \(manacher\)。

思路：

    板子。

关键代码：

vector<int> manacher(string ss)
{
    int m = ss.size();
    vector<int> p(m, 0);
    int c = 0, r = 0;
    for (int i = 0; i < m; ++i)
    {
        int len = r > i ? min(p[2 * c - i], r - i) : 1;

        while (i + len < m && i - len >= 0 && ss[i + len] == ss[i - len])
            ++len;

        if (i + len > r)
        {
            r = i + len;
            c = i;
        }

        p[i] = len;
    }

    return p;
}

void miyan()
{
    string s;
    cin >> s;

    int n = s.size();
    string ss;
    ss.push_back('#');
    for (int i = 0; i < n; ++i)
    {
        ss.push_back(s[i]);
        ss.push_back('#');
    }

    auto p = manacher(ss);

    int m = p.size();
    ll maxx = 1;
    for (int i = 0; i < m; ++i)
    {
        if (i + p[i] == m)
            maxx = max(maxx, p[i] - 1ll);
    }

    cout << s;
    for (int i = n - maxx - 1; i >= 0; --i)
        cout << s[i];
    cout << endl;
}

G – Not Only Tree Game

    还没补。