AtCoder Beginner Contest 344 A-G 题解

AtCoder Beginner Contest 344

A - Spoiler

Question

删除两个 | 之间的字符

Solution

按照题意模拟即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    string p1, p2;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '|') break;
        p1.push_back(s[i]);
    }

    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == '|') break;
        p2.push_back(s[i]);
    }
    reverse(p2.begin(), p2.end());
    cout << p1 + p2 << endl;
    return 0;
}

B - Delimiter

Question

倒叙输出输入的数

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    vector<int> p;
    int x;
    while (cin >> x) p.push_back(x);
    reverse(p.begin(), p.end());
    for (auto &x : p) cout << x << '\n';
    return 0;
}

C - A+B+C

Question

给出三个集合 $A,B,C$，每次询问给出一个 $X$，问是否存在从 $A,B,C$ 中挑出一个数字 $a,b,c$，使得 $a+b+c=X$

Solution

由于集合大小很小，$n^3$ 得预处理出 $a+b+c$ 可能的所有值，最后 map 判断即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, l;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];
    cin >> l;
    vector<int> c(l);
    for (int i = 0; i < l; i++) cin >> c[i];
    
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 0; k < l; k++)
                mp[a[i] + b[j] + c[k]] = 1;
    
    int q; cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << (mp.count(x) ? "Yes" : "No") << endl;
    }
    return 0;
}

D - String Bags

Question

初始时有一个空字符串 $S$，此外有 $1,2,\cdots ,N$ 个袋子，每个袋子里面有装有一些字符串

袋子 $i$ 里包含 $A_i$ 个字符串，对于每个袋子，你可以选择两种操作中的一种：

• 支付 $1$ 元，从袋子中选择一个字符串，将其连接到 $S$ 的末尾
• 什么也不做

给定一个字符串 $T$， 找到使最终 $S=T$ 所需要的最小金额

Solution

一眼背包问题，定义 $dp[i][j]$ 表示枚举到第 $i$ 个袋子，前 $i-1$ 个袋子已经把 $1\sim j$ 的字符串组成了的最小代价

对于每个袋子中的一个串 $p$，如果 $p=T[j,j+p.size-1]$ ，那么代表可以往后添加 $p$ 字串，于是转移方程为：

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    string T; cin >> T; T = " " + T;
    int n; cin >> n;
    vector<vector<string> > a(n + 1);
    for (int i = 1; i <= n; i++) {
        int m; cin >> m;
        for (int j = 0; j < m; j++) {
            string s; cin >> s;
            a[i].push_back(s);
        }
    }
    vector<vector<int> > dp(n + 1, vector<int>(T.size(), INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < T.size(); j++) {
            for (int k = 0; k < a[i].size(); k++) {
                if (j + a[i][k].size() - 1 >= T.size()) continue;
                if (T.substr(j, a[i][k].size()) == a[i][k])
                    dp[i][j + a[i][k].size() - 1] = min(dp[i][j + a[i][k].size() - 1], dp[i - 1][j - 1] + 1);
            }
        }

        for (int j = 0; j < T.size(); j++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
    }
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, dp[i][T.size() - 1]);
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

E - Insert or Erase

Question

给定长度为 $N$ 的序列 $A=(A_1,A_2,\cdots ,A_N)$。序列 $A$ 的元素各不相同

按照给定序列的顺序处理 $Q$ 个查询：

• 1 x y：在 $A$ 中元素 $x$ 之后插入 $y$
• 2 x：从 $A$ 中移除元素 $x$

输出处理完所有询问后的 $A$

Solution

这是一个非常好的题，如果 $N$ 比较小的话，就是一个链表的典题，在一个元素后插入一个元素，删除一个元素

但是本题的 $N$ 非常大，如果能在短时间内找到链表的 $L[x],R[x]$ 就能快速解题了

而 C++ 的 map 就很好的做到了这一点，使用 map 看成数组记录链表的 $L[x],R[x]$ 之后就是链表的正常操作了

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    unordered_map<int,int> right, left;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (i != 1) left[a[i]] = a[i - 1];
        if (i != n) right[a[i]] = a[i + 1];
    }
    left[a[1]] = -INF; right[a[n]] = INF;
    left[INF] = a[n]; right[-INF] = a[1];
    int q; cin >> q;
    while (q--) {
        int opt; cin >> opt;
        if (opt == 1) {
            int x, y; cin >> x >> y;
            const int L = x, R = right[x];
            left[y] = L; right[y] = R;
            right[L] = y; left[R] = y;
        }
        if (opt == 2) {
            int x; cin >> x;
            const int L = left[x], R = right[x];
            right[L] = R; left[R] = L;
            left.erase(x); right.erase(x);
        }
    }
    int x = right[-INF];
    while (x != INF) {
        cout << x << " ";
        x = right[x];
    }
    return 0;
}

F - Earn to Advance

Question

有一个 $N\times N$ 的网格，初始处于 $(1,1)$ ，金钱数为 $0$

当高桥处于 $(i,j)$ 时，可以在依次行动中执行以下操作之一：

• 留在原地并增加金钱 $P_{i,j}$
• 支付 $R_{i,j}$ 移动到方格 $(i,j+1)$
• 支付 $D_{i,j}$ 移动到方格 $(i+1,j)$

问高桥移动到 $(N,N)$ 的最小行动次数

Solution

高桥移动的过程肯定是移动到一个点，然后攒够足够的钱，然后尽量把一个现有的钱用完去移动到下一个点，然后再在下一个点攒钱

因为如果有两个点 $A,B$ ，有 $P_A<P_B$，那么高桥比起在 $A$ 点攒钱，$B$ 点攒钱肯定要划算一点，所以我们只需要在 $A$ 点攒够足够的到 $B$ 点的钱就好了

所以这样就可以定义 $dp$ 了，定义 $dp[x][y]$ 记录两个参数，第一个就是到 $step$ 即到 $(x,y)$ 的最小步数，第二个是到 $money$ 即到 $(x,y)$ 所剩下钱的最大值，其中要先保证步数最小，且需要在 $(x,y)$ 这点出攒钱

我们只需要枚举上一次攒钱的地方 $(x^{\prime },y^{\prime })$，需要额外的步数也就是是在 $(x^{\prime },y^{\prime })$ 处攒钱的步数为 $dis/P_{x^{\prime },y^{\prime }}$ ，其中 $dis$ 为 $(x,y)$ 到 $(x^{\prime },y^{\prime })$ 需要花费的钱的最小值

那么现在这个状态的步数和剩下的钱也就迎刃而解了

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int main() {
    int n; cin >> n;
    vector<vector<LL> > P(n + 1, vector<LL>(n + 1)), D(n + 1, vector<LL>(n + 1)), R(n + 1, vector<LL>(n + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> P[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < n; j++)
            cin >> R[i][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= n; j++)
            cin >> D[i][j];
    
    auto get_dis = [&](int x, int y) {
        vector<vector<LL> > dis(n + 1, vector<LL>(n + 1, INF));
        dis[x][y] = 0;
        for (int px = n; px >= 1; px--)
            for (int py = n; py >= 1; py--) {
                if (px < x) 
                    dis[px][py] = min(dis[px][py], dis[px + 1][py] + D[px][py]);
                if (py < y)
                    dis[px][py] = min(dis[px][py], dis[px][py + 1] + R[px][py]);
            }
        return dis;
    };

    vector<vector<pll> > dp(n + 1, vector<pll>(n + 1, {INF,INF}));
    dp[1][1] = {0,0};
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++) {
            auto dis = get_dis(x,y);
            for (int px = 1; px <= x; px++)
                for (int py = 1; py <= y; py++){
                    auto [p_step, p_money] = dp[px][py];
                    LL ex_step = (dis[px][py] - p_money + P[px][py] - 1) / P[px][py]; ex_step = max(ex_step, 0LL);
                    LL now_step = p_step + ex_step + (x - px) + (y - py);
                    LL now_money = p_money + ex_step * P[px][py] - dis[px][py];
                    if (now_step < dp[x][y].first || (now_step == dp[x][y].first && now_money > dp[x][y].second))
                        dp[x][y] = {now_step, now_money};
                }
        }
    cout << dp[n][n].first << endl;
    return 0;
}

G - Points and Comparison

Question

在 $xy$ 平面中有 $N$ 个点 $(X_i,Y_i)$

给出了 $Q$ 对整数 $(A_j,B_j)$

定义 $f(A_j,B_j)$ 为满足 $Y_i\ge A_j\times X_i+B_j$ 的 $i$ 的数量

求 $\sum _{j=1}^{Q}f(A_j,B_j)$

Solution

不妨设 $k=A,b=B$ ，发现 $(A_j,B_j)$ 其实表示的是一条直线，而 $(X_i,Y_i)$ 表示的是平面上的一个点

观察 $Y_i\ge k{X}_i+b$，就是点在直线上方或是刚在在直线上

由于 $k,b$ 是固定的，移项 $Y_i-k{X}_i\ge b$ ，也就是说，如果 $Y_i-k{X}_i$ 是递增的，那么 $b$ 就可以二分来找答案了

所以关键在于如何维护 $Y_i-k{X}_i$ 递增，我们把这样的排列叫做排列 $A$

先考虑极端情况 $k=-\mathrm{\infty }$ ，那么 pair<int,int> 正好满足 $A$ 排序

考虑 $A$ 排序上的两个点 $(X_l,Y_l)$，$(X_r,Y_r)$ ，对于一个给定的 $k$

• 如果 $X_l==X_r$，则排序还满足 $Y_l,Y_r$ ，也就是说，$l,r$ 的位置不变
• 如果 $Y_l-k{X}_l>Y_r-k{X}_r⟹\frac{Y_r-Y_l}{X_r-X_l}>k$ 也就是说，$l,r$ 两点组成的斜率大于了 $k$ ，则交换 $l,r$

考虑到没两个点至多只需要交换一次，所以把询问按照 $k$ 从小到大排序，这样子对于每对关系，如果交换了一次，后面总是满足 $A$ 排列的规则的

对于相邻的点 $(X_i,Y_i)$，$(X_{i+1},Y_{i+1})$ 的斜率值放到优先队列里面

如果说对于某一个 $k$ 满足 $k$ 大于其中的某个斜率了，就把对应的两个点交换，然后继续维护优先队列

当满足了对于一个 $k$ 的排列 $A$，就在 $A$ 上面二分来找答案

对于时间复杂度分析，最多存在 $N^2$ 对关系，所以交换操作最多操作 $N^2$ 次，总时间复杂度为 $O(Q(\log Q+\log N)+N^2\log N)$

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pll;

const LL mod = (1ll << 31) - 1;

struct Line {
    LL up, dn;
    int pre, nxt; // 两者的编号
    Line(LL _up, LL _dn, int _pre, int _nxt) {
        if (dn < 0) up = -up, dn = -dn;
        up = _up, dn = _dn, pre = _pre, nxt = _nxt;
    }
    bool operator < (const Line &rhs) const {
        return up * rhs.dn > dn * rhs.up;
    }
    bool operator == (const Line &rhs) const {
        return up == rhs.up && dn == rhs.dn && pre == rhs.pre && nxt == rhs.nxt;
    }
};

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n; cin >> n;
    vector<pll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        auto & [k, b] = a[i];
        cin >> k >> b;
    }
    sort (a.begin() + 1, a.end());
    
    int Q; cin >> Q;
    int G0, Ra, Rb; cin >> G0 >> Ra >> Rb;
    vector<pll> q(Q + 1); vector<LL> G(3 * Q + 1); G[0] = G0;
    for (int i = 1; i <= 3 * Q; i++) 
        G[i] = (48271 * G[i - 1]) % mod;
    for (int i = 1; i <= Q; i++) {
        auto &[A, B] = q[i];
        A = -Ra + (G[3 * i - 2] % (2 * Ra + 1));
        B = -Rb + ((G[3 * i - 1] * mod + G[3 * i]) % (2 * Rb + 1));
    }
    sort (q.begin() + 1, q.end());

    auto make_line = [&] (int i, int j) {
        return Line(a[j].second - a[i].second, a[j].first - a[i].first, i, j);
    };

    priority_queue<Line> s;
    for (int i = 1; i < n; i++)
        if (a[i].first < a[i + 1].first)
            s.push (make_line(i, i + 1));

    LL ans = 0;
    for (int i = 1; i <= Q; i++) {
        auto [k, b] = q[i];
        while (s.size() > 0) {   
            auto it = s.top();
            int dn = it.dn, up = it.up, pre = it.pre, nxt = it.nxt;
            if (!(make_line(pre, nxt) == it)) {s.pop(); continue;} // 说明这个线段已经被更新过了
            if (k * dn < up) break;  // 当 k > 两点的斜率时，交换
            s.pop(); swap(a[pre], a[nxt]);
            if (pre > 1 && a[pre - 1].first < a[pre].first) s.push(make_line(pre - 1, pre));
            if (nxt < n && a[nxt].first < a[nxt + 1].first) s.push(make_line(nxt, nxt + 1));
        }

        int l = 1, r = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            auto [X, Y] = a[mid];
            if ( -k * X + Y >= b) r = mid - 1;
            else l = mid + 1;
        }
        ans += n - r;
    }
    cout << ans << endl;
    return 0;
}