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

A – Triple Four

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    ll cnt = 1;
    for (int i = 1; i < n; ++i)
    {
        if (a[i] == a[i - 1])
            ++cnt;
        else
            cnt = 1;

        if (cnt >= 3)
        {
            cout << "Yes" << endl;
            return;
        }
    }

    cout << "No" << endl;
}

B – Card Pile

算法：

    模拟。

思路：

    无。

关键代码：

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

    vector<int> a(100, 0);
    while (Q--)
    {
        int op, x;
        cin >> op;
        if (op == 1)
        {
            cin >> x;
            a.push_back(x);
        }
        else
        {
            cout << a.back() << endl;
            a.pop_back();
        }
    }
}

C – Buy Balls

算法：

    贪心。

思路：

    无。

关键代码：

void miyan()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    ranges::sort(a, greater<>());
    ranges::sort(b, greater<>());

    int cnta = 0;
    ll sum = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] >= 0)
        {
            sum += a[i];
            ++cnta;
        }
    }

    int cntb = 0;
    for (int i = 0; i < min(m, cnta); ++i)
    {
        if (b[i] > 0)
        {
            sum += b[i];
            ++cntb;
        }
    }

    while (cnta < n && cntb < m)
    {
        if (a[cnta] + b[cntb] >= 0)
            sum += a[cnta++] + b[cntb++];
        else
            break;
    }

    cout << sum << endl;
}

D – Minimum XOR Path

算法：

    暴搜。

思路：

    \(n = 10\)，直接搜索所有可能。

关键代码：

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

    ll ans = LLONG_MAX;
    vector<int> st(n + 1, 0);
    auto dfs = [&](auto &&self, int u, ll now) -> void
    {
        if (u == n)
        {
            ans = min(ans, now);
            return;
        }

        for (auto [v, w] : g[u])
        {
            if (st[v])
                continue;

            st[v] = 1;
            self(self, v, now ^ w);
            st[v] = 0;
        }
    };

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

    cout << ans << endl;
}

E – Min of Restricted Sum

算法：

    模拟。

思路：

    异或，按位考虑。

    对于 \(x\)，\(y\)，\(z\) 可以看成 \(x\) 点到 \(u\) 点连了一条边权为 \(z\) 的边。

    那么整个题目就可看做存在一些联通块。

    每个联通块都是独立的。

    在一个联通块中，知道其中一个点的值，那么其他所有点的值都可以求出。

    先考虑什么时候无解：

• 设起点为 \(r\)，起点到 \(u\) 有两条路径，既 \(r – v_1 – v_2 – u\) 和 \(r – v_3 – v_4 – v_5 – u\)。
• 由第一条路径可得 \(a_u = a_s \oplus W_{r,v_1} \oplus W_{v_1,v_2} \oplus W_{v_2,u}\)。
• 由第二条路径可得 \(a_u = a_s \oplus W_{r,v_3} \oplus W_{v_3,v_4} \oplus W_{v_4,v_5} \oplus W_{v_5,u}\)。
• 此时两条路径得到的值必须相等，否者无解。

    延申到多条路径上也是同理。

    记录第一次到达 \(u\) 点时边权异或和，后续再到达时，如果不相等就无解。

    定义 \(val_u\) 为从当前联通块的根节点到达 \(u\) 点的边权异或和。

    考虑 \(Σa_i\) 最小：

        按位考虑，对于当前联通块的第 \(i\) 位，求出块中所有节点的 \(val\) 当前位 \(1\) 的个数和 \(0\) 的个数，如果 \(1\) 的个数大于 \(0\) 的个数就需要将根节点当前为转换为 \(1\)，此时 \(0\) 与 \(1\) 就互相转换；反之取 \(0\)。

    最后每个节点的值就等于 \(root \oplus val_u*\)。

    \(*\)证明：

        设当前联通块为一条简单路径，\(r – v – u\)。

        由于 \(ans_v = W_{r,v} \oplus ans_r\)，\(ans_u = W_{v,u} \oplus ans_v\)，那么 \(ans_u = W_{v,u} \oplus W_{r,v} \oplus ans_r\)，因为 \(val_u = W_{v,u} \oplus W_{r,v}\)，所有 \(ans_u = val_u \oplus ans_r\)。

关键代码：

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

    vector<int> ans(n + 1, 0);
    vector<int> val(n + 1, 0);
    vector<int> st(n + 1, 0);
    vector<int> nw;
    auto dfs = [&](auto &&self, int u) -> void
    {
        st[u] = 1;
        nw.push_back(u);

        for (auto [v, w] : g[u])
        {
            if (st[v])
            {
                if (val[v] != (val[u] ^ w))
                {
                    cout << -1 << endl;
                    exit(0);
                }
                continue;
            }
            val[v] = val[u] ^ w;

            self(self, v);
        }
    };

    for (int i = 1; i <= n; ++i)
    {
        if (st[i])
            continue;

        dfs(dfs, i);

        int root = 0;
        for (int j = 30; j >= 0; --j)
        {
            int cnt0 = 0, cnt1 = 0;
            for (auto u : nw)
            {
                if (val[u] & (1 << j))
                    ++cnt1;
                else
                    ++cnt0;
            }
            if (cnt0 < cnt1)
                root |= 1 << j;
        }

        for (auto u : nw)
            ans[u] = val[u] ^ root;

        nw.clear();
    }

    for (int i = 1; i <= n; ++i)
        cout << ans[i] << ' ';
    cout << endl;
}

F – Rotated Inversions

算法：

    逆序对，贪心，树状数组。

思路：

    考虑没有模数的时候，不管怎么加，数组中的逆序对数量是不变的。

    考虑模数。

    对于当前数组，对于每个元素都加上一个 \(1\) 后，只有当 \(a_i = M – 1\) 时会改变逆序对的值，其值会直接变为 \(0\)。

    \(a_i\) 在操作先后对逆序对造成影响为：

• \(a_i\) 在操作之前为 \(M – 1\)，其会与后面的所有非 \(M – 1\) 值构成逆序对，个数为 \(n – i + 1 – suf_{M – 1}\)。
• \(a_i\) 在操作后，其值变为 \(0\)，\(i\) 位置前面的所有非 \(0\) 值的位置都可当做逆序对第二元素，新增 \(i – 1 – pre_{M – 1}\) 对。

    依次处理 \(k = 0,1,2,……,M – 1\)，对应回当前的答案就为直接继承 \(k – 1\) 的答案，每次处理数组中值为 \(M – k\) 的元素，将其影响运算至答案中即可。

关键代码：

int n, m;
vector<int> tr;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i <= m; i += lowbit(i))
        tr[i] += v;
}

ll query(int x)
{
    ll ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += tr[i];
    return ans;
}

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

    tr.resize(m + 1, 0);
    map<int, vector<int>> hash;
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        ++x;
        ans += query(m) - query(x);
        add(x, 1);
        hash[m - x + 1].push_back(i + 1);
    }

    for (int i = 1; i <= m; ++i)
    {
        cout << ans << endl;

        ll cnt = 0;
        for (auto x : hash[i])
        {
            ans = ans - (n - x - (hash[i].size() - cnt - 1)) + (x - 1 - cnt);
            ++cnt;
        }
    }
}

G – Flip Row or Col

    还没补。