UNIQUE VISION Programming Contest 2023 Autumn(AtCoder Beginner Contest 323)

A. Weak Beats

解题思路:

按题意模拟即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        if (i & 1)
        {
            if (s[i] == '1')
            {
                puts("No");
                return;
            }
        }
    }
    puts("Yes");
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

B. Round-Robin Tournament

解题思路:

暴力统计每一行有多少个\(o\)，然后排个序即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
bool cmp(pii a, pii b)
{
    if (a.fi != b.fi)
    {
        return a.fi > b.fi;
    }
    return a.se < b.se;
}
void solve()
{
    int n;
    cin >> n;
    vector<pii> cnt(n);
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        cnt[i].se = i;
        for (auto c : s)
        {
            if (c == 'o')
            {
                cnt[i].first++;
            }
        }
    }
    sort(cnt.begin(), cnt.end(), cmp);
    for (auto v : cnt)
    {
        cout << v.se + 1 << ' ';
    }
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

C. World Tour Finals

解题思路:

从大到小枚举每个玩家的分数，从大到小枚举每到题的分数，如果没选过就选上，一旦大于了最大值，新加的题数就是答案。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m + 1);
    vector<pii> b(m + 1);
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        b[i].fi = a[i];
        b[i].se = i;
    }
    vector<pii> p(n + 1);
    vector<vector<bool>> st(n + 1, vector<bool>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        p[i].fi += i;
        p[i].se = i;
        string s;
        cin >> s;
        s = ' ' + s;
        for (int j = 1; j <= m; j++)
        {
            if (s[j] == 'o')
            {
                st[i][j] = true;
                p[i].fi += a[j];
            }
        }
    }
    sort(p.begin() + 1, p.end());
    sort(b.begin() + 1, b.end());
    vector<int> ans(n + 1);

    for (int i = n; i; i--)
    {
        int cnt = 0;
        int cur = 0;
        if (i == n)
        {
            if (p[n - 1].fi == p[i].fi)
            {
                cur = p[i].fi;
            }
            else
            {
                continue;
            }
        }
        else
        {
            cur = p[i].fi;
        }
        for (int j = m; j; j--)
        {
            if (!st[p[i].se][b[j].se])
            {
                cur += b[j].fi;
                cnt++;
                if (cur > p[n].fi)
                {
                    ans[p[i].se] = cnt;
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        // cout << p[i].fi << ' ' << p[i].se << endl;
        cout << ans[i] << endl;
    }
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

D. Merge Slimes

解题思路:

从小到大看，能合并就合并。合并得到的继续能合并就合并。

每次合并剩余的不能合并的（就是只剩一个的），记得累加。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second

void solve()
{
    int n;
    cin >> n;
    map<ll, ll> v;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a] = b;
    }
    for (auto &a : v)
    {
        ll cur = 1;
        ll res = a.se >> 1;
        a.se = a.se % 2;
        ll t = a.fi;
        while (res)
        {
            cur = res >> 1;
            t <<= 1;
            if (v.count(t))
            {
                v[t] += (res % 2);
            }
            else
            {
                v[t] = (res % 2);
            }
            res >>= 1;
        }
    }
    ll ans = 0;
    for (auto a : v)
    {
        // cout << a.fi << ' ' << a.se << endl;
        ans += a.se;
    }
    cout << ans;
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

E. Playlist

解题思路:

\(f[i]\)：如\(X\)为\(i\)，答案为多少。

\(f[0]\)第一步只能选第一首歌，所以答案就是\(\frac{1}{n}\)。

对于每一个\(i\),遍历所有的歌。

对于第\(j\)首歌：

若\(t[j] > i\)，那么情况等同于\(f[0]\)，即我们选了这首歌，\(X +0.5\)放的就是这首。所以如果\(j == 1,f[i] = f[i] + \frac{1}{n}\)。
若\(t[j] \leq i\)，那么情况等同于\(f[i-t[j]]\)。\(f[i - t[j]]\)相当于时间\(0 \rightarrow (i - t[j])\)，就是要求选歌使得第\((i - t[j])+0.5\)秒后放的是第一首歌。\(f[i]\)可以相当于时间\(t[j] \rightarrow i\),同样要求选歌使得第\((i - t[j])+0.5\)秒后放的是第一首歌。二者问题等价。

时间复杂度:\(O(nx)\)

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
const int mod = 998244353;
ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return res;
}

void solve()
{
    int n, x;
    cin >> n >> x;
    vector<int> t(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
    }
    // f[i]:X为i时的可能性
    vector<ll> f(x + 10);
    // X为0时，第一步就要选到第一首歌，所以答案是1/n
    f[0] = qmi(n, mod - 2);
    // X为i时，如果要X+0.5秒的时候正好在放第1首歌。
    // 如果t[j] > i，意味着我们第一首歌如果点j，那么X + 0.5时播放的就是第j首，这和X等于0等价
    // 所以若此时j == 1，那么答案加上1 / n。
    // 如果t[j] <= i,意味着我们可以从f[i - t[j]]转移过来。
    // 从i - t[j] 到 i 和 从 0 到 i 是等价的。所以此时f[i] += f[i - t[j]].
    // 由于从每个(i - t[j])转移过来的情况是独立的，所以就可以变成加法了。
    ll inv = qmi(n, mod - 2);
    for (int i = 1; i <= x; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (t[j] > i)
            {
                f[i] = (f[i] + (j == 1) * inv) % mod;
            }
            else
            {
                f[i] = (f[i] + f[i - t[j]] * inv) % mod;
            }
        }
    }
    cout << f[x];
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}