首页 > 其他分享 >AtCoder Beginner Contest 344 A-G 题解

AtCoder Beginner Contest 344 A-G 题解

时间：2024-03-12 14:35:01浏览次数：30  
标签：AtCoder int 题解 py cin 344 vector dp dis

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\) 字串，于是转移方程为：

\[dp[i][j+p.size-1]=\min\{dp[i-1][j]\} \]

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',y')\)，需要额外的步数也就是是在 \((x',y')\) 处攒钱的步数为 \(dis/P_{x',y'}\) ，其中 \(dis\) 为 \((x,y)\) 到 \((x',y')\) 需要花费的钱的最小值

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

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\limits_{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 - kX_i \ge b\) ，也就是说，如果 \(Y_i-kX_i\) 是递增的，那么 \(b\) 就可以二分来找答案了

所以关键在于如何维护 \(Y_i-kX_i\) 递增，我们把这样的排列叫做排列 \(A\)

先考虑极端情况 \(k=-\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-kX_l > Y_r-kX_r\Longrightarrow \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;
}

标签：AtCoder,int,题解,py,cin,344,vector,dp,dis
From： https://www.cnblogs.com/martian148/p/18068219

相关文章

  • LeetCode - 高频SQL50题（基础版）部分题解（上）
    1581.进店却未进行过交易的顾客原题：https://leetcode.cn/problems/customer-who-visited-but-did-not-make-any-transactions/题意：有一些顾客可能光顾了购物中心但没有进行交易。请你编写一个解决方案，来查找这些顾客的ID（customer_id），以及他们只光顾不交易的次数（count_no_trans......
  • node: /lib64/libm.so.6: version `GLIBC_2.27‘ not found问题解决方案
    场景centos7服务器使用nvm安装的node之后，只要使用npm或者node，均会出现以下问题。npm-vnode:/lib64/libm.so.6:version`GLIBC_2.27'notfound(requiredbynode)node:/lib64/libc.so.6:version`GLIBC_2.25'notfound(requiredbynode)node:/lib64/libc.so.6:ver......
  • 开摆题解
    开摆--更新ing没有详解（大概目录开摆--更新ingA题B题C题D题E题A题不配文字讲解了，具体的直接问我本人吧前缀和视频C++代码voidsolve(){intn,m,w,x,i,ans=0;cin>>n;vector<int>qwq(49);//前缀和数组for(i=0;i<n;++i){cin>......
  • Toyota Programming Contest 2024#3（AtCoder Beginner Contest 344）
    C先预处理出三个数组能拼出的数，存放到map中。查询的时候只需要看这个数是否出现在map里即可。时间复杂度\(O(n^3\logv+Q\logv)\)，\(n\leq100\)，\(\logv\)是map的时间复杂度。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=3e......
  • ABC344 D-F
    ABC344D-F**D-StringBags**标签动态规划DP思路这一题可以想到使用\(DP\)。那么\(f[i][j]\)就表示在前\(i\)个包里选择长度为\(j\)的字符串最小钱数。这里的字符串时字符串\(T\)的子串那么状态转移方程就是f[i+1][j+s.size()]=min(f[i+1][j+s.size()],f[i]......
  • rosdep update超时问题解决
    此问题的解决也适用ros11、初始化$sudorosdepinit2、下载rosdistro到本地$gitclonehttps://github.com/ros/rosdistro.git3、修改以下文件,将其url指向本地（1）文件1：20-default.list地址路径：/etc/ros/rosdep/sources.list.d/20-default.list原来内容：#os-specificl......
  • 随机逆序对 题解
    题意给定$1\simn$的排列$a_{1...n}$。在上面进行依次如下操作：首先在$[1,n]$​中选取一个子序列(可以为空);然后将这个子序列内的数重新排列。两个操作不同，当且仅当选取的子序列不同或者重新排列的方式不同。对于所有不同的操作，求他们产生的排列的逆序对个数和，答案......
  • AtCoder Beginner Contest 344
    B-Delimiter难度:⭐题目大意把一个数组倒序输出;解题思路没啥好说的;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'usingnamespacestd;constintN=4e6+......
  • 【蓝桥-大试牛刀7-最短路专场】题解
    最短路1floyd说白了就是个暴力，用三层循环枚举所有路径，然后留下权值最小的一条大概就长这个样for(中转点k) for(起点i) for(终点j) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);注意这个题的数据有重边，输入的时候留下最小的，这样就做完了intd[N][N];voidsolve(){......
  • LeetCode 128.最长连续序列 Python题解
    leetcode128题最长连续序列分享解题思路，使用哈希表算法......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99