链接：https://atcoder.jp/contests/abc441
A – Black Square
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x2 >= x1 && y2 >= y1 && x2 <= x1 + 99 && y2 <= y1 + 99)
cout << "Yes" << endl;
else
cout << "No" << endl;
}B – Two Languages
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
int n, m;
string s, t;
cin >> n >> m >> s >> t;
unordered_set<char> S, T;
for (auto c : s)
S.insert(c);
for (auto c : t)
T.insert(c);
int Q;
cin >> Q;
while (Q--)
{
string c;
cin >> c;
bool ok1 = 1, ok2 = 1;
for (auto x : c)
{
if (!S.count(x))
ok1 = 0;
if (!T.count(x))
ok2 = 0;
}
if (ok1 && !ok2)
cout << "Takahashi" << endl;
else if (!ok1 && ok2)
cout << "Aoki" << endl;
else
cout << "Unknown" << endl;
}
}C – Sake or Water
算法：
贪心。
思路：
确保喝到酒，那么就需要做最坏的打算，即假设共有 \(n\) 杯液体，其中 \(k\) 杯为酒，确保喝到两杯酒，需要选择 \(n – k + 2\) 个杯子。
考虑最少要几杯，先喝最大的 \(n – k\) 杯，由于考虑的最坏打算，喝掉的都为水，在剩余的 \(k\) 杯中从大的开始喝即可。
关键代码：
void miyan()
{
ll n, k, x;
cin >> n >> k >> x;
vector<ll> a(n);
for (auto &x : a)
cin >> x;
ranges::sort(a);
ll ans = n - k;
ll sum = 0;
for (int i = k - 1; i >= 0; --i)
{
++ans;
sum += a[i];
if (sum >= x)
break;
}
if (sum < x)
cout << -1 << endl;
else
cout << ans << endl;
}D – Paid Walk
算法：
图的遍历，\(dfs\)。
思路：
无。
关键代码：
void miyan()
{
ll n, m, l, s, t;
cin >> n >> m >> l >> s >> t;
vector<vector<pii>> g(n + 1);
for (int i = 1; i <= m; ++i)
{
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
set<int> ans;
auto dfs = [&](auto &&self, int u, ll sum, int L) -> void
{
if (sum > t)
return;
if (!L)
{
if (sum >= s && sum <= t)
{
ans.insert(u);
}
return;
}
for (auto [v, w] : g[u])
self(self, v, sum + w, L - 1);
};
dfs(dfs, 1, 0, l);
for (auto x : ans)
cout << x << ' ';
cout << endl;
}E – A > B substring
算法：
前缀和思想，树状数组。
思路：
这类题目有个非常经典的 \(trick\)。
将 \(A\) 转换为 \(1\)，\(B\) 转换为 \(-1\)，然后对数组求前缀和；一段区间中如果 \(A\) 的个数大于 \(B\) 的个数说明满足区间值是正的，即 \(pre[r] > pre[l – 1]\)，那么只需对于每个区间右下标 \(r\) 统计比他值小的区间左下标 \(l\) 即可。
统计答案可以使用树状数组加速。
关键代码：
struct BIT
{
int n;
vector<ll> tr;
BIT(int _N)
{
n = _N;
tr.resize(n + 1, 0);
}
void add(int x, ll v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
ll query(int l, int r)
{
auto ask = [&](int x)
{
ll ans = 0;
for (; x; x -= x & -x)
ans += tr[x];
return ans;
};
return ask(r) - ask(l - 1);
}
};
void miyan()
{
int n;
string s;
cin >> n >> s;
s = ' ' + s;
vector<int> pre(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
pre[i] = pre[i - 1];
if (s[i] == 'A')
++pre[i];
else if (s[i] == 'B')
--pre[i];
}
BIT bit(2 * N);
bit.add(N, 1);
ll ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += bit.query(1, pre[i] + N - 1);
bit.add(pre[i] + N, 1);
}
cout << ans << endl;
}F – Must Buy
算法：
背包\(dp\)。
思路：
最大总价值跑一遍 \(01\) 背包即可。
考虑第 \(i\) 个物品属于哪一类：
- 如果不选第 \(i\) 个物品，在 \(n – 1\) 个物品中选择总价格不超过 \(m\) 的最大总价值 \(value\) 减少了，那么 \(i\) 必选，属于 \(A\) 类；
- 如果选择第 \(i\) 个物品，在 \(n – 1\) 个物品中选择总价格不超过 \(m – p[i]\) 的最大总价值 \(value + v[i]\) 减少了，那么不选 \(i\) ，属于 \(C\) 类；
- 否者为 \(B\) 类。
状态定义：
- 定义 \(dpp[i][j]\) 为考虑前 \(i\) 个物品总价格不超过 \(j\) 的最大总价值。
- 定义 \(dps[i][j]\) 为考虑后 \(n – i + 1\) 个物品总价格不超过 \(j\) 的最大总价值。
状态转移：
- \(dpp[i]_{i = 1}^{n}[j]_{j = 0}^{m} = max(dpp[i – 1][j], p[i] <= j ? dpp[i – 1][j – p[i]] + v[i] : 0)\)
- \(dps[i]_{i = n}^{1}[j]_{j = 0}^{m} = max(dps[i + 1][j], p[i] <= j ? dps[i + 1][j – p[i]] + v[i] : 0)\)
关键代码：
void miyan()
{
ll n, m;
cin >> n >> m;
vector<ll> p(n + 1);
vector<ll> v(n + 1);
for (int i = 1; i <= n; ++i)
cin >> p[i] >> v[i];
vector dpp(n + 2, vector<ll>(m + 1, 0));
vector dps(n + 2, vector<ll>(m + 1, 0));
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
dpp[i][j] = dpp[i - 1][j];
if (j >= p[i])
dpp[i][j] = max(dpp[i][j], dpp[i - 1][j - p[i]] + v[i]);
}
}
for (int i = n; i >= 1; --i)
{
for (int j = 0; j <= m; ++j)
{
dps[i][j] = dps[i + 1][j];
if (j >= p[i])
dps[i][j] = max(dps[i][j], dps[i + 1][j - p[i]] + v[i]);
}
}
ll maxx = dpp[n][m];
string ans;
for (int i = 1; i <= n; ++i)
{
ll val1 = 0, val2 = 0;
for (int j = 0; j <= m; ++j)
{
ll cur = dpp[i - 1][j] + dps[i + 1][m - j];
val1 = max(val1, cur);
}
for (int j = 0; j <= m - p[i]; ++j)
{
ll cur = v[i] + dpp[i - 1][j] + dps[i + 1][m - p[i] - j];
val2 = max(val2, cur);
}
if (val1 < maxx)
ans += 'A';
else if (val2 < maxx)
ans += 'C';
else
ans += 'B';
}
cout << ans << endl;
}G – Takoyaki and Flip
还没补。
