351

A - The bottom of the ninth

高桥队和青木队正在进行一场棒球比赛，高桥队是第一棒。
目前，比赛已进行到第九局上半，第九局下半即将开始。

高桥队在 $i$ （第三局） $(1 \leq i \leq 9)$ 上半场得到了 $A_{i}$ 分，青木队在 $j$ （第三局） $(1 \leq j \leq 8)$ 下半场得到了 $B_{j}$ 分。
第九局上半结束时，高桥队的得分不低于青木队的得分。
求青木队在第九局下半至少需要得到多少分才能赢得比赛。

在这里，如果比赛在第九局下半结束时打成平手，结果就是平局。因此，青木队要想获胜，就必须在第九局下半结束时比高桥队严格多得一分。
高桥队在任何时候的得分都是截至该点的上局总得分，而青木队的得分则是下局的总得分。

void solve() {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1;i <= 9;i++) {
        int x;cin >> x;cnt1 += x;
    }
    for (int i = 1;i <= 8;i++) {
        int x;cin >> x;cnt2 += x;
    }
    cout << cnt1 - cnt2 + 1 << '\n';
}

B - Spot the Difference

给你两个网格，每个网格有 $N$ 行和 $N$ 列，分别称为网格 $A$ 和网格 $B$ 。
网格中的每个单元格都包含一个小写英文字母。
网格 $A$ 的第 $i$ 行和第 $j$ 列的字符是 $A_{i, j}$ 。
位于网格 $B$ 的 $i$ 行和 $j$ 列的字符是 $B_{i, j}$ 。

这两个网格正好有一个单元格不同。也就是说，存在一对不大于 $N$ 的正整数 $(i, j)$ ，使得 $A_{i, j} \neq B_{i, j}$ 。求这个 $(i, j)$ .

char s1[110][110], s2[110][110];
void solve() {
    int n;cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s1[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> s2[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (s1[i][j] != s2[i][j]) {
                cout << i << " " << j << '\n';
            }
        }
    }
}

C - Merge the balls

你有一个空序列和 $N$ 个球。球 $i$ -th 球 $(1 \leq i \leq N)$ 的大小是 $2^{A_{i}}$ 。

你将进行 $N$ 次运算。
在 $i$ /th 操作中，你将 $i$ /th 球添加到序列的右端，然后重复下面的步骤：

如果序列中只有一个或更少的球，则结束操作。
如果序列中最右边的球和第二个最右边的球大小***不同，结束操作。
1. 如果序列中最右边的球和最右边的第二个球的大小**相同，则移除这两个球，并在序列的右端添加一个新球，其大小等于移除的两个球的大小之和。然后回到步骤 1，重复上述过程。

计算经过 $N$ 次操作后序列中剩余的球的个数。

void solve() {
    int n;cin >> n;vector<int> a;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        a.push_back(x);
        if (a.size() <= 1) continue;
        while (a.size() >= 2 && a[a.size() - 1] == a[a.size() - 2]) {
            a.erase(a.begin() + a.size() - 1);
            a[a.size() - 1]++;
        }
    }
    cout << a.size() << '\n';
}

D - Grid and Magnet

有一个行数为 $H$ 列数为 $W$ 的网格。有些单元格（可能为零）包含磁铁。
网格的状态由长度为 $W$ 的 $H$ 个字符串 $S_{1}, S_{2}, \dots, S_{H}$ 表示。如果 $S_{i}$ 的 $j$ 个字符是 "#"，则表示从上往下 $i$ 行、从左往上 $j$ 列的单元格中有磁铁；如果是"."，则表示单元格是空的。

身穿铁甲的高桥可以在网格中做如下移动：

如果与当前单元格垂直或水平相邻的任何一个单元格中含有磁铁，他就不能移动。
否则，他可以移动到任何一个垂直或水平相邻的单元格。
但是，他不能离开网格。

对于每个没有磁铁的单元格，将其自由度定义为他从该单元格重复移动所能到达的单元格数。求网格中所有没有磁铁的单元格的最大自由度。

这里，在自由度的定义中，"他可以通过重复移动到达的单元格 "指的是从初始单元格通过一定的移动序列（可能是零移动）可以到达的单元格。不一定要有一个移动序列能从初始单元格开始访问所有这些可到达的单元格。具体来说，每个单元格本身（没有磁铁）总是包含在从该单元格可到达的单元格中。

这个题目在赛时 cnt 数组开小了 $\dots$ 没有报 RE，却是 WA

总体思路较为简单，将 # 周围的标记为 1，将走过的路标记为 2，这样使得每次进入一个连通块时只访问一次标记为 1/2 的，这样就能算出在每个连通块内能走的路程。

char s[1010][1010];
int vis[1010][1010], dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void solve() {
    int n, m;cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> s[i][j];
            if (s[i][j] == '#') {
                if (i - 1 >= 1)vis[i - 1][j] = 1;
                if (i + 1 <= n) vis[i + 1][j] = 1;
                if (j + 1 <= m) vis[i][j + 1] = 1;
                if (j - 1 >= 1) vis[i][j - 1] = 1;
            }
        }
    }
    int k = 0, ans = 1;
    auto bfs = [&](int sx, int sy) {
        map<pair<int, int>, int>once;
        queue<pair<int, int>>q;q.push({sx,sy});vis[sx][sy] = 2;k++;
        while (q.size()) {
            auto [x, y] = q.front();q.pop();
            for (int i = 0;i < 4;i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a < 1 || b<1 || a>n || b>m || vis[a][b] == 2 || s[a][b] == '#')continue;
                if (vis[a][b] == 1) {
                    if (!once.count({a,b})) {
                        once[{a, b}] = 1; k++;
                    }
                    continue;
                }
                q.push({a,b});vis[a][b] = 2;k++;
            }
        }
        };
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (s[i][j] == '.' && !vis[i][j]) {
                k = 0;
                bfs(i, j);
                ans = max(ans, k);
            }
        }
    }
    cout << ans << '\n';
}

E - Jump Distance Sum

在坐标平面上，有 $N$ 个点 $P_{1}, P_{2}, \dots, P_{N}$ ，其中点 $P_{i}$ 的坐标为 $(X_{i}, Y_{i})$ 。
两点 $A$ 与 $B$ 之间的距离 $dist (A, B)$ 定义如下：

一只兔子最初位于点 $A$ 。
位置为 $(x, y)$ 的兔子可以一次跳到 $(x + 1, y + 1)$ 、 $(x + 1, y - 1)$ 、 $(x - 1, y + 1)$ 或 $(x - 1, y - 1)$ 。
$dist (A, B)$ 被定义为从 $A$ 点跳到 $B$ 点所需的最少跳跃次数。
如果经过任意次数的跳跃都无法从点 $A$ 到达点 $B$ ，则设为 $dist (A, B) = 0$ 。

计算 $$\displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j)$$

Solution

类似题目：
P3964 松鼠聚会

将切比雪夫距离转化为曼哈顿距离： $max (∣ x_{1} - x_{2} ∣, ∣ y_{1} - y_{2} ∣) ⟹ ∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$

Chebyshev \to Manhattan

首先，通过绕原点旋转 $45$ 度并按 $\sqrt{2}$ 倍缩放的变换，原点为 $(X, Y)$ 的点移动到 $(X + Y, X - Y)$ 。设变换后点的坐标为 $(x_{i}, y_{i})$ ，则有 $x_{i} = X_{i} + Y_{i}$ 和 $y_{i} = X_{i} - Y_{i}$ 。

接下来，我们考虑距离 $dist (A, B)$ 的定义如何改变。在原始定义中，兔子可以从 $(X, Y)$ 跳到 $(X + 1, Y + 1)$ 、 $(X + 1, Y - 1)$ 、 $(X - 1, Y + 1)$ 和 $(X - 1, Y - 1)$ ；因此，在变换后，它可以从 $(X + Y, X - Y)$ 跳到 $(X + Y + 2, X - Y)$ 、 $(X + Y, X - Y + 2)$ 、 $(X + Y, X - Y - 2)$ 和 $(X + Y - 2, X - Y)$ 。将 $x = X + Y$ 和 $y = X - Y$ 代入，可以得到它可以从 $(x, y)$ 跳到 $(x + 2, y)$ 、 $(x, y + 2)$ 、 $(x, y - 2)$ 和 $(x - 2, y)$ 。从而，从 $A$ 到 $B$ 的最小跳数就是 $dist (A, B)$ 的定义（如果无法到达则为 $0$ ）。

接下来，我们考虑经过变换后的问题。也就是说，我们令 $P_{i} = (x_{i}, y_{i})$ ，定义 $dist (A, B)$ ，并考虑 $\sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} dist (P_{i}, P_{j})$ ，其中 $dist (A, B)$ 的定义如上所述。显然，这给出的答案与原问题相同。

我们进一步考虑 $A = (x_{1}, y_{1})$ 、 $B = (x_{2}, y_{2})$ 的情况。如果 $x_{1} ≢ x_{2} (\mod 2)$ 或 $y_{1} ≢ y_{2} (\mod 2)$ ，则兔子无法从 $A$ 到 $B$ ，因此 $dist (A, B) = 0$ 。否则，它将恰好是曼哈顿距离的一半，即 $\frac{1}{2} (| x_{1} - x_{2} | + | y_{1} - y_{2} |)$ 。

旋转 45° 并放大 $\sqrt{2}$ 倍后转化为曼哈顿距离：
由 $x_{i} = X_{i} + Y_{i}$ 和 $y_{i} = X_{i} - Y_{i}$ 可以推出 $x_{i}, y_{i}$ 是同奇偶性的

$N$ 个点可以被分为两组： $x_{i}$ 和 $y_{i}$ 都是偶数，或者 $x_{i}$ 和 $y_{i}$ 都是奇数。对于属于不同组的两点 $A$ 和 $B$ ， $dist (A, B) = 0$ ；对于属于同一组的两个不同点， $dist (A, B) = \frac{1}{2} (| x_{1} - x_{2} | + | y_{1} - y_{2} |)$ 。

设 $S$ 为其中 $x_{i}, y_{i}$ 都为偶数或奇数的集合，由于该题是两两计算，先后计算并不影响结果，所以可以先降序排列简化运算：

对于 $x_{i}$ ： ( $y_{i}$ 同理)

\frac{1}{2} \sum_{i = 1}^{∣ S ∣} \sum_{j = i + 1}^{∣ S ∣} ∣ x_{j} - x_{i} ∣= \frac{1}{2} \sum_{i = 1}^{∣ S ∣} \sum_{j = i + 1}^{∣ S ∣} (x_{i} - x_{j}) = \frac{1}{2} \sum_{i = 1}^{∣ S ∣} (| S | - 1 - 2 i)

#define int long long
void solve() {
    int n;cin >> n;vector<int>  a[4];
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;
        if ((x + y) % 2 == 0) {
            a[0].push_back(x + y);a[1].push_back(x - y);
        } else {
            a[2].push_back(x + y);a[3].push_back(x - y);
        }
    }
    int ans = 0;
    for (int i = 0;i < 4;i++) {
        sort(a[i].rbegin(), a[i].rend());
        for (int j = 0;j < a[i].size();j++) {
            ans += a[i][j] * (a[i].size() - 1 - 2 * j);
        }
    }
    cout << ans / 2 << '\n';
}

F - Double Sum

给你一个整数序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 。
请计算以下表达式：

\sum_{i = 1}^{N} \sum_{j = i + 1}^{N} max (A_{j} - A_{i}, 0)

约束条件保证答案小于 $2^{63}$ 。

Solution

树状数组/线段树/扫描线

树状数组求 $k_{t h}$ 小的元素：牛客

官方题解

在这里，对于一个固定的 $i$ ，对双重求和的贡献可以表示为

\begin{aligned} \sum_{i < j} max (A_{j} - A_{i}, 0) \\ = \sum_{i < j, A_{i} \leq A_{j}} A_{j} - A_{i} \\ = (对于 i < j 且 A_{i} \leq A_{j} 的 A_{j} 的和) \\ - (对于 i < j 且 A_{i} \leq A_{j} 的 A_{j} 的个数) \times A_{i} . \end{aligned}

利用这个事实，可以通过扫描线算法来解决这个问题，方法如下。

准备一个管理以下两个值的数据结构：
- 支持两种查询的多重集 $S_{0}$ ，检索不小于 $x$ 的元素数。
- 支持两种查询的多重集 $S_{1}$ ，检索不小于 $x$ 的元素之和。
同样，准备一个变量 $ans$ 来存储答案。最初，让 $ans = 0$ 。
对于每个 $i = N, N - 1, \dots, 2, 1$ ，执行以下操作。
- 用 $x = A_{i}$ 对 $S_{0}$ 进行查询，并将响应值命名为 $c$ 。
- 用 $x = A_{i}$ 对 $S_{1}$ 进行查询，并将响应值命名为 $s$ 。
- 将 $s - c \times A_{i}$ 加到 $ans$ 中。
- 将 $A_{i}$ 插入到 $S_{0}$ 和 $S_{1}$ 中。
打印出 $ans$ 的结果值。

$S_{0}$ 和 $S_{1}$ 可以通过树状数组和坐标压缩来实现；它们可以在 $O (\log N)$ 的时间内处理每个查询。

(待更 $\dots$ )

class FenwickTree {
private:
    vector<long long> bit;  // 1-indexed
    int n;

public:
    FenwickTree(int n) {
        this->n = n;
        bit.assign(n + 1, 0);
    }

    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)add(i + 1, a[i]);
    }

    long long sum(int i) {
        long long ans = 0;
        while (i)ans += bit[i], i -= i & -i;
        return ans;
    }

    long long sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int i, int delta) {
        while (i <= n)bit[i] += delta, i += i & -i;
    }
};

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int& x : A) cin >> x;

    vector<int> B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    int M = B.size();

    FenwickTree sum0(M), sum1(M);
    long long ans = 0;
    for (int i = N - 1; i >= 0; --i) {
        int k = lower_bound(B.begin(), B.end(), A[i]) - B.begin() + 1;
        long long c = sum0.sum(k, M);
        long long s = sum1.sum(k, M);
        ans += s - c * A[i];
        sum0.add(k, 1);
        sum1.add(k, A[i]);
    }
    cout << ans << '\n';
}

G - Hash on Tree

给你一棵有根的树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。
顶点 $1$ 是根，顶点 $i$ 的父顶点 $(2 \leq i \leq N)$ 是顶点 $i$ 的父顶点。 $(2 \leq i \leq N)$ 是顶点 $p_{i}$ 的父节点。 $(p_{i} < i)$ .
此外，还有一个序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 。

有根树的哈希值计算如下：

按照 $n = N, N - 1, \dots, 2, 1$ 的顺序定义 $f (n)$ $(1 \leq n \leq N)$ 如下。
- 如果顶点 $n$ 是叶子，则 $f (n) = A_{n}$ 。
- 如果顶点 $n$ 不是叶子，则 $f (n) = A_{n} + \prod_{c \in C (n)} f (c)$ ，其中 $C (n)$ 是 $n$ 的子集。
有根树的哈希值为 $f (1) mod 998244353$ 。

按照给出的顺序处理 $Q$ 查询。
每个查询都提供了 $v$ 和 $x$ ，因此更新 $A_{v}$ 为 $x$ ，然后计算有根树的哈希值。

ABC 补了写作业，作业写完就“快速见识”DP，然后开始漫长的板刷CF