ABC351(A-G)

其实前几场也做了，但是因为最近实验室太忙，就没有出题解...但是这场质量真的太高了！抽空把题解写了。

A - The bottom of the ninth ¶

题目大意

第一行输入 \(9\) 个数，第二行输入 \(8\) 个数，对两行的数字求和，问：第二行的数字之和至少要加多少才能比第一行的数字之和大？

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    int a = 0, x;
    for(int i = 0; i < 9; i++) 
    {
        cin >> x;
        a += x;
    }
    for(int i = 0; i < 8; i++) 
    {
        cin >> x;
        a -= x;
    }
    cout << max(a+1, 0);
    return 0;
}

B - Spot the Difference ¶

题目大意

给你两个 \(N \times M\) 的矩阵 \(A\) 和 \(B\)，这两个矩阵有且仅有一个位置的值不相同，找出这个位置

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<string> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(a[i][j] != b[i][j])
            {
                cout << i+1 << ' ' << j+1 << endl;
                return 0;
            }
    return 0;
}

C - Merge the balls ¶

题目大意

给你 \(N(1 \le N \le 2 \times 10^5)\) 个球，第 \(i\) 个球的大小是 \(2^{A_i}(0 \le A_i \le 10^9)\)。你需要执行以下操作 \(N\) 次。

在第 \(i\) 次操作中，首先你需要将第 \(i\) 个球加入到序列的最右端，然后重复下列流程：

如果这个序列只剩下 \(1\) 个或 \(0\) 个球，结束本次操作。
如果这个序列最右端的两个球的大小不同，结束本次操作。
如果这个序列最右端的两个球的大小相同，将这两个球合并成一个，合并后的球的大小是原先的两个球的大小之和。然后重复执行直到满足条件 1 或条件 2。

输出 \(N\) 次操作结束后，序列中球的个数。

解题思路

用一个栈来维护即可，栈中存 \(A_i\)，合并时相当于对 \(A_i\) 加 \(1\)。

参考代码

C++

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    int n, x;
    cin >> n;
    stack<int> st;
    while(n--)
    {
        cin >> x;
        while(!st.empty() && x == st.top())
        {
            x++;
            st.pop();
        }
        st.push(x);
    }
    cout << st.size() << endl;
    return 0;
}

D - Grid and Magnet ¶

题目大意

给你一个 \(H \times W(1 \le H, W \le 1000)\) 的矩阵，矩阵中有一些格子是 # 表示磁铁，. 表示地面。磁铁不可通行，且当你在磁铁上的上下左右四个格子中时，磁铁会把你吸住，此时你也不能进行移动。

你可以选定一个任意的起始位置出发，然后进行多次的移动，每一步可以移动到上下左右的相邻格子中，当你被磁铁吸住时，本次移动结束。你只能回到起始位置从新开始移动。

问：如果允许你从起始位置出发无限次，最多能到达多少个不同的格子？

解题思路

我们称磁铁附近的 . 为 终端点，显然我们的起始位置不应该选择终端点，因为终端点的答案只有 \(1\)。

标记出所有的终端点。

下面考虑非终端点如何计算答案，由于可以多次移动，非终端点会形成连通块，连通块的边界就是终端点，因此我们进行执行多轮 dfs 求连通块的操作，每轮 dfs 中将非终端点纳入当前的连通块，访问到终端点时返回。

这里和普通的求连通块不同的是，一个终端点可以被多个不同的连通块访问，所以不能简单的使用 bool 来标记一个点是否被访问过，我的办法是，引入的时间戳 t 用来表示现在正在处理第 t 个连通块，这样就能过了。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; i++)
        cin >> g[i];
    auto inlim = [n, m](int r, int c) -> bool
    { return r >= 0 && r < n && c >= 0 && c < m; };
    const int dr[] = {-1, 1, 0, 0};
    const int dc[] = {0, 0, -1, 1};
    vector<vector<bool>> ep(n, vector<bool>(m));
    for (int r = 0; r < n; r++)
        for (int c = 0; c < m; c++)
        {
            for (int i = 0; i < 4; i++)
            {
                int nr = r + dr[i], nc = c + dc[i];
                if (inlim(nr, nc) && g[nr][nc] == '#')
                {
                    ep[r][c] = true;
                    break;
                }
            }
        }
    vector<vector<int>> vis(n, vector<int>(m));
    int cnt = 0, t = 0;
    auto dfs = [&](auto &&self, int r, int c)
    {
        cnt++;
        vis[r][c] = t;
        if (ep[r][c])
            return;
        for (int i = 0; i < 4; i++)
        {
            int nr = r + dr[i], nc = c + dc[i];
            if (inlim(nr, nc) && g[nr][nc] == '.' && vis[nr][nc] != t)
                self(self, nr, nc);
        }
    };
    int ans = 1;
    for(int r = 0; r < n; r++)
        for(int c = 0; c < m; c++)
            if(!vis[r][c] && g[r][c] == '.' && !ep[r][c])
            {
                cnt = 0;
                t++;
                dfs(dfs, r, c);
                ans = max(ans, cnt);
            }
    cout << ans << endl;
    return 0;
}

E - Jump Distance Sum ¶

题目大意

在平面上给你 \(N(2 \le N \le 2 \times 10^5)\) 个点 \(P_1, P_2, \cdots, P_N\) ，其中 \(P_i\) 的坐标为 \((X_i, Y_i)\) 。

定义点 \(A\) 和点 \(B\) 的距离 \(\text{dist}(A, B)\) 如下：

假设有一只兔子一开始站在点 \(A\) 上。

假设当前兔子的坐标是 \((x, y)\)，它每一次可以跳到 \((x+1, y+1)\)，\((x+1, y-1)\)，\((x-1, y+1)\) 或者 \((x-1, y-1)\) 的格子上。

定义 \(\text{dist}(A, B)\) 表示兔子从点 \(A\) 跳到点 \(B\) 的最少次数。

如果无法从点 \(A\) 跳到点 \(B\)，则 \(\text{dist}(A, B) = 0\)

求出 \(\sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^N\text{dist}(P_i, P_j)\)

解题思路

观察跳跃规则可以发现，\(X_i + Y_i\) 的奇偶性决定了哪些点的距离为 \(0\)，哪些点的距离不为 \(0\)。具体来说：

如果 \((X_i + Y_i) \equiv(X_j+Y_j) \bmod 2\)，则 \(P_i\) 和 \(P_j\) 的距离不为 \(0\)
否则，\(P_i\) 和 \(P_j\) 的距离为 \(0\)

\(0\) 的贡献是不用考虑的，所以直接按照 \(X_i + Y_i\) 的奇偶性分成两个点集，求出两个点集内部的距离之和相加即可。

下面考虑如何求出一个点集内的距离之和。以 \((X_i + Y_i) \equiv 0 \bmod 2\) 的集合为例，注意到跳跃方式实际就是 “左上”，“左下”，”右上“，”右下“，考虑将”右上“映射成”右“，即将 \((x, y)\) 映射成 \((a, b)\)，映射前的 \((x+1, y+1)\) 相当于映射后的 \((a+1, 0)\) ，不难写出映射后的对应关系为：

\[ \left\{\begin{matrix} a = \frac{x+y}{2} \\ b = \frac{y-x}{2} \end{matrix}\right. \]

映射前 \((x, y)\) 的 \(\text{dist}\) 实际就是映射后 \((a, b)\) 的曼哈顿距离，而曼哈顿距离的横纵坐标是分开计入贡献的，所以我们可以将映射后的 \(a\) 和 \(b\) 存入到两个 vector 中，分开计算贡献然后相加即可。

下面考虑计算 \(a\) 所在的 vector 的贡献，只需要对 \(a\) 进行排序，然后在遍历的时候直接减就能计算出差值。这样问题就解决了。

同样给出 \((X_i + Y_i) \equiv 1 \bmod 2\) 的映射关系，在刚才的映射关系中我实际取的中心是 \((0, 0)\)，而在 \((X_i + Y_i) \equiv 1 \bmod 2\) 时就不能取 \((0, 0)\) 了，所以我取的是 \((1, 0)\) ，这样映射关系就是：

\[ \left\{\begin{matrix} a = \frac{x+y-1}{2} \\ b = \frac{y-x+1}{2} \end{matrix}\right. \]

参考代码

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    typedef long long LL;
    vector<vector<int>> v(4);
    int n, x, y;
    cin >> n;
    while (n--)
    {
        cin >> x >> y;
        if ((x & 1) == (y & 1))
        {
            v[0].push_back((x + y) / 2);
            v[1].push_back((y - x) / 2);
        }
        else
        {
            v[2].push_back((x + y - 1) / 2);
            v[3].push_back((y - x + 1) / 2);
        }
    }
    auto cal = [](vector<int> &v) -> LL 
    {
        sort(v.begin(), v.end());
        LL ans = 0, s = 0;
        for(int i = 0, n = v.size(); i < n; s += v[i++])
            ans += (LL)i * v[i] - s;
        return ans;
    };
    LL ans = 0;
    for(int i = 0; i < 4; i++)
        ans += cal(v[i]);
    cout << ans << endl;
    return 0;
}

F - Double Sum ¶

题目大意

给你一个序列 \(A = (A_1, A_2, \cdots, A_N)\)，求出 \(\sum\limits_{i=1}^{N}\sum\limits_{j=i+1}^N\text{max}(A_j-A_i, 0)\)

数据范围：

\(2 \le N \le 4 \times 10^5\)
\(0 \le A_i \le 10^8\)

解题思路

看了一眼 \(A_i\) 的范围，\(10^8\)，果断用动态开点权值线段树，把 \(A\) 的值当成区间，线段树维护当前区间有多少个值，以及这些值的和，这样遍历到 \(A_j\) 时，在线段树中查出有多少个比 \(A_j\) 小的数（假设有 \(k\) 个），以及这些数字的和是多少（假设和是 \(s\)），则所有在 \(1 \le A_i < A_j\) 的贡献就是 \(kA_j - s\)。然后再把 \(A_j\) 插入线段树中。这样时间复杂度是 \(nlog|A|\)，是可以过的。

过了之后发现用了 256MB （本题限制是 1024MB ），算了一下 \(10^8\) 大约是 \(17\) 层，这样的话 \(17n\) 差不多就是 256MB，于是赛后想了想有没有别的做法...

后来看了官解之后才知道，完全可以离散化一下，这样也用不上线段树了，直接树状数组就能维护了，实现真正的线性空间复杂度！

参考代码

离散化+树状数组动态开点线段树

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

struct FenwickTree
{
    int n;
    vector<LL> t;

    FenwickTree(int n) : n(n), t(n+1) {}

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

    void add(int x, int k)
    {
        for(; x <= n; x += lowbit(x))
            t[x] += k;
    }

    LL ask(int x)
    {
        LL ans = 0;
        for(; x; x -= lowbit(x))
            ans += t[x];
        return ans;
    }
};


int main()
{
    int n;
    cin >> n;
    FenwickTree cnt(n), sum(n);
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    vector<int> rk = a;
    sort(rk.begin(), rk.end());
    rk.erase(unique(rk.begin(), rk.end()), rk.end());
    LL ans = 0;
    for(int i = 0; i < n; i++)
    {
        int j = lower_bound(rk.begin(), rk.end(), a[i]) - rk.begin() + 1;
        LL s = sum.ask(j), c = cnt.ask(j);
        ans += c * a[i] - s;
        sum.add(j, a[i]);
        cnt.add(j, 1);
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

struct QueryResult
{
    LL sum, cnt;
};

QueryResult operator + (const QueryResult &x, const QueryResult &y)
{return QueryResult{x.sum+y.sum, x.cnt+y.cnt};}

struct SegmentTree
{
    struct Node
    {
        LL sum;
        int cnt;
        int lch, rch;
    };
    int n, idx = 1;
    vector<Node> t;
    SegmentTree(int n) : n(n), t(27 * n) {}
    void add(int &p, int beg, int end, int x)
    {
        if(p == 0)
            p = ++idx;
        if(beg == end)
        {
            t[p].cnt++;
            t[p].sum += beg;
            return;
        }
        int mid = (beg + end) / 2;
        int &lch = t[p].lch, &rch = t[p].rch;
        x <= mid ? add(lch, beg, mid, x) : add(rch, mid+1, end, x);
        t[p].sum = t[lch].sum + t[rch].sum;
        t[p].cnt = t[lch].cnt + t[rch].cnt;
    }
    QueryResult query(int p, int beg, int end, int l, int r)
    {
        if(p == 0 || end < l || beg > r)
            return QueryResult{0, 0};
        if(beg >= l && end <= r)
            return QueryResult{t[p].sum, t[p].cnt};
        int mid = (beg + end) / 2;
        int lch = t[p].lch, rch = t[p].rch;
        return query(lch, beg, mid, l, r) + query(rch, mid+1, end, l, r);
    }
};

int main()
{
    int n, x;
    cin >> n;
    SegmentTree t(n);
    int root = 1;
    LL ans = 0;
    while(n--)
    {
        cin >> x;
        QueryResult res = t.query(1, 0, 1E8, 0, x-1);
        ans += res.cnt * x - res.sum;
        t.add(root, 0, 1E8, x);
    }
    cout << ans << endl;
    return 0;
}

G - Hash on Tree ¶

题目大意

给你一棵 \(N(1 \le N \le 2 \times 10^5)\) 个点的树，点 \(1\) 是树的根节点。第 \(i\) 个点的权值是 \(A_i(0 \le A_i < 998244353)\)。

定义 \(f(i)\) 表示以点 \(i\) 为根的子树的哈希值，\(f(i)\) 的计算方式为：

如果点 \(i\) 是叶子节点，则 \(f(i) = A_i\)
如果点 \(i\) 不是叶子节点，则 \(f(i) = A_i + \prod\limits_{c \in s(i)} f(c)\)，其中 \(s(i)\) 表示 \(i\) 的孩子。

给你 \(Q(1 \le Q \le 2 \times 10^5)\) 个操作，每一次操作给你两个数字 \(v\) 和 \(x\)，表示将 \(A_v\) 修改成 \(x\)。你需要在每次操作后输出整棵树的哈希值（即 \(f(1)\) 的值），答案对 \(998244353\) 取模。

解题思路

首先不考虑修改操作，求出 \(f(1)\) 就是一个树形 dp。加上修改操作，就是动态 dp 了，先轻重链剖分。

考虑在 \(f[i]\) 的转移式中分割出重孩子的部分，定义 \(j\) 表示点 \(i\) 的重孩子，且 \(g[i] = \prod\limits_{c \in s(i) \backslash j} f(c)\)，即 \(i\) 的所有轻孩子的 \(f\) 值的乘积

此时有 \(f[i] = A[i] + g[i] \times f[j]\)

矩阵的形式就是：

\[ \begin{bmatrix} g[i] & a[i] \\ 0 & 1 \end{bmatrix} \begin{bmatrix} f[j]\\ 1 \end{bmatrix} = \begin{bmatrix} f[i]\\ 1 \end{bmatrix} \]

然后将 \(\begin{bmatrix} f[j]\\ 1 \end{bmatrix}\) 也归一化成矩阵的形式，不难算出：

\[ \begin{bmatrix} g[i] & a[i] \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & f[j]\\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & f[i]\\ 0 & 1 \end{bmatrix} \]

这样在矩阵连乘之后，右上角的值就是对应的 \(f\) 值。

剩下的就是动态 dp 的模板了，令 \(M[i] = \begin{bmatrix} g[i] & a[i] \\ 0 & 1 \end{bmatrix}\) ，每次单点修改实际就是改 \(M[i][0][1]\) 的值，然后求出整条重链的矩阵值，再更新到父节点上，更新的时候首先除掉原先的 \(f\) 值（需要求逆元），然后再乘上新的 \(f\) 值。

不过我发现我总是疯狂 WA 掉最后两个测试点。。最后发现这道题的 \(A_i\) 和 \(x\) 的值都有可能为 \(0\)，一方面这样求逆元的时候要特判一下，另一方面考虑一种情况：

当我们从一条重链更新到父节点的时候， \(g[i]\) 有可能已经是 \(0\) 了，相当于以前的值都丢失了，而 \(g[i]=0\) 表示存在一个轻孩子的 \(f\) 值是 \(0\)，在更新时我们并不知道是哪一个。

所以必须记录额外的信息，我的解决办法是：再单开两个数组，\(c[i]\) 表示 \(i\) 的所有轻孩子的非零 \(f\) 值的乘积，以及 \(cnt[i]\) 表示 \(i\) 的所有轻孩子中 \(f\) 值为 \(0\) 的数量。这样，重链向上的更新只会影响到 \(c[i]\) 和 \(cnt[i]\) 这两个数组的值，然后 \(i\) 在线段树更新（也就是更新自己的 \(M[i]\) 矩阵）时再参考这 \(c[i]\) 和 \(cnt[i]\) 的值更新 \(M[i][0][0]\) 的值。

参考代码

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
const int maxm = maxn * 2;
const int mod = 998244353;

int n;
int head[maxn], edge[maxm], ne[maxm], idx = 1;
void add(int u, int v)
{
    edge[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}

struct Matrix 
{
    static const int n = 2;
    LL g[n][n];
    Matrix() // 默认构造加法单位元
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                g[i][j] = 0;
    }
    static Matrix mul_unit_matrix()
    {
        Matrix u;
        u[0][0] = u[1][1] = 1;
        return u;
    }
    Matrix(LL c, int x)
    {
        g[0][0] = c;
        g[0][1] = x;
        g[1][0] = 0;
        g[1][1] = 1;
    }
    LL* operator [] (int i)
    {return g[i];}
    const LL* operator [] (int i) const
    {return g[i];}
};

const Matrix mul_unit = Matrix::mul_unit_matrix();

Matrix operator * (const Matrix &x, const Matrix &y)
{
    Matrix z;
    for(int i = 0; i < Matrix::n; i++)
        for(int j = 0; j < Matrix::n; j++)
            for(int k = 0; k < Matrix::n; k++)
                z[i][j] = (z[i][j] + x[i][k] * y[k][j]) % mod;
    return z;
}

int fa[maxn], siz[maxn], son[maxn], top[maxn], bot[maxn], dfn[maxn], ord[maxn], ti = 1, cnt[maxn];
LL a[maxn], dp[maxn], c[maxn];
Matrix A[maxn];
void dfs(int u, int f)
{
    siz[u] = 1;
    fa[u] = f;
    int M = 0;
    dp[u] = a[u];
    LL s = 1;
    for(int i = head[u]; i; i = ne[i])
    {
        int v = edge[i];
        if(v == f)
            continue;
        dfs(v, u);
        s = (s * dp[v]) % mod;
        if(siz[v] > M)
        {
            M = siz[v];
            son[u] = v;
        }
        siz[u] += siz[v];
    }
    if(son[u])
        dp[u] = (dp[u] + s) % mod;
}
void decompose(int u, int t)
{
    top[u] = t;
    dfn[u] = ti;
    ord[ti] = u;
    bot[t] = ti++;
    if(!son[u])
        return;
    if(siz[u] > 1)
        c[u] = 1;
    decompose(son[u], t);
    for(int i = head[u]; i; i = ne[i])
    {
        int v = edge[i];
        if(v == fa[u] || v == son[u])
            continue;
        decompose(v, v);
        if(dp[v] == 0)
            cnt[u]++;
        else
            c[u] = (c[u] * dp[v]) % mod;
    }
}

Matrix t[maxn*4];

void build(int p, int beg, int end)
{
    if(beg == end)
    {
        int u = ord[beg];
        A[u] = Matrix(cnt[u] ? 0 : c[u], a[u]);
        t[p] = A[u];
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    build(lch, beg, mid);
    build(rch, mid+1, end);
    t[p] = t[lch] * t[rch];
}

Matrix get_segment(int p, int beg, int end, int l, int r)
{
    if(end < l || beg > r)
        return mul_unit;
    if(beg >= l && end <= r)
        return t[p];
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    return get_segment(lch, beg, mid, l, r) * get_segment(rch, mid+1, end, l, r);
}

void update(int p, int beg, int end, int pos)
{
    if(beg == end)
    {
        int u = ord[beg];
        A[u][0][0] = cnt[u] ? 0 : c[u];
        t[p] = A[u];
        return;
    }
    int mid = (beg + end) / 2;
    int lch = p * 2, rch = p * 2 + 1;
    pos <= mid ? update(lch, beg, mid, pos) : update(rch, mid+1, end, pos);
    t[p] = t[lch] * t[rch];
}

void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

LL inv(LL a)
{
    LL x, y;
    exgcd(a, mod, x, y);
    if(x < 0)
        x += mod;
    return x;
}

void update_path(int u, int x)
{
    A[u][0][1] = a[u] = x;
    Matrix old, now;
    while(u)
    {
        int t = top[u];
        old = get_segment(1, 1, n, dfn[t], bot[t]);
        update(1, 1, n, dfn[u]);
        now = get_segment(1, 1, n, dfn[t], bot[t]);
        u = fa[t];
        LL ft = old[0][1];
        if(!ft)
            cnt[u]--;
        else
            c[u] = (c[u] * inv(ft)) % mod;
        ft = now[0][1];
        if(!ft)
            cnt[u]++;
        else
            c[u] = (c[u] * ft) % mod;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m, u, x;
    cin >> n >> m;
    for(int i = 2; i <= n; i++)
    {
        cin >> u;
        add(u, i);
        add(i, u);
    }
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(1, 0);
    decompose(1, 1);
    build(1, 1, n);
    while(m--)
    {
        cin >> u >> x;
        update_path(u, x);
        Matrix res = get_segment(1, 1, n, 1, bot[1]);
        cout << res[0][1] << endl;
    }
    return 0;
}

最后更新: 2024-05-12
创建日期: 2024-05-10

ABC351(A-G)

A - The bottom of the ninth¶

B - Spot the Difference¶

C - Merge the balls¶

D - Grid and Magnet¶

E - Jump Distance Sum¶

F - Double Sum¶

G - Hash on Tree¶

A - The bottom of the ninth ¶

B - Spot the Difference ¶

C - Merge the balls ¶

D - Grid and Magnet ¶

E - Jump Distance Sum ¶

F - Double Sum ¶

G - Hash on Tree ¶