AtCoder Beginner Contest 398

2025-03-22

赛时只出了 ABCD 。

最难受的一集，F一直WA只有一个点。。我以为我就差一点就对了。但实际可能差得很远。刚才对拍了下才发现，而且是非常常见的数据。

E

不是哥们，怎么这么简单的。都不太敢相信（）。

\(n\) 很小，我们只需要去把每一对距离为奇数的且距离大于1点给找出来，我们只能在这些点上操作。

且一个操作是不会对其他操作产生影响的。所以看总的可操作次数是奇数还是偶数，决定先操作还是后操作。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1, vector<int>());
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> dep(n + 1);
    auto dfs = [&](auto &&self, int u, int pre) -> void
    {
        for (auto v : adj[u])
        {
            if (v == pre)
                continue;
            dep[v] = dep[u] + 1;
            self(self, v, u);
        }
    };
    set<pii> st;
    for (int i = 1; i <= n; i++)
    {
        dep = vector<int>(n + 1);
        dfs(dfs, i, 0);
        for (int j = 1; j <= n; j++)
        {
            if ((dep[j] & 1) && (dep[j] > 1))
            {
                if (i > j)
                    st.insert({j, i});
                else
                    st.insert({i, j});
            }
        }
    }
    if (st.size() % 2 == 1)
    {
        cout << "First" << endl;
        auto [x, y] = *st.begin();
        st.erase(st.begin());
        cout << x << " " << y << endl;
    }
    else
        cout << "Second" << endl;
    for (;;)
    {
        int x, y;
        cin >> x >> y;
        if (x == -1)
        {
            return;
        }
        if (x > y)
            swap(x, y);
        assert(st.size());
        st.erase({x, y});
        assert(st.size());
        x = (*st.begin()).first;
        y = (*st.begin()).second;
        cout << x << " " << y << endl;
        st.erase(st.begin());
    }
}

F

先来说下我的离谱想法。正确的明天再去思考。

最开始我是想能不能二分那个长度的。。然后样例没过才发觉不行。

然后又想，我先匹配 \(s_1\) 和 \(s_n\) 嘛，如果不匹配，那么就加一个字符到末尾去，这样 \(s_2\) 去匹配 \(s_n\) ，不行就再加一个在后面。。就是如果匹配不上，就把上几次匹配上的全当成不可匹配。。。

但是刚才发现 \(GGVG\) 这种就是很明显不行，我的方法会最开始能匹配，中间不行，然后长度 \(+3\) 。。。

void ChatGptDeepSeek()
{
    string s;
    cin >> s;
    int len = s.size(), lst = -1;
    for (int i = 0; i < len - i - 1 && i < s.size() && len - i - 1 < s.size(); i++)
    {
        if (s[i] != s[len - i - 1])
        {
            len += i - lst;
            lst = i;
        }
    }
    string t = s;
    while (t.size() < len)
        t += "a";
    for (int i = 0; i < len - i - 1; i++)
    {
        if (t[i] != t[len - i - 1])
            t[len - i - 1] = t[i];
    }
    cout << t << '\n';
}

起码知道了自己为什么错哈。。。正解 KMP 或 Manacher 。

KMP不太记得了，没用过几次。等会看看。

好好好，实际上我们可以把问题转换成寻找 \(s\) 的最长回文后缀的长度。这个问题可以用 KMP 求解。

如何求呢？

我们构造 \(s=s+'\#'+s\) ， 那么 \(s\) 的最长回文后缀即为最后一个 \(border\) 的值。

void ChatGptDeepSeek()
{
    string s;
    cin >> s;
    string t = s;
    int n = s.size();
    s = s + "#" + s;
    reverse(s.begin(), s.begin() + n);
    vector<int> p(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++)
    {
        int j = p[i - 1];
        while (j > 0 && s[i] != s[j])
            j = p[j - 1];
        p[i] = j;
        if (s[i] == s[j])
        {
            p[i]++;
        }
    }
    n += n - p.back();
    while (t.size() < n)
        t.push_back('@');
    for (int i = 0; i < n - i - 1; i++)
        if (t[i] != t[n - i - 1])
            t[n - i - 1] = t[i];
    cout << t << '\n';
}