A - Daily Cookie
题意：有\(n\)个盒子，有些盒子有蛋糕，被人吃了\(m\)个蛋糕，问有几个盒子没蛋糕。
直接计算即可。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::string s;
std::cin >> s;
std::cout << n - std::count(s.begin(), s.end(), '@') + m << "\n";
}
B - Daily Cookie 2
题意：题意：有\(n\)个盒子，有些盒子有蛋糕，被人从后往前吃了\(m\)个蛋糕，问每个盒子的状况。
模拟即可。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::string s;
std::cin >> s;
for (int i = n - 1; i >= 0 && m; -- i) {
if (s[i] == '@') {
s[i] = '.';
-- m;
}
}
std::cout << s << "\n";
}
C - Kaiten Sushi
题意：有\(n\)个美食家，他们有一个美食值，然后\(m\)个食物从前往后走，每个食物有美味值。食物遇到第一个美食值小于等于他的美食家就会被吃掉，问每个食物被哪个美食家吃掉了。
如果前面有一个美食家美食值小于等于后面的美食家，那么后面的美食家就吃不到东西了。我们可以给食物排序，看每个美食家可以吃哪一个区间的美食。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n), ans(m, -1);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<std::pair<int, int> > b(m);
for (int i = 0; i < m; ++ i) {
int x;
std::cin >> x;
b[i] = {x, i};
}
std::sort(b.begin(), b.end());
for (int i = 0, last = m; i < n; ++ i) {
int p = std::lower_bound(b.begin(), b.end(), std::pair<int, int>{a[i], 0}) - b.begin();
for (int j = p; j < last; ++ j) {
ans[b[j].second] = i + 1;
}
last = std::min(last, p);
}
for (int i = 0; i < m; ++ i) {
std::cout << ans[i] << "\n";
}
}
D - Keep Distance
题意：构造出所有满足条件的序列，第一个数大于等于1，后面每个数都大于等于前面一个数加10，最后一个数小于等于\(m\)。
爆搜即可。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > ans;
std::vector<int> a;
auto dfs = [&](auto self, int cnt, int last) -> void {
if (cnt == n) {
ans.push_back(a);
return;
}
if ((n - cnt) * 10 + last > m) {
return;
}
for (int i = last + 10; i + (n - cnt - 1) * 10 <= m; ++ i) {
a.push_back(i);
self(self, cnt + 1, i);
a.pop_back();
}
};
dfs(dfs, 0, -9);
std::cout << ans.size() << "\n";
for (auto & a : ans) {
for (auto & x : a) {
std::cout << x << " \n"[x == a.back()];
}
}
}
E - Expansion Packs
题意：有无数个包裹，每个包里都有\(n\)张卡牌，每张卡牌有\(p_i\)的几率是稀有的，问你获得m张稀有卡牌需要开启包裹的期望。
我们可以记\(f_i\)为开出\(i\)张卡牌的期望，那么我们枚举最后一次开包裹开出了几张卡牌，如果一次包裹开出\(x\)张卡牌的概率为\(g_x\)，那么\(f_i = 1 + \sum_{j=0}^{i} f_j g_{i-j}\)。但我们发现这里包含一个\(f_i\)，有后效性，我们可以整理一下式子 \(f_i = 1 + \sum_{j=0}^{i-1} f_j g_{i-j} + f_i g_0\)，整理得到\(f_i = \frac{1 + \sum_{j=0}^{i-1} f_j g_{i-j}}{1 - g_0}\)。 关于\(g\)，我们也可以dp求得，设\(dp_{ij}\)表示前\(i\)中卡牌开出\(j\)个卡牌的概率，那么\(dp_ij = dp_{i-1j-1}p_i + dp_{i-1j}(1-p_i)\)，意为当前整个卡牌是稀有的和不是稀有的情况之和。于是\(g_i\)等于\(dp_{ni}\)。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<double> p(n);
for (int i = 0; i < n; ++ i) {
std::cin >> p[i];
p[i] = p[i] / 100;
}
std::vector<double> g(n + 1);
g[0] = 1;
for (int i = 0; i < n; ++ i) {
for (int j = i + 1; j >= 1; -- j) {
g[j] = g[j - 1] * p[i] + g[j] * (1 - p[i]);
}
g[0] = g[0] * (1 - p[i]);
}
std::vector<double> f(m + 1);
for (int i = 1; i <= m; ++ i) {
for (int j = std::max(0, i - n); j < i; ++ j) {
f[i] += f[j] * g[i - j];
}
f[i] += 1;
f[i] /= 1 - g[0];
}
std::cout << std::fixed << std::setprecision(12);
std::cout << f[m] << "\n";
}
F - Falling Bars
题意：一个矩阵里有\(n\)个占1行多列的长条，每个长条如果下面没有其他长条挨着他就会一直往下掉，类似俄罗斯方块。问最后每个长条在哪一行。
很明显的线段树题，我们给长条按行从低到高排序，然后看当前长条所在的区间被占到的最大行是多少，更新即可。可以用线段树维护每列的最大值。
点击查看代码
#define ls (u << 1)
#define rs (u << 1 | 1)
struct Node {
int l, r;
int max;
int lazy;
};
struct SegmentTree {
std::vector<Node> tr;
SegmentTree(int _n) {
tr.assign(_n << 2, {});
build(1, 1, _n);
}
void pushup(int u) {
tr[u].max = std::max(tr[ls].max, tr[rs].max);
}
void pushup(Node & u, int v) {
u.max = u.lazy = v;
}
void pushdown(int u) {
if (tr[u].lazy) {
pushup(tr[ls], tr[u].lazy);
pushup(tr[rs], tr[u].lazy);
tr[u].lazy = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r};
int mid = l + r >> 1;
if (l == r) {
return;
}
build(ls, l, mid); build(rs, mid + 1, r);
}
void modify(int u, int l, int r, int v) {
if (l <= tr[u].l && tr[u].r <= r) {
pushup(tr[u], v);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) {
modify(ls, l, r, v);
}
if (r > mid) {
modify(rs, l, r, v);
}
pushup(u);
}
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u].max;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid) {
return query(ls, l, r);
} else if (l > mid) {
return query(rs, l, r);
} else {
return std::max(query(ls, l, r), query(rs, l, r));
}
}
};
void solve() {
int h, w, n;
std::cin >> h >> w >> n;
std::vector<std::array<int, 4> > a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i][0] >> a[i][1] >> a[i][2];
a[i][0] = h - a[i][0] + 1;
a[i][3] = i;
}
std::sort(a.begin(), a.end());
SegmentTree tr(w);
std::vector<int> ans(n);
for (auto & [r, c, l, id] : a) {
int x = tr.query(1, c, c + l - 1) + 1;
tr.modify(1, c, c + l - 1, x);
ans[id] = h - x + 1;
}
for (int i = 0; i < n; ++ i) {
std::cout << ans[i] << "\n";
}
}