371

A - Jiro

有三兄弟，分别叫 A、B 和 C。他们之间的年龄关系由三个字符 $S_{AB}, S_{AC}, S_{BC}$ 表示，其含义如下：

如果 $S_{AB}$ 是"<"，则 $A$ 比 $B$ 小；如果是">"，则 $A$ 比 $B$ 大。
如果 $S_{AC}$ 是"<"，那么 $A$ 小于 $C$ ；如果是">"，那么 $A$ 大于 $C$ 。
如果 $S_{BC}$ 是 <，那么 $B$ 小于 $C$ ；如果是 >，那么 $B$ 大于 $C$ 。

谁是中间的哥哥，也就是三个哥哥中的老二？

void solve() {
    char a, b, c;cin >> a >> b >> c;
    if (b == '<' && c == '>' || b == '>' && c == '<') {
        cout << "C\n";
    } else if (b == '<' && a == '>' || b == '>' && a == '<') {
        cout << "A\n";
    } else {
        cout << "B\n";
    }
}

B - Taro

在 AtCoder 王国，长子的名字总是太郎。其他人都不叫太郎。长子是每个家庭中最早出生的男孩子。

王国共有 $N$ 个家庭，出生了 $M$ 个婴儿。在 $M$ 个婴儿出生之前， $N$ 个家庭都没有婴儿出生。

婴儿的信息按出生时间顺序排列。

出生在 $A_{i}$ 家庭的 $i$ 个婴儿，如果 $B_{i}$ 为 "M"，则该婴儿为男性；如果为 "F"，则该婴儿为女性。

请判断 $M$ 个婴儿的名字是否叫太郎。

void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1;i <= m;i++) {
        int x;char gen;cin >> x >> gen;
        if (!a[x] && gen == 'M') {
            cout << "Yes\n";a[x] = 1;
        } else {
            cout << "No\n";
        }
    }
}

C - Make Isomorphic

给你简单的无向图 $G$ 和 $H$ ，每个图都有 $N$ 个顶点：顶点 $1$ ， $2$ ， $\dots$ ， $N$ 。图 $G$ 有 $M_{G}$ 条边，它的 $i$ -th 边为 $(1 \leq i \leq M_{G})$ 。

连接顶点 $u_{i}$ 和 $v_{i}$ 。图 $H$ 有 $M_{H}$ 条边，它的 $i$ -th 边 $(1 \leq i \leq M_{H})$ 连接顶点 $a_{i}$ 和 $b_{i}$ 。

您可以在图 $H$ 上执行以下操作，次数不限，可能为零。

选择一对满足 $1 \leq i < j \leq N$ 的整数 $(i, j)$ 。支付 $A_{i, j}$ 日元，如果 $H$ 中的顶点 $i$ 和 $j$ 之间没有边，则添加一条；如果有，则删除。

求使 $G$ 和 $H$ 同构所需的最小总成本。

暴力搜索即可

void solve() {
    int n;cin >> n;
    vector<int> p(n + 1);
    iota(p.begin() + 1, p.end(), 1);
    int m;cin >> m;
    vector<pair<int, int>> g1;
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;g1.push_back({u,v});
    }
    int h;cin >> h;
    set<pair<int, int>>s2;
    for (int i = 1;i <= h;i++) {
        int u, v;cin >> u >> v;
        s2.insert({u,v});
    }
    vector<vector<int>> val(n + 1, vector<int>(n + 1));
    for (int i = 1;i < n;i++) {
        for (int j = i + 1;j <= n;j++) {
            cin >> val[i][j];
        }
    }
    int ans = 1e9;
    do {
        set<pair<int, int>> s1;
        for (auto [x, y] : g1) {
            int l = p[x], ll = p[y];
            if (l > ll)swap(l, ll);
            s1.insert({l,ll});
        }
        int sum = 0;
        for (auto [u, v] : s1) {
            if (!s2.count({u, v})) {
                sum += val[u][v];
            }
        }
        for (auto [u, v] : s2) {
            if (!s1.count({u, v})) {
                sum += val[u][v];
            }
        }
        ans = min(ans, sum);
    } while (next_permutation(p.begin() + 1, p.end()));
    cout << ans << '\n';
}

D - 1 D Country

在一条数线上有 $N$ 个村庄。第 $i$ 个村庄位于坐标 $X_{i}$ 处，有 $P_{i}$ 个村民。

回答 $Q$ 个问题。 $i$ th 查询的格式如下：

给定整数 $L_{i}$ 和 $R_{i}$ ，求生活在坐标 $L_{i}$ 和 $R_{i}$ （含）之间村庄的村民总数。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> x(n + 2), p(n + 1);
    for (int i = 1;i <= n;i++)cin >> x[i];
    x[0] = -1e9 - 1;x[n + 1] = 1e9 + 1;
    for (int i = 1;i <= n;i++)cin >> p[i];
    partial_sum(p.begin() + 1, p.end(), p.begin() + 1);
    int q;cin >> q;
    while (q--) {
        int l, r;cin >> l >> r;
        int a = lower_bound(x.begin(), x.end(), l) - x.begin();
        int b = upper_bound(x.begin(), x.end(), r) - x.begin() - 1;
        cout << p[b] - p[a - 1] << '\n';
    }
}

E - I Hate Sigma Problems

给你一个长度为 $N$ 的整数序列 $A = (A_{1}, A_{2}, \dots, A_{N})$ 。定义 $f (l, r)$ 为：

子序列 $(A_{l}, A_{l + 1}, \dots, A_{r})$ 中不同值的个数。

计算下面的表达式

$\sum_{i = 1}^{N} \sum_{j = i}^{N} f (i, j)$ .

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), lst(n + 1, 0);
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        ans += (i - lst[a[i]]) * lst[a[i]];
        lst[a[i]] = i;
    }
    for (int i = 1;i <= n;i++) {
        ans += (n + 1 - lst[i]) * lst[i];
    }
    cout << ans << '\n';
}

F - Takahashi in Narrow Road

有一条东西向延伸的路，路上有 $N$ 人。这条路从一个叫做原点的点向东西两边无限延伸。

$i$ 个 $(1 \leq i \leq N)$ 人最初位于离原点向东 $X_{i}$ 米的位置。

这些人可以沿着道路向东或向西移动。具体来说，他们可以进行以下任意次数的移动。

选择一个人。如果目的地没有其他人，则将所选的人向东或向西移动 $1$ 米。

他们总共有 $Q$ 个任务，其中 $i$ 个任务 $(1 \leq i \leq Q)$ 如下。

第 $T_{i}$ 个人到达坐标 $G_{i}$ 。

求按顺序完成所有 $Q$ 任务所需的最小总移动次数。

Solution

咋一看有点像前缀和，但想到要动态变化，显然就是线段树。

挖坑...

jiangly 的代码：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    
    std::vector<int> X(N);
    std::map<int, int> f;
    for (int i = 0; i < N; i++) {
        std::cin >> X[i];
        X[i] -= i;
        f[i] = X[i];
    }
    
    i64 ans = 0;
    
    int Q;
    std::cin >> Q;
    
    while (Q--) {
        int T, G;
        std::cin >> T >> G;
        T--;
        G -= T;
        
        auto it = std::prev(f.upper_bound(T));
        int x = it->second;
        
        if (x < G) {
            f[T] = x;
            it = f.find(T);
            while (true) {
                auto nxt = std::next(it);
                if (nxt == f.end()) {
                    ans += 1LL * (N - T) * (G - x);
                    x = G;
                    break;
                }
                if (nxt->second >= G) {
                    ans += 1LL * (nxt->first - T) * (G - x);
                    x = G;
                    break;
                }
                ans += 1LL * (nxt->first - T) * (nxt->second - x);
                x = nxt->second;
                f.erase(nxt);
            }
            it->second = x;
        } else {
            if (T + 1 < N && next(it) == f.end() || std::next(it)->first != T + 1) {
                f[T + 1] = x;
            }
            int p = it->first;
            while (true) {
                if (it == f.begin()) {
                    ans += 1LL * (T + 1) * (x - G);
                    x = G;
                    break;
                }
                auto prv = std::prev(it);
                if (prv->second <= G) {
                    ans += 1LL * (T + 1 - p) * (x - G);
                    x = G;
                    break;
                }
                ans += 1LL * (T + 1 - p) * (x - prv->second);
                x = prv->second;
                p = prv->first;
                f.erase(prv);
            }
            f.erase(it);
            f[p] = x;
        }
    }
    
    std::cout << ans << "\n";
}