AtCoder Beginner Contest 325

这篇具有很好参考价值的文章主要介绍了AtCoder Beginner Contest 325。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

感觉错失了上分机会

A - Takahashi san (abc325 A)

题目大意

给定姓和名,输出尊称,即姓+san

解题思路

按照题意模拟即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    cout << s << " san" << '\n';

    return 0;
}



B - World Meeting (abc325 B)

题目大意

给定\(n\)个地区的公司人数和对应的时区,规定上班时间为 \(9:00-18:00\),现召开一小时会议,上班期间的公司可以参加。问订个时间,能参与的人数的最大值。

解题思路

枚举开会的时间,然后依次判断每个公司能否参加,累计参加人数,取最大值即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<array<int, 2>> a(n);
    for (auto& i : a)
        cin >> i[0] >> i[1];
    int ans = 0;
    auto is_work_time = [](int time) { return time >= 9 && time < 18; };
    for (int i = 0; i < 24; ++i) {
        int sum = 0;
        for (auto& [num, time] : a)
            if (is_work_time((i + time) % 24))
                sum += num;
        ans = max(ans, sum);
    }
    cout << ans << '\n';

    return 0;
}



C - Sensors (abc325 C)

题目大意

给定二维平面,有#.。每个#可以与周围八个格子连成一整体。

问有多少个整体。

解题思路

BFS或者并查集判断一下连通性,最后数连通块即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

class dsu {
  public:
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        sz.resize(n);
        iota(p.begin(), p.end(), 0);
        fill(sz.begin(), sz.end(), 1);
    }

    inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x != y) {
            p[x] = y;
            sz[y] += sz[x];
            return true;
        }
        return false;
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w;
    cin >> h >> w;
    dsu d(h * w);
    auto two2one = [&](int x, int y) { return x * w + y; };
    vector<string> s(h);
    for (int i = 0; i < h; ++i) {
        cin >> s[i];
        for (int j = 1; j < w; ++j) {
            if (s[i][j - 1] == '#' && s[i][j] == '#') {
                d.unite(two2one(i, j - 1), two2one(i, j));
            }
        }
        if (i) {
            for (int j = 0; j < w; ++j) {
                if (s[i - 1][j] == '#' && s[i][j] == '#') {
                    d.unite(two2one(i - 1, j), two2one(i, j));
                }
                if (j > 0 && s[i - 1][j - 1] == '#' && s[i][j] == '#') {
                    d.unite(two2one(i - 1, j - 1), two2one(i, j));
                }
                if (j + 1 < w && s[i - 1][j + 1] == '#' && s[i][j] == '#') {
                    d.unite(two2one(i - 1, j + 1), two2one(i, j));
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if (s[i][j] == '#') {
                ans += d.get(two2one(i, j)) == two2one(i, j);
            }
    cout << ans << '\n';

    return 0;
}



D - Printing Machine (abc325 D)

题目大意

给定\(n\)个物品的出现时间和消失时间。拿一个物品花费 \(1\)的时间。

问最多能拿多少个物品。

解题思路

对于某一时刻,我肯定拿出现的物品中,最早消失的物品。

由此贪心拿即可。

注意每拿完一个物品后要考虑是否有新物品出现。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<array<LL, 2>> a(n);
    for (auto& i : a)
        cin >> i[0] >> i[1];
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    ranges::sort(id, [&](int x, int y) {
        if (a[x][0] != a[y][0])
            return a[x][0] < a[y][0];
        else
            return a[x][1] < a[y][1];
    });
    priority_queue<LL> item;
    LL time = 0;
    int ans = 0;
    auto it = id.begin();
    while (!item.empty() || it != id.end()) {
        if (item.empty())
            time = a[*it][0];
        while (it != id.end() && a[*it][0] <= time) {
            item.push(-(a[*it][0] + a[*it][1]));
            it = next(it);
        }
        while (!item.empty() && -item.top() < time)
            item.pop();
        if (!item.empty() && -item.top() >= time) {
            ++ans;
            ++time;
            item.pop();
        }
    }
    cout << ans << '\n';

    return 0;
}



E - Our clients, please wait a moment (abc325 E)

题目大意

给定一张完全图,从\(1\)号点到 \(n\)号点,一开始打车,在某点可转成坐火车,但不能转回来。

从一个点到另一个点,打车和火车的耗时不同。

问最少耗时。

解题思路

注意到我们肯定是在某一点\(a\)转乘火车,那从\(1\)号点到 \(n\)号点就分成了两部分:

  • 先打车到\(a\)号点(可以看成从\(a\)号点打车到 \(1\)号点)
  • 再乘火车到 \(n\)号点

因此我们可以预处理出,每个点打车到\(1\)号点和坐火车到 \(n\)号点的最短耗时。然后两者的和的最小值就是答案。

而求每个点到 \(1\)号点的耗时和到 \(n\)号点的耗时,相当于分别从 \(1\)号点出发到每个点的耗时,以及从 \(n\)号点出发到每个点的耗时,两次 最短路即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<vector<int>> tu(n, vector<int>(n));
    for (auto& i : tu)
        for (auto& j : i)
            cin >> j;
    LL ans = numeric_limits<LL>::max();
    auto dijkstra = [&](int st, function<LL(int)> E, vector<LL>& dis) {
        dis[st] = 0;
        priority_queue<pair<LL, int>> team;
        team.push({0, st});
        while (!team.empty()) {
            auto [expect, u] = team.top();
            team.pop();
            if (dis[u] != -expect)
                continue;
            for (int v = 0; v < n; ++v) {
                if (v == u)
                    continue;
                if (dis[v] > dis[u] + E(tu[u][v])) {
                    dis[v] = dis[u] + E(tu[u][v]);
                    team.push({-dis[v], v});
                }
            }
        }
    };
    vector<LL> dis0(n, numeric_limits<LL>::max());
    auto dis1 = dis0;
    dijkstra(
        0, [&](int w) { return 1ll * w * a; }, dis0);
    dijkstra(
        n - 1, [&](int w) { return 1ll * w * b + c; }, dis1);
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dis0[i] + dis1[i]);
    }
    cout << ans << '\n';

    return 0;
}



F - Sensor Optimization Dilemma (abc325 F)

题目大意

给定\(n\)个区间长度,有两种操作,

  • 操作一,区间长度减 \(a_1\),成本 \(c_1\),最多用 \(k_1\)
  • 操作二,区间长度减 \(a_2\),成本 \(c_2\),最多用 \(k_2\)

问将每个区间长度减成非正的最小成本。

解题思路

考虑搜索的状态,就是当前的区间操作一的使用次数操作二的使用次数,然后枚举当前区间使用的操作一的次数,复杂度是\(O(nk^3)\)

上述搜索转换成 \(dp\)的形式就是 \(dp[i][j][k]\)表示前\(i\) 个区间,操作一用了\(j\)次,操作二用了 \(k\)次,这一状态是否合法(即 bool型,成本从两个操作次数就能算出来),这难免过于浪费,我们可以把一个状态放到\(dp\)的值里。

即设 \(dp[i][j]\)表示前 \(i\)个区间,操作一用了 \(j\)次时,操作二使用的最小次数(换句话说就是最小成本),转移同样是枚举当前区间的操作一的次数,时间复杂度是 \(O(nk^2)\)

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> d(n);
    for (auto& i : d)
        cin >> i;
    array<int, 2> l{}, c{}, k{};
    for (int i = 0; i < 2; ++i)
        cin >> l[i] >> c[i] >> k[i];
    vector<LL> dp(k[0] + 1, inf);
    dp[0] = 0;
    for (auto& i : d) {
        vector<LL> dp2(k[0] + 1, inf);
        for (int j = 0; j <= k[0]; ++j) {
            for (int u = 0; u <= j; ++u) {
                int v = max(0, (i - u * l[0] + l[1] - 1) / l[1]);
                dp2[j] = min(dp2[j], dp[j - u] + v);
            }
        }
        dp.swap(dp2);
    }
    LL ans = numeric_limits<LL>::max();
    for (int i = 0; i <= k[0]; ++i) {
        if (dp[i] <= k[1])
            ans = min(ans, 1ll * i * c[0] + dp[i] * c[1]);
    }
    if (ans == numeric_limits<LL>::max())
        ans = -1;
    cout << ans << '\n';

    return 0;
}



G - offence (abc325 G)

题目大意

给定一个字符串\(s\)和一个数 \(k\),每次可以将 of连带后面的最多\(k\)个字符删除。

问字符串剩余的最小长度。

解题思路

依次考虑每个前缀,设\(dp[i]\)表示 \(s[1..i]\)经过操作后的最小长度,则 \(dp[i] = min(dp[i - 1] + 1, dp[j - 1])\),其中 \(j\)是满足\(s[j..i]\)能完全被删除的。

从中我们发现需要求一个\(del[i][j]\)表示 \(s[i..j]\)能否被完全删除,这是一个常见的区间\(dp\)。考虑转移,分两种情况

  • 一个就是常规的转移,即\(del[i][j] |= del[i][l] & del[l+1][j]\)
  • 另一个是考虑进行一次操作,即\(s[i]=o\),找到\(s[l]=f\)的地方,\(s[l+1..j]\)的进行操作后的最短长度 \(\leq k\),这样就可以通过一次操作就把 \(del[i][j]\)完全删除。

\(s[i..j]\)的进行操作后的最短长度为\(mink[i][j]\),其转移就两种:

  • 一个就是常规的转移,即\(mink[i][j] = \min(mink[i][l] + mink[l+1][j])\)
  • 另一个就是当\(del[i][j]=true\)时, \(mink[i][j]=0\)

这样 \(dp\)数组就可以转移求答案了。

其实最后发现 \(mink[0][n-1]\)就是答案。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    int k;
    cin >> s >> k;
    vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1, 0));
    vector<vector<int>> mink(s.size() + 1, vector<int>(s.size() + 1, 0));
    for (int i = 0; i < dp.size(); ++i)
        for (int j = i + 1; j < dp.size(); ++j)
            dp[j][i] = 1;
    for (int j = 0; j < s.size(); ++j) {
        for (int i = j; i >= 0; --i) {
            mink[i][j] = j - i + 1;
            for (int l = i; l <= j; ++l)
                dp[i][j] |= (dp[i][l] & dp[l + 1][j]);

            for (int l = i; l <= j; ++l)
                if (s[i] == 'o' && s[l] == 'f' && dp[i + 1][l - 1] &&
                    mink[l + 1][j] <= k) {
                    dp[i][j] = true;
                }

            if (dp[i][j])
                mink[i][j] = 0;
            else {
                for (int l = i; l <= j; ++l) {
                    mink[i][j] = min(mink[i][j], mink[i][l] + mink[l + 1][j]);
                }
            }
        }
    }
    cout << mink[0][s.size() - 1] << '\n';
    return 0;

    vector<int> dp2(s.size(), 0);
    dp2[0] = 1;
    for (int i = 1; i < s.size(); ++i) {
        dp2[i] = dp2[i - 1] + 1;
        for (int j = 0; j < i; ++j) {
            if (dp[j][i]) {
                if (j)
                    dp2[i] = min(dp2[i], dp2[j - 1]);
                else
                    dp2[i] = 0;
            }
        }
    }
    cout << dp2.back() << '\n';

    return 0;
}


可以发现这是一道区间\(dp\),从它操作结果可以合并可以感受出来。即设 \(dp[l][r]\)表示子串 \(s[l..r]\)经过操作后的最小长度。

其中一个转移就是\(dp[l][r] = min(dp[l][i] + dp[i + 1][r])\),就是两个区间的合并。

还有一个转移就是经过操作的转移,可以发现这类转移都可以归到\(s[l]=o\)的情况,因为如果 \(s[l] \neq o\)的话,其实可以归成上面这种情况。如果 \(s[l]=o\),那么就找一个 \(s[i]=f\),如果 \(dp[l+1][i-1] = 0\),即完全删除,可以拼接出一个新的 \(of\),那么 \(dp[l][r] = max(dp[i + 1][r] - k, 0)\),即一个前缀被删除了,剩下的字符最多可再减去\(k\)个字符。

时间复杂度都是\(O(n^3)\)文章来源地址https://www.toymoban.com/news/detail-711399.html

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    int k;
    cin >> s >> k;
    vector<vector<int>> dp(s.size() + 1, vector<int>(s.size() + 1, 0));
    for (int r = 0; r < s.size(); ++r)
        for (int l = r; l >= 0; --l) {
            dp[l][r] = r - l + 1;
            for (int m = l; m < r; ++m)
                dp[l][r] = min(dp[l][r], dp[l][m] + dp[m + 1][r]);
            if (s[l] == 'o')
                for (int m = l + 1; m <= r; ++m) {
                    if (s[m] == 'f' && dp[l + 1][m - 1] == 0)
                        dp[l][r] = min(dp[l][r], max(0, dp[m + 1][r] - k));
                }
        }
    cout << dp[0][s.size() - 1] << '\n';

    return 0;
}



到了这里,关于AtCoder Beginner Contest 325的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • AtCoder Beginner Contest 331

    给定一年的月数和一月的天数,以及当天日期,问次日的日期。 一个简单的进制加法运算,超出进制数则向前加一。 神奇的代码 给定 (6,8,12) 根胡萝卜的价格。 问买至少 (n) 根胡萝卜的最小花费。 由于 (n) 只有 (100) ,花 (O(n^3)) 枚举这三类胡萝卜的购买次数,取花费最

    2024年02月05日
    浏览(43)
  • AtCoder Beginner Contest 302

    给定怪物的血量 (a) 和你每次攻击扣除的血量 (b) ,问打多少次怪物才会死。 答案即为 (lceil frac{a}{b} rceil = lfloor frac{a + b - 1}{b} rfloor) 神奇的代码 给定一个二维网格,格子上有字母,找到一连串位置,使得其字符串为 (snuke) ,要求这一连串位置俩俩相邻,即有共边或

    2024年02月05日
    浏览(78)
  • AtCoder Beginner Contest 304

    依次给定每个人的姓名和年龄,排成一圈。从年龄最小的人依次输出姓名。 找到年龄最小的,依次输出就好了。 神奇的代码 给定一个数字,如果其超过三位数,则仅保留其最高三位,低位数字全部置为0。 读一个 string ,直接赋值即可。 神奇的代码 给定 (n) 个人的坐标,第

    2024年02月07日
    浏览(39)
  • AtCoder Beginner Contest 329

    劳累一天不该写题,启发式合并都写错了 给定一个字符串,将每个字符输出出来,中间留个空格。 遍历输出即可。 神奇的代码 给定一个数组,找出次大的数。 遍历一下,从非最大的数求一个最大值即可。 神奇的代码 给定一个字符串,问有多少个连续的子串,其由一个字母

    2024年02月05日
    浏览(75)
  • AtCoder Beginner Contest 339

    给一个网址,问它的后缀是多少。 找到最后的\\\'.\\\'的位置,然后输出后面的字符串即可。 python 可以一行。 神奇的代码 二维网格,上下左右相连,左上原点。初始全部为白色,位于原点,面朝上。 进行 (n) 次操作,每次操作,将当前格子颜色黑白反转,然后 如果原来是白色

    2024年02月19日
    浏览(31)
  • AtCoder Beginner Contest 340

    给定等差数列的 首项 、 末项 、 公差 。 输出这个等差数列。 从 首相 依次累加 公差 到 末项 即可。 神奇的代码 依次进行 (Q) 次操作,分两种。 1 x ,将 x 放到数组 (a) 的末尾。 2 k ,输出数组 (a) 的倒数第 (k) 项。 用 vector 模拟即可,操作 2 可快速寻址访问。 神奇的代

    2024年02月19日
    浏览(33)
  • AtCoder Beginner Contest 314

    怎么好多陌生单词 审核怎么这么逆天,半小时还没审完 给定 (pi) 的值以及数 (n) ,要求保留 (n) 位小数输出,不四舍五入。 字符串形式储存然后截取末尾即可。 神奇的代码 (n) 个人玩轮盘赌游戏,简单说就是一个转盘有 (37) 个数字以及一个箭头,箭头会等概率停在某

    2024年02月13日
    浏览(40)
  • AtCoder Beginner Contest 308

    这几天在收拾东西搬家,先附上代码,晚点补上题解 补完了 感觉这次FG都写不太明白 给定八个数,问是否满足以下要求: 不严格升序 每个数在 (100 sim 675) 之间 每个数都是 (25) 的倍数 依次对每个数判断是否符合这三个条件即可。 神奇的代码 高桥吃 (n) 份寿司,寿司分

    2024年02月11日
    浏览(30)
  • AtCoder Beginner Contest 345

    给定一个字符串,问是不是形如 ======...==== 的字符串。 根据长度构造出期望的字符串,再判断是否相等即可。 神奇的代码 给定 (a) ,输出 (lceil frac{a}{10} rceil) 上下取整的转换, (lceil frac{a}{10} rceil = lfloor frac{a + 9}{10} rfloor) 。用下取整即可。 Python 的 // 是下取证,

    2024年03月21日
    浏览(36)
  • AtCoder Beginner Contest 309

    感觉F写了个乱搞做法 给定一个 (3 times 3) 的网格,以及两个数字。 问这两个数字是否 水平相邻 。 求出两个数字的横纵坐标,看是否横坐标相同,纵坐标差一即可。 读题不仔细,开题就WA了。 神奇的代码 给定一个矩形。将最外围的数字顺时针旋转一格。 可以模拟一个指针

    2024年02月13日
    浏览(32)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包