ABC371(A-G)

A - Jiro

题目大意

有三个不相等的数字 \(A\)、\(B\) 和 \(C\)，给你三个符号 \(S_{AB}\)，\(S_{AC}\) 和 \(S_{BC}\)，这三个符号要么是 <，要么是 >。如果 \(S_{AB}\) 是 <，表示 \(A < B\)，如果 \(S_{AB}\) 是 > ，表示 \(A > B\)，其他情况以此类推。问：三个数字中第二大的数字是哪个？

解题思路

如果不想分类讨论的话，可以小于号表示为偏序关系，若 \(x < y\)，则图中有一条从 \(x\) 到 \(y\) 的有向边。在这种图中，记录下每个点的入度，就是小于这个点的数字的个数。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    char s;
    vector<int> ind(3);
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 3; j++)
        {
            cin >> s;
            if(s == '<')
                ind[j]++;
            else
                ind[i]++;
        }
    for(int i = 0; i < 3; i++)
        if(ind[i] == 1)
            cout << char('A' + i) << endl;
    return 0;
}

---

B - Taro

题目大意

某个国家有 \(N\) 个家庭，初始的时候，每个家庭都没有小孩。有 \(M\) 个小孩出生的事件按顺序到达，第 \(i\) 个事件可以用 \(A_i\) 和 \(B_i\) 表示，其中 \(A_i\) 是整数且 \(1 \le A_i \le N\)，表示这个小孩出生在第 \(A_i\) 个家庭。\(B_i\) 是一个字符，只可能取 M 或 F, 其中 M 表示男性，F 表示女性。定义 长子 表示某个家庭中最年长的男孩子（注意，可能存在比长子年长的姐姐）。对于这个 \(M\) 个按顺序出生的孩子，如果这个孩子是长子，输出 Yes，否则输出 No。

参考代码

C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<bool> vis(n+1);
    while(m--)
    {
        int a;
        char f;
        cin >> a >> f;
        if(!vis[a] && f == 'M')
        {
            vis[a] = true;
            cout << "Yes" << endl;
        }
        else
            cout << "No" << endl;
    }
    return 0;
}

---

C - Make Isomorphic

题目大意

给你两个简单无向图 \(G\) 和 \(H\)，这两个图都有 \(N(1 \le N \le 8)\) 个点，但两个图的边数不一定相同。

你可以执行以下操作任意次：

• 从图 \(H\) 中选择两个点，如果这两个点之间没有连边，你可以花费 \(A_{i, j}\) 添加这条边。如果这两个点之间有连边，你可以花费 \(A_{i, j}\) 移除这条边。

问：为了让图 \(G\) 和图 \(H\) 同构，最少的花费多少？

解题思路

\(N \le 8\)，枚举全排列代表同构的方式，然后二重循环求解花费即可。时间复杂度 \(O(N! \times N^2)\)

参考代码

C++

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

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> src(n + 1, vector<bool>(n + 1));
    vector<vector<bool>> dst(n + 1, vector<bool>(n + 1));
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        dst[u][v] = dst[v][u] = true;
    }
    cin >> m;
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        src[u][v] = src[v][u] = true;
    }
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            cin >> a[i][j];
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++)
        p[i] = i;
    int ans = numeric_limits<int>::max();
    do
    {
        int cost = 0;
        for (int u = 1; u <= n; u++)
            for (int v = u + 1; v <= n; v++)
            {
                if (src[u][v] != dst[p[u]][p[v]])
                    cost += a[u][v];
            }
        ans = min(ans, cost);
    } while (next_permutation(p.begin() + 1, p.end()));
    cout << ans << endl;
    return 0;
}

---

D - 1D Country

题目大意

在一维数轴上有 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个村庄，第 \(i\) 个村庄的坐标是 \(X_i\)，有 \(P_i\) 个村民。

给你 \(Q(1 \le Q \le 2 \times 10 ^ 5)\) 个询问，每个询问包括两个数字 \(L_i\) 和 \(R_i\)，你需要回答出在范围 \([L_i, R_i]\) 内有多少村民。

解题思路

在线的做法就是前缀和+二分，每一次查询 \(O(\log N)\) 。离线做法可以离散化所有的坐标，每次查询 \(O(1)\)，下面的做法是离线做法。

参考代码

C++

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

using namespace std;
using LL = long long;

int main()
{
    int n, q;
    cin >> n;
    vector<int> x(n), p(n);
    for (int i = 0; i < n; i++)
        cin >> x[i];
    for (int i = 0; i < n; i++)
        cin >> p[i];
    cin >> q;
    vector<int> l(q), r(q);
    for (int i = 0; i < q; i++)
        cin >> l[i] >> r[i];
    vector<int> xs = x;
    xs.insert(xs.end(), l.begin(), l.end());
    xs.insert(xs.end(), r.begin(), r.end());
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    auto compress = [&xs](vector<int> &v) -> void
    {
        for (auto &x : v)
            x = lower_bound(xs.begin(), xs.end(), x) - xs.begin() + 1;
    };

    compress(x);
    compress(l);
    compress(r);

    int len = xs.size();
    vector<LL> s(len + 1);
    for (int i = 0; i < n; i++)
        s[x[i]] += p[i];
    for (int i = 1; i <= len; i++)
        s[i] += s[i - 1];
    for (int i = 0; i < q; i++)
        cout << s[r[i]] - s[l[i] - 1] << endl;
    return 0;
}

---

E - I Hate Sigma Problems

题目大意

给你一个长度为 \(N(2 \times 10 ^ 5)\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\)，定义 \(f(l, r)\) 表示连续子序列 \((A_l, A_{l+1}, \cdots, A_r)\) 当中不同的数字的数量。求出 \(\sum\limits_{i = 1} ^ N\sum\limits_{j = i}^Nf(i, j)\)

解题思路

对于一个连续子序列，如果有出现两次或更多次的数字，只计入第一个数字所产生的贡献。这样的话，每个数字都会有一个作用范围，设序列 \(A\) 中数字 \(x\) 出现的位置为 \(p_1, p_2, \cdots, p_n\)，首先考虑 \(p_1\) 的贡献，如果有序列 \(f(l, r)\) 满足 \(1 \le l \le p_1 \le r \le n\)，这都表示 \(p_1\) 位置是第一个数字 \(x\)，只计入 \(p_1\) 作贡献，而这样的序列 \(l\) 可能取值有 \(p_1\) 个，\(r\) 的可能取值有 \(n- p_1 + 1\) 个，因此 \(p_1\) 的贡献为 \(p_1 \times(n-p_1+1)\)。考虑 \(p_2\) 的贡献，为了屏蔽掉 \(p_1\)，就需要 \(f(l, r)\) 满足 \(p_1+1 \le l \le p_2 \le r \le n\)，因此 \(p_2\) 的贡献为 \((p_2 - p_1) \times (n - p_2 + 1)\)。后面同理。

参考代码

C++

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    unordered_map<int, vector<LL>> num;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        auto it = num.find(x);
        if (it == num.end())
            num[x] = {0, i};
        else
            it->second.push_back(i);
    }
    LL ans = 0;
    for (auto [_, v] : num)
    {
        int k = v.size();
        for (int i = 1; i < k; i++)
        {
            LL l = v[i] - v[i - 1];
            LL r = n - v[i] + 1;
            ans += l * r;
        }
    }
    cout << ans << endl;
    return 0;
}

---

F - Takahashi in Narrow Road

题目大意

有一个一维无限长的数轴，数轴上有 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个棋子，初始的时候，第 \(i\) 枚棋子的坐标是 \(X_i\)。

在任何时刻，你可以执行以下操作任意次：

• 每一次操作选择一枚棋子，将这枚棋子向左或者向右移动 \(1\) 单位。注意不能出现两个棋子在同一个坐标的情况，也就是说对于某个坐标为 \(X\) 的棋子，如果 \(X-1\) 或者 \(X+1\) 上已经有一枚棋子，就不能将这枚棋子向左或者向右移动。

按顺序给你 \(Q\) 个任务，每个任务给你一个数字 \(T_i\) 和 \(G_i\)，表示你需要将从左往右数的第 \(T_i\) 个棋子移动到 \(G_i\)。对于每个任务，你需要回答至少需要执行几次操作才能完成。

解题思路

假设当前第 \(T_i\) 个棋子需要往右移动到目的地，且第 \(T_i\) 个棋子当前的坐标为 \(X\)，如果 \(X + 1,X+2,...\) 一连串的位置都有棋子，根据移动的规则，这些棋子肯定是一起往右移动的，所以为了加快移动的操作，需要批量的将相连的棋子进行移动。于是需要维护每个棋子所在的左右边界，在移动的过程中进行批量的合并和拆解。可以证明，每一次移动至多进行一次拆分（就是 \(T_i\) 处于连续一段的中间时），但是合并却有可能进行多次，所以均摊下来合并的拆解的时间复杂度是 \(O(1)\)，至于批量的移动，维护一个 map 表示当前还存在的连续的棋子段，每次移动的时候在 map 当中二分即可，要么二分到达目的地，要么二分到达下一个应该合并的位置。实现的时候略微繁琐。

参考代码

C++

#include <iostream>
#include <limits>
#include <map>

using namespace std;
using LL = long long;

const int NINF = numeric_limits<int>::min() / 2;
const int PINF = numeric_limits<int>::max() / 2;

int main()
{
    int n, q;
    cin >> n;
    map<int, pair<LL, LL>> pos;
    pos[0] = {NINF, NINF};
    pos[n + 1] = {PINF, PINF};
    for (int i = 1; i <= n; i++)
    {
        LL x;
        cin >> x;
        pos[i] = {x, x};
    }
    cin >> q;
    LL ans = 0;
    while (q--)
    {
        int t, g;
        cin >> t >> g;
        auto it = --pos.upper_bound(t);
        auto [id, p] = *it;
        auto [l, r] = p;
        LL now = t - id + l;
        if (now == g)
            continue;
        else if (now < g)
        {
            if(id != t)
                it->second.second = now - 1;
            l = now;
            LL cnt = r - l + 1;
            ++it;
            while (true)
            {
                auto [next_l, next_r] = it->second;
                LL d = min(g - l, next_l - 1 - r);
                ans += d * cnt;
                l += d;
                r += d;
                if (l == g)
                    break;
                cnt += next_r - next_l + 1;
                r = next_r;
                it = pos.erase(it);
            }
            pos[t] = {l, r};
        }
        else
        {
            if (r != now)
                pos[t + 1] = {now + 1, r};
            r = now;
            LL cnt = r - l + 1;
            it = --pos.erase(it);
            int lid = id;
            while (true)
            {
                auto [last_l, last_r] = it->second;
                LL d = min(r - g, l - last_r - 1);
                ans += d * cnt;
                r -= d;
                l -= d;
                if (r == g)
                    break;
                cnt += last_r - last_l + 1;
                l = last_l;
                lid = it->first;
                it = --pos.erase(it);
            }
            pos[lid] = {l, r};
        }
    }
    cout << ans << endl;
    return 0;
}

---

G - Lexicographically Smallest Permutation

题目大意

给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的排列 \(P = (P_1, P_2, \cdots, P_N)\) 和长度为 \(N\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\)。

你可以执行以下操作任意次：

• 对于所有的 \(i = 1,2,...,N\)， 同时 将 \(A_i\) 替换成 \(A_{p_i}\)。

输出能够得到的字典序最小的序列 \(A\)

解题思路

这种替换关系最终会形成若干个环，例如对于第一个环（包含 \(i = 1\) 的环）类似于 \(1 \leftarrow P_1 \leftarrow P_{P_1}\cdots \leftarrow 1\)。在所有的 \(P\) 序列上跑一边，处理出所有的环。

为了让字典序最小，首先需要让第一个环的字典序最小，也就是把最小的元素放在 \(i = 1\) 的位置，假设需要 \(a_1\) 次操作才能做到。下面考虑第二个环，从第二个环开始就不能盲目选择最小的元素放在前面，因为第一个环优先级更高，而第二个环的操作次数有可能影响第一个环。

进一步可以发现，如果设第一个环的长度为 \(L_1\)，那么再额外执行 \(L_1\) 次操作不会改变第一个环的结果，也就是后续的环需要保证结果形如 \(a_1 + k_1L_1\)。因此，对于第二个环来说，假设第二个环长度为 \(L_2\)，将某个元素移动到首位需要操作 \(a_2\) 次，就必须满足 \(a_1 + k_1L_1 = a_2 + k_2L_2\)，仅当这个方程有解，才能在不影响第一个环的情况下将这个元素移动到首位。这就是扩展中国剩余定理，不会的可以看 中国剩余定理 - OI Wiki、P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪 - 洛谷 、P4777 【模板】扩展中国剩余定理（EXCRT） - 洛谷。

由于这里环的长度不一定互质，所以需要用扩展中国剩余定理，但是如果根据 oiwiki 上的做法，我们需要实时的将方程进行合并，合并的时候就需要算出 \(L' = \text{lcm}(L_1, L_2)\)，这样会爆 long long（这个数字非常大，即使 128 bit 也存不下）。然而官方题解居然是用 python 高精度水过去的。这里给出一个不用高精度的做法，其实非常简单，不进行方程合并就好了，我们存下之前合法的方程，每当碰到一个新的环 \(i\)，就遍历其中所有的 \(a_i = 0, 1, ..., L_i-1\)，将 \(x \equiv a_i \bmod L_i\) 依次和之前的合法方程计算是否兼容（根据裴蜀定理确定是否有解），仅当与所有之前的方程有解，这个位置 \(a_i\) 才认为合法。在所有合法的 \(a_i\) 中找到数字最小的那一个移动到首位，然后加入到方程中，这样就做完了。

下面分析时间复杂度，首先我们会发现，如果第一个环的 \(a_1\) 已经确定，且第二个环的长度满足 \(L_2 = L_1\) 的话，那么第二个环一定只有 \(a_2 = a_1\) 符合条件，毕竟长度一样，所以前面操作多少次就影响了第二个环多少次。于是在记录合法的方程的时候，实际只需要记录环长度不同的方程，这样的话，方程的数量最多是多少呢？为了让方程数量尽可能多，一定是优先出现长度比较小的环，也就是从小到大，这样，假设有 \(m\) 个环，我们有 \(1 + 2 + 3 + \cdots+m = \frac{m(m+1)}{2}\le n\)，所以 \(m\) 是 \(\sqrt n\) 的级别，这样每个位置至多与 \(\sqrt n\) 个方程计算是否合法，总的时间复杂度就是 \(O(n \sqrt n)\)。

另外附上一个 \(O(n\log n)\) 的 题解，不过说实话我没有看懂。。

参考代码

C++

#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>

using namespace std;
using LL = long long;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }
    for (int i = 0; i < n; i++)
        cin >> a[i];
    unordered_map<int, int> equations;
    vector<int> ans(n);
    vector<bool> vis(n);

    auto check = [&equations](unordered_map<int, int> &g, int a) -> bool
    {
        for (auto [li, ai] : equations)
            if (abs(a - ai) % g[li] != 0)
                return false;
        return true;
    };

    for (int i = 0; i < n; i++)
    {
        if (vis[i])
            continue;
        vector<int> ring_idx;
        int j = i;
        while (!vis[j])
        {
            vis[j] = true;
            ring_idx.push_back(j);
            j = p[j];
        }
        int len = ring_idx.size();
        unordered_map<int, int> g;
        for (auto [l, _] : equations)
            g[l] = gcd(l, len);
        int min_num = n + 1, min_j = -1;
        for (int j = 0; j < len; j++)
        {
            int idx = ring_idx[j];
            if (a[idx] < min_num && check(g, j))
            {
                min_num = a[idx];
                min_j = j;
            }
        }
        equations[len] =  min_j;
        for (int j = 0, k = min_j; j < len; j++, k = (k + 1) % len)
        {
            int pos = ring_idx[j];
            ans[pos] = a[ring_idx[k]];
        }
    }
    for (int i = 0; i < n; i++)
        cout << ans[i] << ' ';
    return 0;
}

---

---

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