Atcoder ABC437游记

上一场没写因为实在太唐了，但这场挺难的，rating给我 $\pm 0$ 就很尴尬，差两分上蓝。

---

题目

题目评级

A.Feet

题目描述

$1$ 英尺是 $12$ 英寸。

$A$ 英尺 $B$ 英寸等于多少英寸？

思路

语法题

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int a, b;
    cin >> a >> b;
    cout << a * 12 + b;
    return 0;
}

---

B.Tombola

题目描述

有一个行数为 $H$ 列数为 $W$ 的网格。每个方格上都写有一个整数，这些整数是不同的。从上面起第 $i$ 行，从左边起第 $j$ 列的方格上写着整数 $A_{i,j}$ 。

现在，主持人喊出了 $N$ 个不同的整数 $B_1, \dots, B_N$ 。

如果你找出每一行，主机调出的整数中有多少个包含在这一行中，这些整数中的最大值是多少？

思路

英语不好的鬼子来考察你英语能力啦

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n, m;
    cin >> n >> m;
    int T;
    cin >> T;
    
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    vector<int> b(T);
    for (int i = 0; i < T; i++) {
        cin >> b[i];
    }
    set<int> st(b.begin(), b.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < m; j++) {
            if (st.count(a[i][j])) {
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans;
    return 0;
}

---

C.Reindeer and Sleigh 2

题目描述

有 $N$ 头驯鹿和一个雪橇。 $i$ 只驯鹿的重量是 $W_i$ ，力量是 $P_i$ 。

每只驯鹿可以选择 "拉雪橇 "或 “坐雪橇”。这里，拉雪橇的驯鹿的总力量必须大于或等于坐雪橇的驯鹿的总重量。最多可以有多少只驯鹿坐上雪橇？

给你 $T$ 个测试案例。请逐一解答。

思路

勾史贪心。

我们可以先假设所有的鹿都在拉雪橇，然后从前往后考虑每只鹿确定了拉雪橇的情况，每次判断一下可不可行，不可行的话重量和力量加起来最小的抓出来当苦力，这里哪些鹿在雪橇上可以用set维护。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    function<bool(pair<int, int>, pair<int, int>)> cmp = [&] (pair<int, int> a, pair<int, int> b) -> bool {
        return (a.first + a.second) < (b.first + b.second);
    };
    sort(a.begin(), a.end(), cmp);
    int ans = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += a[i].second;
    }
    multiset<int, greater<int>> st;
    int cntw = 0;
    for (int i = 0; i < n; i++) {
        st.insert(a[i].first);
        cntw += a[i].first;
        cnt -= a[i].second;
        while (!st.empty() && cnt < cntw) {
            auto it = st.begin();
            cntw -= *it;
            st.erase(it);
        }
        ans = max(ans, (int)st.size());
    }
    cout << ans << '\n';
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

---

D.Sun of Differences

题目描述

给你一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$ 和一个长度为 $M$ 的正整数序列 $B = (B_1, B_2, \dots, B_M)$ 。

求以 $998244353$ 为模数的 $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} |A_i - B_j|$ 的值。

思路

把 $b$ 排序之后挨个看 $a$ 里面的元素 $x$ ，对于每个下标 $i$ 答案只可能会有 $b_i - x$ 或者 $x - b_i$两种，前一个是 $b_i \geq x$，后一个是 $b_i \leq x$，可以直接二分出第一个大于 $x$ 的位置再用前缀和辅助计算即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    sort(b.begin(), b.end());
    vector<int> pre(m + 1, 0);
    for (int i = 0; i < m; i++) {
        pre[i + 1] = (pre[i] + b[i]) % mod;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int pos = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
        ans = ((ans + (((pos * a[i]) % mod - pre[pos]) % mod + mod) % mod) % mod + 
        ((pre[m] - pre[pos] + mod) % mod - ((m - pos) * a[i]) % mod + mod) % mod) % mod;
    }
    cout << ans;
    return 0;
}

---

E.Sort Arrays

题目描述

有 $N+1$ 个序列 $A_0, A_1, \ldots, A_{N}$ 。 $A_i$ 的定义如下：

• $A_0$ 是空序列。
• $A_i\ (1\leq i\leq N)$ 是在序列 $A_{x_i}\ (0\leq x_i\lt i)$ 的末尾追加整数 $y_i$ 得到的序列。

求满足以下条件的 $(1,2,\ldots,N)$ 的排列 $P=(P_1, P_2,\ldots,P_N)$ ：

• 就 $i = 1,2,\ldots,N-1$ 而言，以下条件之一成立：
  • $A_{P_i}$ 在词序上小于 $A_{P_{i+1}}$ 。
  • $A_{P_i}= A_{P_{i+1}}$ 和 $P_i\lt P_{i+1}$ 。

换句话说，当 $A_1,A_2,\ldots,A_N$ 按词典顺序排列时（当有多个相等的序列时，先排列指数小的序列）， $P$ 是出现在该排列中的指数序列。

什么是序列的词典顺序？

如果以下两个条件之一成立，则序列 $S = (S_1,S_2,\ldots,S_{|S|})$ 在词法上**小于序列 $T = (T_1,T_2,\ldots,T_{|T|})$ 。这里， $|S|$ 和 $|T|$ 分别表示 $S$ 和 $T$ 的长度。

1. $|S| \lt |T|$ 和 $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$ 。
2. 存在一个整数 $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ ，使得下面两个条件都成立：
   • $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$
   • $S_i$ 在数值上小于 $T_i$ 。

思路

很显然的字典树，但是我怎么死了 $3$ 发 www

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
    map<int, int> edges; 
    vector<int> idx;
}trie[333333];
void dfs(int x, vector<int>& ans)
{
    for (auto nex : trie[x].idx) {
        ans.push_back(nex);
    }
    for (auto nex : trie[x].edges) {
        dfs(nex.second, ans);
    }
}
int cnt = 0;
signed main()
{
    int n;
    cin >> n;
    vector<int> pos(n + 1);
    pos[0] = 0;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        int u = pos[x]; 
        if (trie[u].edges.find(y) == trie[u].edges.end()) {
            trie[u].edges[y] = ++cnt;
        }
        pos[i] = trie[u].edges[y];
        trie[trie[u].edges[y]].idx.push_back(i);
    }
    vector<int> ans;
    dfs(0, ans); 
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

---

F.Manhattan Chirstmas Tree 2

题目描述

二维平面上有 $N$ 棵圣诞树。棵圣诞树。 $i$ /- $(1\le i\le N)$ 棵圣诞树位于坐标 $(X_i,Y_i)$ 处。圣诞树位于坐标 $(X_i,Y_i)$ 处。

给你 $Q$ 个查询。请按顺序处理这些查询。每个查询都是下列查询之一：

• 键入 $1$ ：以 1 i x y 的形式给出。将 $i$ -圣诞树的坐标改为 $(x,y)$ 。
• 输入 $2$ : 以 2 L R x y 的形式给出。输出从坐标 $(x,y)$ 到第 $L,L+1,\ldots,R$ 棵圣诞树中最远的圣诞树的曼哈顿距离。

这里，坐标 $(x_1,y_1)$ 与坐标 $(x_2,y_2)$ 之间的曼哈顿距离定义为 $|x_1-x_2|+|y_1-y_2|$ 。

思路

线段树但是维护的时候需要转一下坐标轴

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{
    int mx1, mx2, mn1, mn2;
    node() : mx1(LLONG_MAX), mx2(LLONG_MIN), mn1(LLONG_MAX), mn2(LLONG_MIN) {} 
    node(int x, int y) {
        mx1 = mx2 = x + y;
        mn1 = mn2 = x - y;
    }
}bit[200005 << 2];
int n;
node merge(node a, node b)
{
    node res;
    res.mx1 = min(a.mx1, b.mx1);  
    res.mx2 = max(a.mx2, b.mx2);  
    res.mn1 = min(a.mn1, b.mn1);  
    res.mn2 = max(a.mn2, b.mn2);  
    return res;
}
vector<int> a, b;
void build(int x, int L, int R)
{
    if (L == R) {
        bit[x] = node(a[L], b[L]);
    } else {
        int mid = (L + R) / 2;
        build(2 * x, L, mid);
        build(2 * x + 1, mid + 1, R);
        bit[x] = merge(bit[2 * x], bit[2 * x + 1]);
    }
}
void update(int x, int L, int R, int k, int p1, int p2)
{
    if (L == R) {
        bit[x] = node(p1, p2);
    } else {
        int mid = (L + R) / 2;
        if (k <= mid) {
            update(2 * x, L, mid, k, p1, p2);
        } else {
            update(2 * x + 1, mid + 1, R, k, p1, p2);
        }
        bit[x] = merge(bit[2 * x], bit[2 * x + 1]);
    }
}
node query(int x, int L, int R, int l, int r)
{
    if (r < L || R < l) {
        return node();
    }
    if (l <= L && R <= r) {
        return bit[x];
    }
    int mid = (L + R) / 2;
    return merge(query(2 * x, L, mid, l, r), query(2 * x + 1, mid + 1, R, l, r));
}
signed main()
{
    cin >> n;
    int T;
    cin >> T;
    a.resize(n + 1);
    b.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    build(1, 1, n);
    while (T--) {
        int ch;
        cin >> ch;
        if (ch == 1) {
            int k, x, y;
            cin >> k >> x >> y;
            a[k] = x;
            b[k] = y;
            update(1, 1, n, k, x, y);
        } else {
            int l, r, x, y;
            cin >> l >> r >> x >> y;
            node res = query(1, 1, n, l, r);
            int ans = LLONG_MIN;
            ans = max(ans, res.mx2 - (x + y));
            ans = max(ans, (x + y) - res.mx1);
            ans = max(ans, res.mn2 - (x - y));
            ans = max(ans, (x - y) - res.mn1);
            cout << ans << '\n';
        }
    }
    return 0;
}