A. Welcome to AtCoder Land
模拟
B. Ticket Counter
模拟
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, a;
cin >> n >> a;
vector<int> t(n);
rep(i, n) cin >> t[i];
int x = 0;
rep(i, n) {
if (t[i] < x) {
x += a;
}
else {
x = t[i]+a;
}
cout << x << '\n';
}
return 0;
}
C. Popcorn
先把每条信息压成一个二进制数，再做二进制枚举即可
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<string> s(n);
rep(i, n) cin >> s[i];
using BS = bitset<10>;
vector<BS> b(n);
rep(i, n) {
rep(j, m) if (s[i][j] == 'o') b[i][j] = 1;
}
int ans = n;
rep(x, 1<<n) {
BS bx(x);
BS sb;
rep(i, n) if (bx[i]) sb |= b[i];
if (sb.count() == m) ans = min(ans, (int)bx.count());
}
cout << ans << '\n';
return 0;
}
D. Souvenirs
贪心
先对序列 \(B\) 做升序排序，然后购买当前剩下的数中大于等于 \(B_i\) 的最小值
可以用 std::multiset 来维护序列 \(A\)
也可以用双指针，但需要先对序列 \(A\) 做排序
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
rep(i, n) cin >> a[i];
rep(i, m) cin >> b[i];
sort(b.begin(), b.end());
multiset<int> s(a.begin(), a.end());
ll ans = 0;
rep(i, m) {
auto it = s.lower_bound(b[i]);
if (it == s.end()) {
puts("-1");
return 0;
}
ans += *it;
s.erase(it);
}
cout << ans << '\n';
return 0;
}
E. Alphabet Tiles
原题：ABC234F
记 dp[i][j] 表示用前 \(i\) 种大写字母能构成的长度为 \(j\) 的本质不同的字符串个数
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
struct modinv {
int n; vector<mint> d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(-d[mint::mod()%n]*(mint::mod()/n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} invs;
struct modfact {
int n; vector<mint> d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*n), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} facts;
struct modfactinv {
int n; vector<mint> d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*invs(n)), ++n;
return d[i];
}
mint operator[](int i) const { return d[i];}
} ifacts;
mint comb(int n, int k) {
if (n < k || k < 0) return 0;
return facts(n)*ifacts(k)*ifacts(n-k);
}
int main() {
int n = 26;
int k;
cin >> k;
vector<int> c(n);
rep(i, n) cin >> c[i];
vector<mint> dp(k+1);
dp[0] = 1;
rep(i, n) {
vector<mint> old(k+1);
swap(dp, old);
rep(j, k+1) {
rep(a, c[i]+1) {
int nj = j+a;
if (nj > k) break;
dp[nj] += old[j]*ifacts(a);
}
}
}
mint ans;
rep(i, k) ans += dp[i+1]*facts(i+1);
cout << ans.val() << '\n';
return 0;
}