AtCoder Beginner Contest 323

有的人边上课边打abc

A - Weak Beats (abc323 A)

题目大意

给定一个\(01\)字符串,问偶数位(从\(1\)开始) 是否全为\(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);
    string s;
    cin >> s;
    bool ok = true;
    for (int i = 1; i < s.size(); i += 2) {
        ok &= (s[i] == '0');
    }
    if (ok)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}



B - Round-Robin Tournament (abc323 B)

题目大意

给定\(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;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a) {
        string s;
        cin >> s;
        i = count(s.begin(), s.end(), 'o');
    }
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int x, int y) {
        if (a[x] != a[y])
            return a[x] > a[y];
        else
            return x < y;
    });
    for (auto& i : id)
        cout << i + 1 << ' ';

    return 0;
}



C - World Tour Finals (abc323 C)

题目大意

给定每道题的分数,以及每个人的通过情况,每个人的得分为解决题目的分的和,其中第\(i\)个人还有\(i\)的额外加分。

对于每个人,问最少还得解决多少道题,才能成为第一。

解题思路

因为范围只有\(100\),可以采取最朴素的做法,先统计每个人的分数,得到当前最高的分数。

然后对于每个人,从未通过题目的分数,排个序,大到小依次解决获得分数,看何时超过最高分。

由于每个人有不同的额外得分,所以不会有同分。

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

也可以每次遍历未通过的题目,找分数最大的,这样复杂度为\(O(n^3)\)同样可以通过。

神奇的代码
#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, m;
    cin >> n >> m;
    vector<int> a(m);
    for (auto& i : a)
        cin >> i;
    vector<int> score(n);
    vector<string> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        score[i] = i + 1;
        for (int j = 0; j < m; ++j)
            score[i] += a[j] * (s[i][j] == 'o');
    }
    int maxx = *max_element(score.begin(), score.end());
    for (int i = 0; i < n; ++i) {
        if (score[i] == maxx) {
            cout << 0 << '\n';
            continue;
        }
        int dis = maxx - score[i];
        vector<int> unsolve;
        for (int j = 0; j < m; ++j)
            if (s[i][j] == 'x')
                unsolve.push_back(a[j]);
        sort(unsolve.begin(), unsolve.end(), greater<int>());
        int ans = 0;
        for (; dis > 0 && ans < unsolve.size(); ++ans) {
            dis -= unsolve[ans];
        }
        cout << ans << '\n';
    }

    return 0;
}



D - Merge Slimes (abc323 D)

题目大意

\(n\)类数字,第 \(i\)类数字为 \(s_i\),有 \(c_i\)个。

同类数字可以两两合并,得到一个\(s_i + s_i\)数字。

问最后剩下的数字数量。

解题思路

因为数字很大,可以考虑用map存对应数的数量。

但是不能遍历\(map\)的每个元素,然后合并,累计到更大的数里。因为如果更大的数不存在,会插入到 \(map\)中,从而可能导致原因迭代器失效。

但考虑到一类元素不断合并,最终停止时,其个数一定是\(1\),就不用管它了,我们只考虑一开始的那些类别。 因此事先用set储存原来的数的类别。

然后对于set的每一个类别,从小到大考虑不断合并,直到数量变为\(1\)。由于每次合并数量都除以 \(2\)。因此每一类最多 \(\log\)次就结束了。

最后看 map里剩余数的个数。

神奇的代码
#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;
    unordered_map<LL, int> cnt;
    set<int> a;
    for (int i = 0; i < n; ++i) {
        int s, c;
        cin >> s >> c;
        cnt[s] = c;
        a.insert(s);
    }
    int ans = 0;
    for (auto& i : a) {
        int sum = 0;
        for (LL j = i; true; j = j + j) {
            sum = (sum + cnt[j]);
            if (sum < 2) {
                cnt[j] = sum;
                break;
            }
            cnt[j] = sum % 2;
            sum /= 2;
        }
    }
    for (auto& i : cnt) {
        ans += i.second;
    }
    cout << ans << '\n';

    return 0;
}



E - Playlist (abc323 E)

题目大意

给定\(n\)首歌的播放时间。

从第\(0\)秒,随机选一首歌播放。当一首歌播放完后,立刻随机选下一首歌播放。

问第 \(X + 0.5\)秒 时播放第一首歌的概率。

解题思路

假设第一首歌的播放时长为\(t\)

那么要在 \(X + 0.5\)秒播放第一首歌,则要求第一首歌在第 \(X, X - 1, X - 2, ..., X - t + 1\)秒中的一秒开始播放。

而如果我知道能够在\(X,X-1,X-2,...,X-t + 1\)秒开始播放的概率(或者说这些时刻恰好播放完的概率),那么这些概率的和,再乘以\(\frac{1}{n}\)(即选到第一首歌播放的概率),就是答案。

\(dp[i]\)表示能够在第 \(i\)秒开始播放的概率,转移则枚举之前播放的是哪一首歌,比如第 \(j\)首,播放时长为\(t_j\),则有 \(dp[i] += dp[i - t_j] \times \frac{1}{n}\)

\(dp[i] = \sum_{t_j \leq i} dp[i - t_j] \times \frac{1}{n}\)

初始条件就是\(dp[0] = 1\)。即第 \(0\)秒肯定能够播放一首歌。

最后答案就是\(\sum_{i = x - t + 1}^{x} dp[i] \times \frac{1}{n}\)

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

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

const int mo = 998244353;

int qpower(int a, int b) {
    int ret = 1;
    while (b) {
        if (b & 1) {
            ret = 1ll * ret * a % mo;
        }
        a = 1ll * a * a % mo;
        b >>= 1;
    }
    return ret;
}

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

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int> t(n);
    for (auto& i : t) {
        cin >> i;
    }
    vector<int> dp(x + 1);
    int one = inv(n);
    dp[0] = 1;
    for (int i = 1; i <= x; ++i) {
        int sum = 0;
        for (auto& j : t) {
            if (i < j)
                continue;
            sum += 1ll * dp[i - j] * one % mo;
            if (sum >= mo)
                sum -= mo;
        }
        dp[i] = sum;
    }
    int ans = 0;
    for (int i = max(0, x - t[0] + 1); i <= x; ++i) {
        ans = ans + dp[i];
        if (ans >= mo)
            ans -= mo;
    }
    ans = 1ll * ans * one % mo;
    cout << ans << '\n';

    return 0;
}



F - Push and Carry (abc323 F)

题目大意

二维平面,推箱子。给定你的位置,箱子位置,目标位置,一次上下左右移动一格,问把箱子推到目标位置的最小步数。

解题思路

虽然坐标范围挺大的,但实际上决策只有两种。枚举两种决策分别计算下步数取最小即可。

假设箱子在左下,目标位置在右上。很显然,推箱子只有两个决策:

  • 先向上推,再向右推。
  • 先向右推,再向上推。

而为了把箱子向上推,那么事先要走到箱子的下方。同理向右推,要事先走到箱子的左方。

最终步数的贡献来自于:

  • 起始位置走到推箱子的位置的步数
  • 推动箱子的步数(固定的,为箱子位置目标位置的曼哈顿距离)
  • 中间转动方向时额外需要的步数(固定的,为\(2\)),比如向上推时,你在箱子下方,然后要向右推,你需要走到箱子的左方,步数为\(2\)

因此只有第一个位置需要枚举,事实上就两种情况:

  • 先向上推,则求出初始位置到箱子下方的距离
  • 先向右推,则求出初始位置到箱子左方的距离

而这个距离事实上也是个曼哈顿距离,因为除了箱子别无障碍,两种方式到达指定位置中,必有一种是畅通无阻的。

当注意一种情况,当初始位置、箱子位置、到达箱子的位置处于同一条线,且箱子位置在中间的时候,此时并不是畅通无阻的,必须要偏移一下。比如初始位置在左边,箱子在中间,为了把箱子往左推,你要跑到箱子右边,但不能穿过箱子,此时的步数在曼哈顿距离的基础上还要\(+2\),即先向上走或向下走,再走回来。

代码里两种情况的分别考虑就相当于交换了下两个坐标,再考虑一次。

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

int sign(LL x) {
    if (x == 0)
        return 0;
    else if (x > 0)
        return 1;
    else
        return -1;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    array<array<LL, 2>, 3> pos;
    for (auto& i : pos)
        for (auto& j : i)
            cin >> j;
    auto& [player, box, target] = pos;
    auto dis = [&](const array<LL, 2>& a, const array<LL, 2>& b) {
        return abs(a[0] - b[0]) + abs(a[1] - b[1]);
    };
    LL bound = dis(box, target);
    auto in_middle = [](LL l, LL m, LL r) {
        LL L = min(l, r), R = max(l, r);
        return m > L && m < R;
    };
    auto solve = [&]() {
        LL ret = bound;
        int d = sign(box[0] - target[0]);
        if (d == 0)
            return numeric_limits<LL>::max();
        array<LL, 2> t1 = box;
        t1[0] += d;
        ret += dis(player, t1);
        if ((player[0] == t1[0] && player[0] == box[0] &&
             in_middle(player[1], box[1], t1[1])) ||
            (player[1] == t1[1] && player[1] == box[1] &&
             in_middle(player[0], box[0], t1[0])))
            ret += 2;
        if (box[1] != target[1])
            ret += 2;
        return ret;
    };
    LL ans = solve();
    for (auto& i : pos)
        swap(i[0], i[1]);
    ans = min(ans, solve());
    cout << ans << '\n';

    return 0;
}



G - Inversion of Tree (abc323 G)

题目大意

给定一个关于\(n\)的全排列\(p\)。对于每个\(k = 0,1,2,...,n - 1\),问有多少种形态的树,满足树上恰好有\(k\)条边\((u,v)(u < v)\),有 \(p_u > p_v\)

解题思路

<++>

神奇的代码



热门相关:英雄联盟之巅峰王座   宠物小精灵之庭树   隐婚试爱:娇妻,好甜!   雏妓1988   重生之嫡女祸妃