2024-10-18 11:04 已编辑羽丘女子学园 C++ 发布于江西

关注

提高组第六场题解

pink

期望、计数、逆元

根据期望的性质，每一个 $2 \times 2$ 的子矩阵彼此之间都是独立的，并且每一个子矩阵染成黑色或白色也是独立的。

因此我们只需要考虑每一个 $2 \times 2$ 的子矩阵染成黑色或白色的期望贡献即可。

每一个 $2 \times 2$ 子矩阵的期望贡献为，四个格子都被染成黑色的概率乘 $a$ 加上四个格子都被染成白色的概率乘 $b$ 。

整体的时间复杂度为： $O(n \times m \times log(10^9+5))$ 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

const LL M = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    auto ksm = [&](LL x, LL y) {
        LL ans = 1;
        while (y) {
            if (y & 1) ans = ans * x % M;
            x = x * x % M;
            y >>= 1;
        }
        return ans;
    };
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    vector p(n + 1, vector<LL>(m + 1));
    auto q = p;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> p[i][j];
            p[i][j] = p[i][j] * ksm(100, M - 2) % M;
            q[i][j] = (1 - p[i][j] + M) % M;
        }
    }
    LL sum = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            LL t = p[i][j] * p[i - 1][j] % M;
            t = t * p[i][j - 1] % M;
            t = t * p[i - 1][j - 1] % M;
            sum += t * a % M;
            sum %= M;

            t = q[i][j] * q[i - 1][j] % M;
            t = t * q[i][j - 1] % M;
            t = t * q[i - 1][j - 1] % M;
            sum += t * b % M;
            sum %= M;
        }
    }
    cout << sum << endl;
}

red

图论、最短路

首先，如果限定护照等级为 $x$ ，那么只能到达等级小于等于 $x$ 的城市。

那么此时的最小花费就是最短路 + $x$ ，此处的单源最短路可以使用朴素的迪杰斯特拉算法（堆优化反而可能更慢）、SPFA等。

由于有效的护照等级实际只有 $n$ 种，每种等级都求一遍单源最短路并取最小值，时间复杂度就为 $O(n^3)$ 。

如果我们将护照等级从小到大排序，那么就相当于每次加入一个新的顶点，并求起点到终点的最短路。

可以发现，此处可以直接使用Floyd算法，时间复杂度不变，但是代码量小、常数小。

整体的时间复杂度为： $O(n^3)$ 。

这题大样例错误回复太晚，非常抱歉QAQ。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    vector<pair<int, int>> pr;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pr.push_back({a[i], i});
    }
    sort(pr.begin(), pr.end());
    vector dis(n + 1, vector<LL>(n + 1, 1e18));
    for (int i = 1; i <= n; i++) {
        dis[i][i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        LL w = 0;
        cin >> u >> v >> w;
        dis[u][v] = min(dis[u][v], w);
        dis[v][u] = min(dis[v][u], w);
    }
    LL ans = 1e18;
    for (auto &[x, k] : pr) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[j][k]);
            }
        }
        if (x >= a[n]) ans = min(ans, dis[1][n] + x);
    }
    if (ans > 1e17) ans = -1;
    cout << ans << endl;
}

yellow

数据结构、离散化、离线

对于第一个10%的数据，可以直接暴力模拟。

对于第二个10%的数据，可以在DFS的过程中，用map记录从根节点到第u个节点的颜色数量。

对于第三个10%的数据，可以使用一个整数的二进制位存储颜色，并通过dfs序将子树转化成区间，再使用数据结构维护区间或。

对于第四个10%的数据：

首先将操作离线，并记录每个操作的时间戳；

其次从根节点向下dfs处理每个操作：

1）若为染色操作，则先判断这个颜色是否已经染过，若没有染过，则直接将这次染色时间的位置置为1；若已经染过且染色的时间比这次染色早，则这次染色无意义，不需要处理；否则，将之前染色时间的位置置为0，这次染色时间的位置置为1。

2）若为查询操作，则对1到查询时间求和，然后判断查询的颜色是否被染过即可。

实际上染色操作是一个单点修改的操作，查询操作是一个区间求和的操作（前缀和），因此可以使用数据结构进行维护（树状数组等）。并且回溯时，需要把子树中染色产生的影响消除，相当于是进行逆操作。

最后根据查询操作的时间戳，输出每一次的答案即可。

对于100%的数据，由于颜色数量有限，并且颜色本身的数字不重要，因此只需要将颜色离散化后使用上述做法即可。

整体的时间复杂度为： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector ve(n + 1, vector<int>());
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    map<int, int> mp;
    int pt = 0;
    vector a(n + 1, vector<array<int, 3>>());
    for(int i = 1; i <= q; i++){
        int op, u, x;
        cin >> op >> u >> x;
        if (!mp.count(x)) mp[x] = ++pt;
        x = mp[x];
        a[u].push_back({i, op, x});
    }
    vector<int> tr(q + 1);
    auto add = [&](auto u, auto x) {
        for (; u <= q; u += -u & u) {
            tr[u] += x;
        }
    };
    auto find = [&](auto u) {
        auto ans = 0;
        for (; u > 0; u -= -u & u) {
            ans += tr[u];
        }
        return ans;
    };
    vector st(pt + 1, vector<int>());
    vector<int> ans(q + 1, -1);
    auto dfs = [&](auto dfs, int u, int fa)->void{
        for (auto &[ti, op, x] : a[u]) {
            if (op == 1) {
                if (st[x].size() && st[x].back() < ti) continue;
                if (st[x].size()) add(st[x].back(), -1);
                st[x].push_back(ti);
                add(ti, 1);
            }
            else {
                ans[ti] = find(ti);
                if (!st[x].size() || st[x].back() > ti) ans[ti]++;
            }
        }
        for (auto &i : ve[u]) {
            if (i == fa) continue;
            dfs(dfs, i, u);
        }
        for (auto &[ti, op, x] : a[u]) {
            if (op == 1) {
                if (!st[x].size() || st[x].back() != ti) continue;
                add(ti, -1);
                st[x].pop_back();
                if (st[x].size()) add(st[x].back(), 1);
            }
        }
    };
    dfs(dfs, 1, 0);
    for (auto &i : ans) {
        if (i >= 0) cout << i << endl;
    }
}

blue

打表、前缀和、离散化

对于前40%的数据，可以通过DFS或者三进制枚举将值域内所有对称的数对打表出来后，再枚举每一对对应位置上的数字变化为每一种对称的数对需要的操作次数，找到最小值即可。

打出的表的大小在 $6 \times 10^3$ 级别，因此时间复杂度为 $O(n \times 6 \times 10^3 / 2)$ ，时限为 3s ，可以通过。

其中需要注意的有：若长度为奇数，则正中间的那个数必须变成自己与自己对称；两个 $10^9$ 需要变成 $10^9+1$ 而不是 $888888888$ 。

以[x1,y1]表示对应位置上的数字，令x1<=y1
以[x0,y0]表示对称的数对，令x0<=y0
并且我们现在有一个很大的二维数组
现在我们需要将[x1,y1]变成[x0,y0]
操作次数就是|x1-x0|+|y1-y0|
根据[x1,y1]、[x0,y0]的大小关系，可以分为四个类型：
type1:   x1 >= x0 && y1 <= y0
	min((x1 - x0) + (y0 - y1))
	调整变量顺序
	min((y0 - x0) + (x1 - y1))
由于x1-y1是定值，因此我们需要在x0小于x1，y0大于等于y1的区域（右上角）找到y0-x0最小值

type2:   x1 <= x0 && y1 <= y0
	min((x0 + y0) - (x1 + y1))
	右下角x0+y0最小值

type3:   x1 <= x0 && y1 >= y0
	min((x0 - y0) + (y1 - x1))
	左下角x0-y0最小值

type4:   x1 >= x0 && y1 >= y0
	min(-(x0 + y0) + (x1 + y1))
	左上角-(x0+y0)最小值

由于数字非常大，且有意义的数字较少（表内大概是 $10^4$ 种，每个位置上的数字不需要进入表里），因此我们可以先将数字离散化，再用四次二维前缀和维护前缀最小值。由于牛客最大只能开1GB空间，无法开到4GB，导致无法开四个 $10^8$ 的数组，只能开一个然后重复使用四次，麻烦一些。

当然，也可以离线后使用一个 $10^4$ 的数组按行进行二维前缀和，还可以用其他优雅方式计算这个前缀最小值。反正二倍时限下卡不住小常数的二位前缀和，干脆就用最暴力的办法，不卡时间和空间（要不是开不下，就直接开4GB了）。

整体的时间复杂度和空间复杂度都为： $O(1)$ 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<pair<int, int>> qry;
    for (int i = 1, j = n; i < j; i++, j--) {
        if (a[i] > a[j]) swap(a[i], a[j]);
        qry.push_back({a[i], a[j]});
    }
    map<int, int> mp;
    auto dfs = [&](auto &dfs, string s) -> void{
        if (s.size()) {
            auto x = stoi(s);
            auto t = to_string(x);
            reverse(t.begin(), t.end());
            x = stoi(t);
            t = to_string(x);
            reverse(t.begin(), t.end());
            auto y = stoi(t);
            mp[x] = y;
            mp[y] = x;
        }
        if (s.size() >= 9) return;
        dfs(dfs, s + "0");
        dfs(dfs, s + "1");
        dfs(dfs, s + "8");
    };
    dfs(dfs, "");
    mp[1e9 + 1] = 1e9 + 1;
    map<int, int> ch;
    for (auto &[x, y] : mp) {
        ch[x]++;
        ch[y]++;
    }
    int pt = 0;
    for (auto &[x, y] : ch) {
        y = ++pt;
    }
    ch[2e9 + 7] = pt + 1;
    array<array<int, 13126>, 13126> f;
    auto init = [&](int t) {
        for (int i = 0; i <= pt + 1; i++) {
            for (int j = 0; j <= pt + 1; j++) {
                f[i][j] = t;
            }
        }
    };
    auto get = [&](auto type) {
        init(2e9 + 7);
        int li = 1, ri = pt, ti = 1;
        int lj = 1, rj = pt, tj = 1;
        if (type == 1 || type == 2) {
            swap(lj, rj);
            tj = -tj;
        }
        if (type == 2 || type == 3) {
            swap(li, ri);
            ti = -ti;
        }
        for (auto &[x, y] : mp) {
            int t = x + y;;
            if (type == 1) t = y - x;
            if (type == 3) t = x - y;
            if (type == 4) t = -t;
            f[ch[x]][ch[y]] = t;
        }
        for (int i = li;; i += ti) {
            for (int j = lj;; j += tj) {
                f[i][j] = min({f[i][j], f[i - ti][j], f[i][j - tj]});
                if (j == rj) break;
            }
            if (i == ri) break;
        }
    };
    vector ans(5, vector<int>());
    for (int type = 1; type <= 4; type++) {
        get(type);
        for (auto &[x, y] : qry) {
            int i, j;
            if (type == 1 || type == 4) i = prev(ch.upper_bound(x))->second;
            else i = ch.lower_bound(x)->second;
            if (type == 3 || type == 4) j = prev(ch.upper_bound(y))->second;
            else j = ch.lower_bound(y)->second;
            int sum = f[i][j];
            if (type == 1) sum += x - y;
            if (type == 2) sum -= x + y;
            if (type == 3) sum += y - x;
            if (type == 4) sum += x + y;
            ans[type].push_back(sum);
        }
    }
    LL sum = 0;
    if (n & 1) {
        int mi = 2e9;
        for (auto &[x, y] : mp) {
            if (x == y) mi = min(mi, abs(x - a[n + 1 >> 1]));
        }
        sum += mi;
    }
    for (int i = 0; i < ans[1].size(); i++) {
        int mi = 2e9;
        for (int j = 1; j <= 4; j++) {
            mi = min(mi, ans[j][i]);
        }
        sum += mi;
    }
    cout << sum << endl;
}