AtCoder Beginner Contest 334

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

A - Christmas Present (abc334 A)

题目大意

给定两个数\(b,g(b \neq g)\),如果 \(b\)大则输出 Bat,否则输出Glove

解题思路

比较大小输出即可。

神奇的代码
#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 a, b;
    cin >> a >> b;
    if (a > b)
        cout << "Bat" << '\n';
    else
        cout << "Glove" << '\n';

    return 0;
}



B - Christmas Trees (abc334 B)

题目大意

给定\(a,m,l,r\),问有多少个整数 \(k\)满足 \(l \leq a + mk \leq r\).

解题思路

对不等式化简一下即为
\(\frac{l - a}{m} \leq k \leq \frac{r - a}{m}\)
的整数个数。

答案就是\(\lfloor \frac{r - a}{m} \rfloor - \lceil \frac{l - a}{m} \rceil + 1\)

C++直接用floor,ceil函数貌似有精度问题。

上下取整的转换是\(\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor\)

C++的取整都是向0取整(舍尾),在负数的时候不适用,因此代码里先把它们全部平移到正数。

神奇的代码
#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);
    LL a, m, l, r;
    cin >> a >> m >> l >> r;
    l -= a;
    r -= a;
    if (l < 0) {
        LL shift = -l;
        shift += m - shift % m;
        l += shift;
        r += shift;
    }
    LL R = r / m;
    LL L = (l + m - 1) / m;
    LL ans = R - L + 1;

    cout << ans << '\n';

    return 0;
}



C - Socks 2 (abc334 C)

题目大意

给定\(n\)双袜子,编号 \(1-n\),但丢失了其中 \(k\)双袜子各一只。

现重新俩俩配对,使得每双袜子的编号差的和最小。

解题思路

考虑原本成双的袜子,如果拆开来配对单个袜子的话,发现不会更优。因此仅考虑单个袜子的。

单个袜子的按照编号从小到大一一配对,容易发现这是最小的了,任意交换两个配对方式都会导致差的和更大。

如果是偶数只则完美匹配,如果是奇数只,则需舍弃一只,枚举舍弃的这只(容易发现舍弃了这只后,左边数量一定是偶数,右边数量一定是偶数的情况才更优),剩下的就是从头一一匹配,而从尾一一匹配,这个可以事先预处理得到。时间复杂度是\(O(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, k;
    cin >> n >> k;
    vector<int> a(k);
    for (auto& i : a)
        cin >> i;
    LL ans = 0;
    if (~k & 1) {
        for (int i = 0; i < k; i += 2)
            ans += a[i + 1] - a[i];
    } else if (k > 1) {
        LL sum = 0;
        for (int i = k - 1; i > 0; i -= 2)
            sum += a[i] - a[i - 1];
        ans = sum;
        for (int i = 0; i < k - 1; i += 2) {
            sum -= a[i + 2] - a[i + 1];
            sum += a[i + 1] - a[i];
            ans = min(ans, sum);
        }
    }
    cout << ans << '\n';

    return 0;
}



D - Reindeer and Sleigh (abc334 D)

题目大意

\(n\)个雪橇,第 \(i\)个雪橇需要 \(r_i\)只麋鹿拉。

给定 \(q\)个询问,对于每个询问给定 \(x\)只麋鹿,问最多能拉多少个雪橇。

解题思路

很显然我们优先拉需要的麋鹿数量少的雪橇。

因此先对拉雪橇所需的麋鹿数量\(r_i\)拍个序,找到最大的\(k\)使得\(\sum_{i=1}{k}r_i \leq x\)

在一个关于\(r_i\)的前缀和数组上 二分找到对应位置即可。时间复杂度是\(O(q\log 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, q;
    cin >> n >> q;
    vector<LL> r(n);
    for (auto& i : r)
        cin >> i;
    ranges::sort(r);
    partial_sum(r.begin(), r.end(), r.begin());
    while (q--) {
        LL x;
        cin >> x;
        auto pos = ranges::upper_bound(r, x) - r.begin();
        cout << pos << '\n';
    }

    return 0;
}



E - Christmas Color Grid 1 (abc334 E)

题目大意

给定包含 .#的二维网格。现随机将一个 .改成#,问#的期望连通块数量。

解题思路

由于网格大小只有\(1000 \times 1000\),可以枚举每个 .,计算它变成#后的影响。

考虑如何计算影响,首先计算出原图的所有#的连通块\(block\),可以用并查集或者BFS。然后考虑当一个.变成#后,它能连通多少个不同的连通块。很显然四个方向,如果有\(x\)个不同的连通块,那么此时连通块数量就变成\(block + 1 - x\)

所有情况求和,再除以 .的数量即为答案。

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

const int mo = 998244353;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    int red = 0;
    for (auto& i : s) {
        cin >> i;
        red += ranges::count(i, '.');
    }
    vector<vector<int>> own(h, vector<int>(w, 0));
    int block = 0;
    array<int, 4> dx{1, -1, 0, 0};
    array<int, 4> dy{0, 0, 1, -1};
    auto BFS = [&](int x, int y) {
        queue<array<int, 2>> team;
        team.push({x, y});
        block++;
        own[x][y] = block;
        while (!team.empty()) {
            auto [x, y] = team.front();
            team.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w ||
                    s[nx][ny] != '#' || own[nx][ny])
                    continue;
                own[nx][ny] = block;
                team.push({nx, ny});
            }
        }
    };
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            if (s[i][j] == '#' && !own[i][j])
                BFS(i, j);
        }
    LL ans = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            if (s[i][j] == '.') {
                set<int> nei;
                for (int k = 0; k < 4; ++k) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < 0 || y < 0 || x >= h || y >= w || s[x][y] == '.')
                        continue;
                    nei.insert(own[x][y]);
                }
                ans += block + 1 - int(nei.size());
            }
        }
    ans = ans % mo * inv(red) % mo;
    cout << ans << '\n';

    return 0;
}



F - Christmas Present 2 (abc334 F)

题目大意

二维平面,起点\(st\),依次去\(n\)个点送礼物,一次只能携带最多 \(k\)个礼物。只能回起点补充礼物。

问从起点出发,送完 \(n\)个点的礼物,并回到起点的最小距离和。

解题思路

考虑当前已经送完了前\(i\)点的礼物,那我接下来的决策就是决定送多少(\(\leq k\))个礼物 ,不同的决策就有一个距离代价。

由此设\(dp[i]\)表示送完前 \(i\)个点的礼物,并回到起点的最小距离和。考虑上次送了几个礼物,得转移式:

\(dp[i] = \min_{i - k \leq j \leq i - 1}(dp[j] + dis[st \to j+1] + dis[j + 1 \to ... \to i] + dis[i \to st])\)

时间复杂度是\(O(n^2)\)

把中间的\(dis[j+1 \to ... \to i]\)用距离前缀和代替 \(sum[i] - sum[j + 1]\),并把与 \(j\)无关的项抽出来,得

\(dp[i] = \min_{i - k \leq j \leq i - 1}(dp[j] + dis[st \to j+1] - sum[j + 1]) + sum[i] + dis[i \to st]\)

中间是一个关于数组\(cost[j] = dp[j] + dis[st \to j+1] - sum[j + 1]\)的滑动窗口取 \(\min\),用单调队列优化即可。

时间复杂度是 \(O(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, k;
    cin >> n >> k;
    vector<array<int, 2>> pos(n + 1);
    for (auto& i : pos)
        cin >> i[0] >> i[1];
    vector<double> sum(n + 2);
    auto calc = [&](array<int, 2>& a, array<int, 2>& b) {
        LL dx = a[0] - b[0];
        LL dy = a[1] - b[1];
        return sqrt(dx * dx + dy * dy);
    };
    vector<double> dis(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + calc(pos[i], pos[i - 1]);
        dis[i] = calc(pos[i], pos[0]);
    }
    deque<pair<double, int>> team;
    vector<double> dp(n + 1);
    team.push_back({dp[0] + dis[1] - sum[1], 0});
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        while (!team.empty() && team.front().second < i - k) {
            team.pop_front();
        }
        dp[i] = team.front().first + sum[i] + dis[i];
        double cur = dp[i] + dis[i + 1] - sum[i + 1];
        while (!team.empty() && team.back().first >= cur)
            team.pop_back();
        team.push_back({cur, i});
    }
    cout << fixed << setprecision(10) << dp.back() << '\n';

    return 0;
}



G - Christmas Color Grid 2 (abc334 G)

题目大意

给定包含 .#的二维网格。现随机将一个 #改成.,问#的期望连通块数量。

解题思路

由于网格大小只有\(1000 \times 1000\),可以枚举每个 #,计算它变成.后的影响。

枚举#,当它变成 .,原本所在的#连通块可能会被拆分成若干块,也可能不会被拆开,这取决于这个点是否是关键点,或者说割点

我们需要一个描述这样性质的信息,即tarjan里的dfnlow。其中dfn[i]表示第一次访问该点的时间,low[i]表示从该点往下走,通过返祖边能往上返回的最早的节点的时间。

注意一张图可以看作是一颗DFS树和一些返祖边构成,而这些返祖边就是会造成连通块不会被拆开的原因。

因此先对原图进行DFS,得到每个点的dfnlow。然后依次考虑删除每个点\(u\),对于其儿子点 \(v\),考虑其是否还和点\(u\)的父亲往上部分连通。

根据定义,如果 \(dfn[u] \leq low[v]\),说明 \(v\)子树无法回溯到点 \(u\)的父亲往上,也就和上面断开了,此时连通块数量会\(+1\)。。

因此,记\(dfs[u] \leq low[v]\)\(v\)的数量为 \(c\)

如果当前点 \(u\)是根,则删去该点后,连通块 数量会增加\(c-1\),否则就增加 \(c\)

这样考虑一个#后的连通块数量就能\(O(1)\)算的,所有情况累加,除以#数量即为答案。文章来源地址https://www.toymoban.com/news/detail-760808.html

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

const int mo = 998244353;

long long qpower(long long a, long long b) {
    long long qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x) { return qpower(x, mo - 2); }

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    int greeen = 0;
    for (auto& i : s) {
        cin >> i;
        greeen += ranges::count(i, '#');
    }
    vector<int> dfn(h * w), low(h * w);
    int time = 0;
    int block = 0;
    auto tr = [&](int x, int y) { return x * w + y; };
    auto invtr = [&](int x) -> array<int, 2> { return {x / w, x % w}; };
    array<int, 4> dx{1, -1, 0, 0};
    array<int, 4> dy{0, 0, 1, -1};
    vector<vector<int>> son(h * w);
    vector<int> f(h * w);
    auto dfs = [&](auto self, int u, int fa) -> void {
        ++time;
        f[u] = fa;
        dfn[u] = low[u] = time;
        auto [x, y] = invtr(u);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= h || ny >= w || s[nx][ny] == '.')
                continue;
            int nu = tr(nx, ny);
            if (nu == fa)
                continue;
            if (dfn[nu])
                low[u] = min(low[u], dfn[nu]);
            else {
                son[u].push_back(nu);
                self(self, nu, u);
                low[u] = min(low[u], low[nu]);
            }
        }
    };
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            auto it = tr(i, j);
            if (s[i][j] == '#' && !dfn[it]) {
                ++block;
                dfs(dfs, it, it);
            }
        }
    LL ans = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            if (s[i][j] == '#') {
                int cnt = 0, u = tr(i, j);
                for (auto& v : son[u]) {
                    cnt += (dfn[u] <= low[v]);
                }
                ans += block - 1 + cnt + (f[u] != u);
            }
        }
    ans = ans % mo * inv(greeen) % mo;
    cout << ans << '\n';

    return 0;
}



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

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

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

相关文章

  • AtCoder Beginner Contest 314

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

    2024年02月13日
    浏览(36)
  • AtCoder Beginner Contest 326

    100楼层,一次可以上最多两层,或下最多三层。 给定两楼层,问能否一次到达。 比较大小,然后判断其差是是不是在 (2) 或 (3) 内即可。 神奇的代码 给定一个 (n) ,问不小于 (n) 的形如 (326) 的数字是多少。 形如 (326) 的数字,即数位有 (3) ,且百位 (times) 十位

    2024年02月08日
    浏览(33)
  • AtCoder Beginner Contest 344

    给定一个字符串,包含两个 | ,将 | 和两个 | 之间的字符消去。 按照题意模拟即可。 Python 比较简洁。 神奇的代码 给定 (n) 个数,倒序输出。 储存这 (n) 个数,然后倒着输出即可。 神奇的代码 给定三个数组 (a,b,c) ,回答 (q) 次询问。 每次询问,给定 (x) ,问能否从三

    2024年03月10日
    浏览(50)
  • AtCoder Beginner Contest 302

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

    2024年02月05日
    浏览(69)
  • AtCoder Beginner Contest 305

    给定一个数字 (x) ,输出一个数字,它是最接近 (x) 的 (5) 的倍数。 令 (y = x % 5) ,如果 (y leq 2) ,那答案就是 (x - y) ,否则就是 (x + 5 - y) 。 神奇的代码 给定 (ABCDEFG) 的相邻距离,给定两个字母,问它们的距离。 累加距离即可。 神奇的代码 二维平面,有一个矩形

    2024年02月08日
    浏览(52)
  • AtCoder Beginner Contest 341

    给定 (n) ,输出 (n) 个 (0) 和 (n+1) 个 (1) 交替的字符串。 (101010...) 循环输出即可。 神奇的代码 货币兑换。 (A) 国货币每 (x_a) 钱可兑换 (B) 国货币 (y_a) 钱。 (B) 国货币每 (x_b) 钱可兑换 (C) 国货币 (y_b) 钱。 ... 给定你拥有的每国货币钱数和兑换规则,依次兑换

    2024年02月19日
    浏览(25)
  • AtCoder Beginner Contest 328

    给定 (n) 个数字和一个数 (x) 。 问不大于 (x) 的数的和。 按找要求累计符合条件的数的和即可。 神奇的代码 给定一年的月数和一个月的天数。 问有多少对 ((i,j)) ,表示第 (i) 个月的第 (j) 日, (i,j) 的数位上每个数字都是一样的。 范围只有 (O(100^2)) ,枚举所有的

    2024年02月05日
    浏览(34)
  • AtCoder Beginner Contest 330

    给定 (n) 个学生的分数,以及及格分 (x) ,问多少人及格了。 依次判断即可。 神奇的代码 回答 (n) 个问题,每个问题给定 (a,l,r) ,问函数 (f(x) = |x - a|) 在 ([l,r]) 的最小值。 全定义域下,最小值显然在 (x=a) 取得。绝对值函数图像是 (V) 型。 现在限定在 ([l,r]) ,则

    2024年02月05日
    浏览(115)
  • AtCoder Beginner Contest 336

    给定一个数 (n) ,将 long 中的 o 重复 (n) 次后输出。 模拟即可。 神奇的代码 给定一个数 (n) ,问 (n) 的二进制表示下的末尾零的数量。 即找到最小的 (i) 使得 (n (1 i)) 不为零的位置。枚举即可。 或者直接用内置函数 __builtin_ctz 。(count tail zero? 神奇的代码 定义一个数

    2024年01月20日
    浏览(41)
  • AtCoder Beginner Contest 304

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

    2024年02月07日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包