链接：https://codeforces.com/contest/2131

A. Lever

算法：

    思维。

思路：

    无。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 10), b(n + 10);
    cin >> a >> b;

    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] > b[i])
            ans += a[i] - b[i];
    }

    cout << ans + 1 << endl;
}

B. Alternating Series

算法：

    构造。

思路：

    无。

关键代码：

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

    if (n & 1)
    {
        for (int i = 1; i <= n - 1; i += 2)
            cout << -1 << ' ' << 3 << ' ';
        cout << -1 << endl;

        return;
    }

    for (int i = 1; i <= n - 2; i += 2)
    {
        cout << -1 << ' ' << 3 << ' ';
    }
    cout << -1 << ' ' << 2 << endl;
}

C. Make it Equal

算法：

    模拟。

思路：

    仔细分析操作规则会发现，其实我们只需要关注 第二种操作 \(|x – k|\)（第一种操作 \(x + k\) 可以通过多次第二种操作实现）。

    如果想要将一个数字 \(x\) 转换成另一个数字 \(y\)，它们必须满足以下两个条件之一：

• “对称”同余关系： \(k – x \equiv y \pmod{k}\)
• 同余关系：\(x \equiv y \pmod{k}\)

    换句话说，模 \(k\) 意义下：

• 余数为 \(r\) 的数
• 余数为 \(k – r\) 的数

    它们可以互相转换。

    因此，只需将每个元素修改为：

\(\min(x \bmod k, \; k – (x \bmod k))\)

    再对两个数组排序，判断受否相等即可。

关键代码：

void solve()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> s(n), t(n);

    for (int i = 0; i < n; ++i)
    {
        cin >> s[i];
        ll x = s[i] % k;
        s[i] = min(x, k - x);
    }
    for (int i = 0; i < n; ++i)
    {
        cin >> t[i];
        ll x = t[i] % k;
        t[i] = min(x, k - x);
    }

    ranges::sort(s);
    ranges::sort(t);

    cout << (s == t ? "YES" : "NO") << endl;
}

D. Arboris Contractio

算法：

    贪心，图。

思路：

    特判: 只有两个节点时不需要操作。

    可以发现最优目标是把树变成“菊花图”（所有点都连到同一个中心），此时直径为 \(2\)。

    令 \(cnt\) 为树中叶子（度为 \(1\) 的点）总数；对每个顶点 \(u\)，令 \(cur(u)\) 为与 \(u\) 直接相连的叶子数。

    若选 \(u\) 作为中心，至少需要把剩下的叶子都搬到 \(u\)，操作次数为 \(cnt − cur(u)\)；

    显然可以做到，所以这是可达的下界。

    在所有 \(u\) 中取最小：答案 \(= cnt − max_cur\)。

    只需统计叶子总数 \(cnt\)，对每个节点统计其相邻的叶子数 \(cur(u)\)，对答案取最小值即可。。

关键代码：

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

    if (n == 2)
    {
        cout << 0 << endl;
        return;
    }

    ll cnt = 0;
    for (int i = 1; i <= n; ++i)
        cnt += (g[i].size() == 1);

    ll ans = cnt - 1;
    for (int u = 1; u <= n; ++u)
    {
        ll cur = 0;
        for (auto v : g[u])
            cur += (g[v].size() == 1);

        ans = min(ans, cnt - cur);
    }

    cout << ans << endl;
}

E. Adjacent XOR

算法：

    贪心，思维。

思路：

    先注意最后一个元素必须满足: \(a_n = b_n\)​ 因为它无法被修改。

    然后从 \(i = n-1\) 倒序遍历，想让 \(a[i]\) 变成 \(b[i]\)，只需满足以下任一条件：

1. \(a[i] = b[i]\)
2. \(a[i] \oplus a[i+1] = b[i]\)
3. \(a[i] \oplus b[i+1] = b[i]\)

    第三条是因为顺序可以任意，\(a[i+1]\) 可能已被改成 \(b[i+1]\)，所以用它来异或判断。

    若所有位置都满足上述条件之一，输出 \(YES\)，否则 \(NO\)。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];

    if (a[n - 1] != b[n - 1])
    {
        cout << "NO" << endl;
        return;
    }

    for (int i = n - 2; ~i; --i)
    {
        if (a[i] == b[i] || (a[i] ^ a[i + 1]) == b[i] || (a[i] ^ b[i + 1]) == b[i])
            continue;

        cout << "NO" << endl;
        return;
    }

    cout << "YES" << endl;
}

F. Unjust Binary Life

算法：

    思维，前缀和，推公式，贪心，数学。

思路：

定义：

• \(cnta1(x)\): 字符串 \(a\) 中前 \(x\) 个元素 \(1\) 的个数
• \(cnta0(x)\): 字符串 \(a\) 中前 \(x\) 个元素 \(0\) 的个数
• \(cntb1(x)\): 字符串 \(b\) 中前 \(x\) 个元素 \(1\) 的个数
• \(cntb0(x)\): 字符串 \(b\) 中前 \(x\) 个元素 \(0\) 的个数

规律：

1. 从 \((1,1)\) 到 \((x,y)\) 的简单路径，一定会访问：
   • 所有行编号 \(1, 2, \dots, x\)
   • 所有列编号 \(1, 2, \dots, y\)
2. 如果存在一条路径从 \((1,1)\) 到 \((x,y)\)，且路径上所有格子值都是 \(0\)，那么：
   • \(a[1], a[2], \dots, a[x]\)
   • \(b[1], b[2], \dots, b[y]\)

    必须全部相等（要么全 \(0\)，要么全 \(1\)）

    证明（归纳法）：

1. \((1,1)\) 为 \(\Rightarrow a_1 = b_1 = v（v \in \{0,1\}）\)。
2. 若当前格为 \((p,q)\)，值为 \(0\)，则 \(a_p = b_q = v\)。
   • 向右走到 \((p,q+1)\) 为 \(\Rightarrow a_p = b_{q+1} = v\)。
   • 向下走到 \((p+1,q)\) 为 \(\Rightarrow a_{p+1} = b_q = v\)。
3. 路径会触及所有行 \(1..x\) 和列 \(1..y\)，因此这些行列对应的 \(a_i\)​ 与 \(b_j\)​ 必须全部等于同一个 \(v\)。

    直观理解：一旦起点是 \(0\)，这条路径就会“强制”整块区域的行列全部同值。

---

推导：

    根据规律 \(2\)，要让路径全 \(0\)，有两种方式：

1. 把 \(a[1..x]\) 和 \(b[1..y]\) 都变成 \(0\)
   操作次数：\(\text{cnta1}(x) + \text{cntb1}(y)\)
2. 把 \(a[1..x]\) 和 \(b[1..y]\) 都变成 \(1\)
   操作次数：\(\text{cnta1}(x)) + (y – \text{cntb1}(y))\)

    于是：

\(f(x, y) = \min\big(\text{cnta1}(x) + \text{cntb1}(y),\; \text{cnta0}(x) + \text{cntb0}(y)\big)\)

    利用最小值恒等式，可将式子转换成：

\(\frac{(\text{cnta1}(x) + \text{cntb1}(y)) + (\text{cnta0}(x) + \text{cntb0}(y)) – \left|(\text{cnta1}(x) + \text{cntb1}(y)) – (\text{cnta0}(x) + \text{cntb0}(y))\right|}{2}\)

    对于分子左半部分可等价转换为：

\((\text{cnta1}(x) + \text{cntb1}(y)) + (\text{cnta0}(x) + \text{cntb0}(y)) = x + y\)

    而分子右半部分可变形为：

\( \left|\text{cnta1}(x) + \text{cntb1}(y) – \text{cnta0}(x) – \text{cntb0}(y)\right| \)

\(\Rightarrow \left|(\text{cnta1}(x) – \text{cnta0}(x)) + (\text{cntb1}(y) – \text{cntb0}(y))\right|\)

    可以发现可以提出来一个减号，将其转换为经典的数组两两绝对值差问题，既：

\(\left|(\text{cnta1}(x) – \text{cnta0}(x)) – (\text{cntb0}(y) – \text{cntb1}(y))\right|\)

    此时，令：

• \(sa[x] = \text{cnta1}(x) – \text{cnta0}(x)\)
• \(sb[y] = \text{cntb0}(y) – \text{cntb1}(y)\)

    对于：

• \(sa[x]\): 可以看出这是字符串 \(a\) 前 \(x\) 个字符中 \(1\) 的个数与 \(0\) 的个数的差值
• \(sb[y]\): 可以看出这是字符串 \(b\) 前 \(y\) 个字符中 \(0\) 的个数与 \(1\) 的个数的差值

    于是：

\(f(x, y) = \frac{(x+y) – |sa[x] – sb[y]|}{2}\)

    令:

\(s_1 = x + y\)

\(s_2 = |sa[x] – sb[y]|\)

    所以：

\(f(x, y) = \frac{s_1 – s_2}{2}\)

    那么最终答案就为：

\(\text{Ans} = \sum_{x=1}^n \sum_{y=1}^n f(x, y) = \frac{\sum_{x=1}^n \sum_{y=1}^n s_1 – \sum_{x=1}^n \sum_{y=1}^n s_2}{2}\)

---

求 S₁：

\(\sum_{x=1}^n \sum_{y=1}^n (x+y) = \sum_{x=1}^n \big(n \cdot x + \frac{n(n+1)}{2}\big) = n \cdot \frac{n(n+1)}{2} + n \cdot \frac{n(n+1)}{2} = n^2 (n+1)\)

---

求 S₂：

    已知：

• \(sa[x]\): 可以看出这是字符串 \(a\) 前 \(x\) 个字符中 \(1\) 的个数与 \(0\) 的个数的差值
• \(sb[y]\): 可以看出这是字符串 \(b\) 前 \(y\) 个字符中 \(0\) 的个数与 \(1\) 的个数的差值

    将字符串 a 中的字符 ‘\(1\)’ 赋值为 \(+1\)，字符 ‘\(0\)’ 赋值为 \(-1\)，
    构造前缀和数组 \(sa：\)

\(sa[i] = sa[i-1] + (a[i] == ‘1’ ? 1 : -1)\)

    将字符串 b 中的字符 ‘\(0\)’ 赋值为 \(+1\)，字符 ‘\(1\)’ 赋值为 \(-1\)，
    构造前缀和数组 \(sb：\)

\(sb[i] = sb[i-1] + (a[i] == ‘0’ ? 1 : -1)\)

    此时，就可在 \(O(1)\) 的时间内求出 \(sa[x] – sb[y]\)

    剩下的就是求任意两两 \((x, y)\) 。直接双循环是 \(O(n^2)\)，不可行。
    我们换个角度：对每个 \(v=sa[i]\)，求它与所有 \(sb[j]\) 的绝对差之和。

    已排序前缀和法：

• 将 \(sa,sb\) 排序，记为 \(t_1 \le t_2 \le \dots \le t_n\)
• 前缀和数组：\(prefix[k] = t_1 + \dots + t_k\)

    对固定 \(v\)：

• 双指针找到 \(cnt=\) 满足 \(t_j < v\) 的个数
• 左边和 \(L = prefix[cnt]\)，右边和 \(R = prefix[n] – L\)
• 绝对差之和公式：

\(\sum_{j=1}^n |v – t_j| = v \cdot cnt – L + R – v \cdot (n – cnt) = (2cnt – n) \cdot v – L + R\)

    这样每个 \(v\) 可 \(O(1)\) 求，整体\(O(n)\)。

关键代码：

void solve()
{
    ll n;
    string a, b;
    cin >> n >> a >> b;

    a = ' ' + a, b = ' ' + b;

    vector<ll> sa(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        sa[i] = sa[i - 1] + (a[i] == '1' ? 1 : -1);

    vector<ll> sb(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        sb[i] = sb[i - 1] + (b[i] == '0' ? 1 : -1);

    sort(sa.begin() + 1, sa.begin() + 1 + n);
    sort(sb.begin() + 1, sb.begin() + 1 + n);

    ll ans = n * n * (n + 1);
    ll l = 0, r = accumulate(sb.begin() + 1, sb.begin() + 1 + n, 0ll);
    for (int i = 1, j = 1; i <= n; ++i)
    {
        while (j <= n && sb[j] < sa[i])
        {
            l += sb[j];
            r -= sb[j];
            ++j;
        }

        ans -= (2ll * (j - 1) - n) * sa[i] + r - l;
    }

    cout << ans / 2 << endl;
}

G. Wafu!

    还没补。