526互联

AtCoder Beginner Contest 323 (ABC 323) D、E、F 题解

发布时间 2023-10-08 16:33:30作者: 过_路_人

AtCoder Beginner Contest 323 (ABC 323) D、E、F 题解

D

题目大意

给 \(n\) 种数 \(s_i\) ，每一种数有 \(c_i\) 个，每次可以把两个相同的数合并为一个数，问最后会剩下多少数？

分析

对于每一个数 \(s_i\) ，它最多被分解 \(log_2c_i\) 次，并且合并出来最大的数的大小小于 \(s_i\times c_i\)

如果将 \(s_i\) 合并，这个操作是对任意小于 \(2s_i\) 的数没有影响的。

因此考虑维护一个堆，每次将最小的数尽量合并，如果该元素只剩一个就将其踢出去并让答案+1。

Code （用优先队列写很慢~）

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int n;
ll s[N], c[N];
map<ll, ll> cnt;

int main() {
    IO;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> c[i];
        cnt[s[i]] += c[i];
    }
    ll ans = 0;
    while (!cnt.empty()) {
        auto [x, y] = *cnt.begin();
        cnt.erase(cnt.begin());
        ans += y % 2;
        if (y > 1) {
            cnt[x*2] += y / 2;
        }
    }
    cout << ans;
    return 0;
}

E

题目大意

给 \(n\) 首歌，每首持续时间 \(T_i\) ，当没有歌正在播放时，在 \(n\) 首歌里随机播放一首，问第 \(x + 0.5\) 秒时第一首歌正在播放的概率

分析

应该说我的方法不如官方题解

如果第 \(x + 0.5\) 秒正在播放的是第一首歌，那么这首歌开始播放的时间应该是 \([x-t_1+1,x]\)

考虑 \(f[i][j]\) 表示当前为第 \(i\) 秒，正准备开始播放第 \(j\) 首歌的概率

那么最终的结果就是 \(\sum\limits_{i=x-t_1+1}^{x} f[i][1]\)

可以得到比较暴力的转移式子：$f[i][j] = \sum_{k=1}^{n}\frac{1}{n}f[i-t[k]][k] $

在实现的时候，可以写成 f[i+t[j]][k] += f[i][j] / n

那么注意到，无论 \(k\) 是几，都会收到 \(f[i][j]\) 的一份转移

那么用 \(sum[i]\) 记录第 \(i\) 秒会加上多少，在考虑第 \(i\) 秒时，加上 \(sum[i]\) 就可以了

注意分数逆元是可以直接加减的 ！

对于两个分数 \(\frac{a}{b}\) 和 \(\frac{c}{d}\) ，它们各自在模 \(p\) 下的值为 \(a \times inv_b\) 和 \(c \times inv_d\)

当它们相加时，

\[\begin{aligned} (\frac{a}{b}+\frac{c}{d}) ~mod~p &= \frac{ad+bc}{bd}~mod~p \\ &= (ad+bc) \times inv_{bd} ~mod~p~(注意d\times inv_{bd}=inv_b)\\ &= (a \times inv_b + c \times inv_d)~mod~p \\ \end{aligned} \]

Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const int N = 1005, M = 3e4 + 5;
int n, x;
ll t[N];
ll qpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return res;
}
ll f[M][N], sum[M];
ll frac(ll a, ll b) {
    return (a * qpow(b, mod - 2) % mod + mod) % mod;
}

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++)
        f[0][i] = frac(1, n);
    for (int i = 0; i <= x; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = (f[i][j] + sum[i]) % mod;
            sum[i+t[j]] = (sum[i+t[j]] + frac(f[i][j], n)) % mod;
        }
    }
    ll res = 0;
    for (int i = max(0ll, x - t[1] + 1); i <= x; i++) 
        res = (res + f[i][1]) % mod;
    cout << res;
    return 0;
}

F

AtCoder 你确定没有把 D 和 F 放反吗？？？

题目大意

\((x_a,y_a)\) 点站了一个人，\((x_b,y_b)\) 点有一个箱子，人要把箱子推到 \((x_c,y_c)\) 去，人和箱子不会出现在同一坐标，会把箱子挤走

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

ll Abs(ll a) {
    return a > 0 ? a : -a;
}

int main() {
    ll xa, ya, xb, yb, xc, yc;
    cin >> xa >> ya >> xb >> yb >> xc >> yc;
    ll ans = 0;
    ans = Abs(xa - xb) + Abs(ya - yb) + Abs(yc - yb) + Abs(xc - xb) - 1;
    if (xa == xb && xb == xc) {
        if ((ya < yb && yc < yb) || (ya > yb && yc > yb))
            ans += 4;
        cout << ans;
        return 0;
    }
    if (ya == yb && yb == yc) {
        if ((xa < xb && xc < xb) || (xa > xb && xc > xb))
            ans += 4;
        cout << ans;
        return 0;
    }
    if ((xa <= xb && xc < xb) || (xa >= xb && xc > xb))
        ans += 2;
    if ((ya <= yb && yc < yb) || (ya >= yb && yc > yb))
        ans += 2;
    if ((ya < yb && yb < yc && xa > xb && xb > xc) || (ya > yb && yb > yc && xa < xb && xb < xc))
        ans += 2;
    if ((ya < yb && yb < yc && xa < xb && xb < xc) || (ya > yb && yb > yc && xa > xb && xb > xc))
        ans += 2;
    cout << ans;
    return 0;
}