AtCoder Beginner Contest 371 题解

E – I Hate Sigma Problems

定义函数 $f (l,r)$ 表示 $A [l],A [l+1],\cdots,A [r]$ 中不同的元素个数，求
$\sum_{i=1}^N\sum_{j=i}^N f(i,j).$

其实就是求数组 $A$ 中所有区间的元素种类数。可以通过枚举不同元素的贡献来解决，以样例 5 4 2 2 3 2 4 4 1 为例，可以枚举元素 $1,2,3,4,5$ ；以元素 $2$ 为例，此时我们只关注该元素，即数组 x x 2 2 x 2 x x x。

要做的就是求出元素 2 出现在哪些区间中，反向思考：求出元素 2 不出现哪些区间中本题就解决了。

 #include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    map<int, vector<int>> mp;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (!mp.count(x)) {
            mp[x].push_back(0);
        }
        mp[x].push_back(i + 1);
    }
    
    ll res = 0;
 
    auto solve = [&](vector<int>& v) {
        ll ans = 1ll * n * (n + 1) / 2;
        v.push_back(n + 1);
        for (int i = 1; i < v.size(); i++) {
            ans -= 1ll * (v[i] - v[i - 1]) * (v[i] - v[i - 1] - 1) / 2;
        }
        return ans;
    };
 
    for (auto&& [k, v] : mp) {
        res += solve(v);
    }
    cout << res;
}

F – Takahashi in Narrow Road

$N$ 个人初始分布在一维数轴上，第 $i$ 个人位于位置 $X_i$ ，且 $0\le X_1\lt X_2\lt\cdots\lt X_N\le 10^8$ 。

进行以下操作 $Q$ 次：

指定第 $T_i$ 个人前往坐标 $G_i$ 。但是有一个要求：任意两个人的位置不能重合。

求出所有人总共的移动距离。

我们可以将每一个人看作一个 “块”，当某个人要前往一个坐标且需要推动别人前进时，我们可以认为这个人和被推动的人所在的块合并了。当一个 “大块” 内部的某个人被指定移动时，这个 “大块” 就可以被认为是分裂成了两个新的块，一个块在原地，另一个块则发生了移动并可能继续与其他块合并。

由于块的合并必定会减少块的数量，而块的分裂至多令块的总数加一，所以我们可以直接维护这个块的合并、分裂过程。需要的操作就是：

查询第 k 个人在当前的哪一个块中
块的合并 / 分裂

块的合并 / 分裂就是模拟。查询第 k 个人在当前的哪一个块中可以通过维护前缀和 + 二分的方法搞定，这是因为本题中每个人的相对位置是不会变的。具体实现上，我们只需要维护每个块覆盖的区间 $[l,r]$ 并将这个块挂在位于 $l$ 的这个人的排名所在的结点上。假设我们当前在维护的区间是 $[1,1],[12,13],[20,22],[30,30]$ ，那么这 4 个区间分别应该挂在结点 $1,2,4,7$ 上。

 #include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
struct seg {
    int l, r;
    bool operator < (const seg& rhs) {
        return l < rhs.l;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n;
    map<int, seg> mp;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        mp[i] = { x,x };
    }
    mp[(int)1e9] = { (int)2e9,(int)2e9 };
    mp[(int)-1e9] = { (int)-2e9,(int)-2e9 };
 
    ll res = 0;
    cin >> q;
    while (q--) {
        int t, g;
        cin >> t >> g;
        --t;
        auto&& it = mp.upper_bound(t);
        it--;
        auto pre_it = it;
        int pl = pre_it->second.l, pr = pre_it->second.r;
        int current_pos = it->second.l + (t - it->first);
        int pt = current_pos;
        int lo = pt, hi = pt;
 
        ll res_q = 0;
        if (current_pos > g) {  // go left
            // split node
            // [l, r] split into [l, current_pos], [current_pos + 1, r]
            res_q += 1ll * (current_pos - pl + 1) * (current_pos - g);
            lo = g - (current_pos - pl);
            if (pr > current_pos) {
                mp[t + 1] = { current_pos + 1, pr };
            }
            it--;
            mp.erase(pre_it);
            pre_it = it;
            pl = it->second.l, pr = it->second.r;
            int pl_target = g - t + it->first;  // taeget position that pl is going to
            
            while (pl > pl_target) {
                lo = pl_target;
                res_q += 1ll * (pr - pl + 1) * (pl - pl_target);
                it--;
                mp.erase(pre_it);
                pre_it = it;
 
                pl = it->second.l, pr = it->second.r;
                pl_target = g - t + it->first;
            }
            mp[t - g + lo] = { lo,g };
        } else if (current_pos < g) {  // go right
            // split node
            // [l, r] split into [l, current_pos - 1], [current_pos, r]
            res_q += 1ll * (pr - current_pos + 1) * (g - current_pos);
            hi = g + (pr - current_pos);
            it++;
            if (current_pos > pl) {
                mp[pre_it->first] = { pl,current_pos - 1 };
            } else {
                mp.erase(pre_it);
            }
            pre_it = it;
 
            pl = it->second.l, pr = it->second.r;
            int pr_target = g + it->first - t + pr - pl;  // target position that pr is going to
            while (pr < pr_target) {
                hi = pr_target;
                res_q += 1ll * (pr - pl + 1) * (pr_target - pr);
                it++;
                mp.erase(pre_it);
                pre_it = it;
 
                pl = it->second.l, pr = it->second.r;
                pr_target = g + it->first - t + pr - pl;
            }
            mp[t] = { g,hi };
        }
        res += res_q;
    }
    cout << res;
}

G – Lexicographically Smallest Permutation

给定两个排列 $P$ 和 $A$ 。你可以进行以下操作任意次：

对于所有 $i$ ，将 $A_i$ 替换为 $A_{P_i}$ 。

求字典序最小的 $A$ 。

首先很显然的是这个替换的操作必定是一堆置换环，然后目标是字典序最小，因此考虑贪心， $A [0]$ 这个位置必定要让元素 $A [0]$ 所在的置换环上最小的元素占据。假设 $A [0]$ 所在的环大小为 $M_0$ ，将最小元素换到 $A [0]$ 的操作次数为 $T_0$ ，则对于其他任意一个环而言，他们就只能执行操作 $T_0+nM_0$ 次了。

然后再考虑怎么让第二个环取到最小值，如果不考虑第一个环的限制，假设环的大小是 $M_1$ ，将最小元素换到环的最左侧需要 $T_1$ 次操作，那么我们就只需要检测同余方程组
$\begin{cases} x\equiv T_0\pmod{M_0}\\ x\equiv T_1\pmod{M_1}\\ \end{cases}$
是否有解。这是一个经典模型，根据裴蜀定理，只需要检测 $T_0-T_1$ 是否整除 $\gcd (M_0,M_1)$ 即可。但是，由于方程组可能无解（即第二个环无法令最小元素换到最左），所以我们实际上需要枚举出所有可行的 $T_1$ ，并在所有可行的 $T_1$ 中找到字典序最小的那个。

可以用 exgcd 将同余方程 $T_0\pmod {M_0}\equiv T_1\pmod {M_1}$ 合并为一个新的同余方程 $x\equiv T^\prime\pmod {M^\prime}$ ，然后重复上述操作直到找到所有环的最小可能字典序。这个做法实际上就是 excrt。

当然也可以简化这一流程，因为我们可以直接枚举所有可能的 $T_1$ 。仍然沿用上方的符号，设第二个环的大小为 $M_1$ ，那么多少个位置可能被枚举到呢？即方程组
$\begin{cases} x\equiv T_0\pmod{M_0}\\ x\equiv y\pmod{M_1}\\ \end{cases}$
中 $y$ 的可能取值数量。这个值就是 $\frac {\text {lcm}(M_0,M_1)}{M_0} = \frac {M_1}{\gcd (M_0,M_1)}$ ，因此我们可以直接枚举 $T_0+nM_1 \pmod {M_2},n\in [0,\frac {M_1}{\gcd (M_0,M_1)})$ ，并找到最小的 $A [i]$ 。

需要注意的是这里将同余方程组合并为方程 $x\equiv T^\prime\pmod {M^\prime}$ 时的 $M^\prime$ 可能很大，因为 $M^\prime = \text {lcm}(M_0,M_1)$ ，因此直接做需要大数或者 python。

 import sys
from math import gcd
readline = sys.stdin.readline
 
 
n = int(readline())
p = list(map(int, readline().split()))
a = list(map(int, readline().split()))
p = [i - 1 for i in p]
visited = [0 for _ in range(n)]
t0, m0 = 0, 0
 
 
for i in range(n):
    if visited[i]:
        continue
 
    cycle = [a[i]]
    pos = p[i]
    while cycle[0] != a[pos]:
        visited[pos] = 1
        cycle.append(a[pos])
        pos = p[pos]
 
    if m0 == 0:
        t0 = min((cycle[i], i) for i in range(len(cycle)))[1]
        m0 = len(cycle)
        pos = i
        for j in range(m0):
            a[pos] = cycle[(j + t0) % m0]
            pos = p[pos]
    else:
        m1 = len(cycle)
        step = m0
        cnt = m1 // gcd(m0, m1)
        m0 *= cnt
        min_pos = min((cycle[(t0 + step * i) % m1], i) for i in range(cnt))[1]
        t0 += min_pos * step
        t1 = t0
        pos = i
        for j in range(m1):
            a[pos] = cycle[(j + t1) % m1]
            pos = p[pos]
 
 
print(" ".join(map(str, a)))

AtCoder Beginner Contest 371 题解

E – I Hate Sigma Problems

F – Takahashi in Narrow Road

G – Lexicographically Smallest Permutation

分享到微信

发送评论 编辑评论

发送评论编辑评论