AtCoder Beginner Contest 195 Editorial
Problem A - Health M Death(opens new window)
只要检查 (Hequiv 0) 即可.
- Time complexity is (mathcal{O}(1)).
- Space complexity is (mathcal{O}(1)).
Code(C++)
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int M, H;
cin >> M >> H;
cout << (H % M == 0 ? "Yes
" : "No
");
return 0;
}
Problem B - Many Oranges(opens new window)
注意 (W) 是以千克为单位,所以需要以 (1000W) 代替 (W)
首先先来分析上限:
尽可能使用 A 来达到上限,但问题是可能会有剩余的克数
,我们需要将其分配给 (B) 即可
- Time complexity is (mathcal{O}(1))).
- Space complexity is (mathcal{O}(1)).
Code (C++)
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int A, B, W;
cin >> A >> B >> W;
W *= 1000;
int minn = W / B;
int maxn = W / A;
if (minn + (W % B != 0) <= maxn) {
cout << minn + (W % B != 0) << ' ' << maxn << "
";
} else {
cout << "UNSATISFIABLE
";
}
return 0;
}
Problem C - Comma(opens new window)
- [1,9]: 9 numbers, each has 0 commas.
- [10,99]: 90 numbers, each has 0 commas.
- [100,999]: 900 numbers, each has 0 commas.
- [1000,9999]: 9000 numbers, each has 1 comma.
- (cdots)
基于以上模式可以很简单从 (1000) 开始,然后每 (10) 倍的递增直到超过 (N).
- Time complexity is (mathcal{O}(log_{10}N)).
- Space complexity is (mathcal{O}(1)).
Code (Rust)
use proconio::input;
fn main() {
input! {
n: usize,
}
let mut base: usize = 1_000;
let mut ans: usize = 0;
let mut cnt = 3;
while base <= n {
let num = (n - base + 1).min(base * 9);
ans += num * (cnt / 3);
cnt += 1;
base *= 10;
}
println!("{}", ans);
}
Code (C++)
using ll = long long;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
ll n, ans = 0;
cin >> n;
if (n > 999) ans += n - 999;
if (n > 999999) ans += n - 999999;
if (n > 999999999) ans += n - 999999999;
if (n > 999999999999) ans += n - 999999999999;
if (n > 999999999999999) ans += n - 999999999999999;
cout << ans << "
";
return 0;
}
Problem D - Shipping Center(opens new window)
第一眼看过去是线段树问题,但数据范围较小可以暴力找。
对于每个查询,我们收集所有可用的框,并根据其容量以升序对其进行排序。 对于每个盒子,我们从没有使用过的,盒子可以容纳的所有物品中,贪婪地选择最有价值的行李。
- Time complexity is (mathcal{O}(QM(N+log M))).
- Space complexity is (mathcal{O}(1)).
Code (C++)
using ll = long long;
typedef pair pii;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector wv(n);
vector x(m);
for (int i = 0; i < n; ++i) cin >> wv[i].second >> wv[i].first;
for (int i = 0; i < m; ++i) cin >> x[i];
sort(wv.begin(), wv.end(), greater());
while (q--) {
multiset s;
// 避免使用 Set 增加不必要的排序,因为上面已经排好序了
ll ans = 0;
int l, r;
cin >> l >> r;
for (int i = 0; i < l - 1; ++i) s.insert(x[i]);
for (int i = r; i < m; ++i) s.insert(x[i]);
multiset::iterator it;
for (int i = 0; i < n; ++i) {
if ((it = s.lower_bound(wv[i].second)) != s.end())
s.erase(it), ans += wv[i].first;
}
cout << ans << "
";
// cout << "
";
}
return 0;
}
Problem E - Lucky 7 Battle(opens new window)
不难发现,在这个游戏中,只有(7)的模数很重要。 因此,我们将精确地具有(7)个状态,表示当前的模数。
从后开始,因为我们只知道游戏结束时的赢/输状态:$0 = ext{Takahashi获胜} , ext {others} = ext{Aoki获胜} $
对于每一步,我们都会枚举所有 (7)个模,并计算其后继者:(a =(last * 10)%7,b =(last * 10 + s [i])%7)。
如果高桥移动,则他需要 (a)或(b)才能成为获胜状态(对于高桥来说),以便last将成为获胜状态。
如果Aoki移动,他需要 (a)和b(b)成为失败状态(对于Takahashi),以便last将成为失败状态,否则(a和b均为获胜状态),last将成为获胜状态。
并且我们只需要首先检查 (0) 是否为获胜状态。
- Time complexity is (mathcal{O}(CN), where C=7).
- Space complexity is (mathcal{O}(C)).
using ll = long long;
int p7[8] = {1, 3, 2, 6, 4, 5};
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int l;
cin >> l;
string s, t;
cin >> s >> t;
int mask = 1;
for (int i = l - 1; i >= 0; i--) {
int tg = (p7[(l - 1 - i) % 6] * (s[i] - '0')) % 7;
int nm = (mask << tg);
nm |= (nm >> 7);
nm &= (1 << 7) - 1;
if (t[i] == 'T') mask |= nm;
else
mask &= nm;
// cout << mask << '
';
}
cout << (mask & 1 ? "Takahashi
" : "Aoki
");
return 0;
}