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;
}