链接：https://atcoder.jp/contests/abc415
A – Unsupported Type
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
int n, k;
cin >> n;
vi a(n + 10);
cin >> a;
cin >> k;
bool ans = 0;
for (int i = 0; i < n; ++i)
{
if (a[i] == k)
ans = 1;
}
if (ans)
cout << "Yes" << endl;
else
cout << "No" << endl;
}B – Pick Two
算法：
模拟。
思路：
无。
关键代码：
void solve()
{
string s;
cin >> s;
int n = s.size();
vi ans;
for (int i = 0; i < n; ++i)
if (s[i] == '#')
ans.push_back(i + 1);
for (int i = 0; i < ans.size(); i += 2)
cout << ans[i] << ',' << ans[i + 1] << endl;
}C – Mixture
评价：
什么狗屎题意。
算法：
bfs。
思路：
无。
关键代码：
void solve()
{
int n;
string S;
cin >> n >> S;
int full = (1 << n) - 1;
vector<char> vis(1 << n, 0);
queue<int> q;
vis[0] = 1;
q.push(0);
bool ok = 0;
while (!q.empty())
{
int m = q.front();
q.pop();
if (m == full)
{
ok = 1;
break;
}
for (int i = 0; i < n; i++)
{
if (!(m & (1 << i)))
{
int m2 = m | (1 << i);
if (!vis[m2] && S[m2 - 1] == '0')
{
vis[m2] = 1;
q.push(m2);
}
}
}
}
if (ok)
cout << "Yes" << endl;
else
cout << "No" << endl;
}D – Get Many Stickers
算法：
贪心。
思路：
对每对兑换所需的消耗进行升序排序，从消耗最小的开始计算即可。
关键代码：
void solve()
{
ll n, m;
cin >> n >> m;
vector<ll> a(m + 10), b(m + 10);
for (int i = 0; i < m; ++i)
cin >> a[i] >> b[i];
vector<array<ll, 3>> cnt;
for (int i = 0; i < m; ++i)
cnt.push_back({a[i] - b[i], a[i], b[i]});
sort(all(cnt));
ll ans = 0;
ll sum = n;
for (int i = 0; i < m; ++i)
{
if (sum >= cnt[i][1])
{
ll t = 0;
if (sum == cnt[i][1])
t = 1;
else
t = (sum - cnt[i][1]) / cnt[i][0] + 1ll;
ans += t;
sum = sum - t * cnt[i][0];
}
}
cout << ans << endl;
}E – Hungry Takahashi
算法：
dp。
思路：
我们使用逆向动态规划，从终点开始反推到起点。
定义状态：
dp[i][j] 表示：如果高桥在第 i + j + 1 天结束后正好位于格子 (i, j)，那么为了确保后续所有天数都不会饿死，他此时手中最少需要持有的金币数。
之所以是第 i + j + 1 天，是因为从 (0, 0) 开始，每次只能向右或向下走一格，到达 (i, j) 恰好需要走 i + j 步，所以是第 i + j + 1 天。
状态转移：
每个状态 dp[i][j] 可以更新它的上方格子 (i – 1, j) 和左方格子 (i, j – 1)。
以 (i, j) 向上转移为例：
- 从 (i – 1, j) 移动到 (i, j)，发生在第 i + j 天（数组下标为 i + j − 1）；
- 在 (i – 1, j)，高桥会先收集 A[i – 1][j] 个金币；
- 然后他要消费 P[i + j − 1] 个金币吃饭；
- 接着进入 (i, j)，而 dp[i][j] 表示他进入该格子前必须手上至少有这么多金币。
定义 X 为在到达(i – 1, j)之前获得的金币，因此，他在进入 (i – 1, j) 时，手上需要携带的金币满足：
\(X + G[i-1][j] – P[i+j-1] ≥ dp[i][j]\)
也就是说：
\(X ≥ dp[i][j] – G[i-1][j] + P[i+j-1]\)
因为金币数量不能为负，最少需要的 X 是：
\(max(0, dp[i][j] – G[i-1][j] + P[i+j-1])\)
所以：
\(dp[i-1][j] = min(dp[i-1][j], max(0, dp[i][j] – G[i-1][j] + P[i+j-1]))\)
同理可得，从 (i, j) 向左方 (i, j – 1) 转移的公式为：
\(dp[i][j-1] = min(dp[i][j-1], max(0, dp[i][j] – G[i][j-1] + P[i+j-1]))\)
由于 (i – 1, j) 或 (i, j – 1) 可能也会被其他格子更新过，所以我们要在原有 dp 值基础上取 min，保持最优。
终点初始化:
终点为 (H – 1, W – 1)，到达这一天是第 H + W − 1 天（对应数组下标 H + W − 2）。
他当天收集 A[H – 1][W – 1] 个金币，然后需要花费 P[H + W − 2] 个金币买食物。
如果收集的金币不足，那差额就必须提前携带。因此：
\(dp[H-1][W-1] = max(0, P[H+W-2] – G[H-1][W-1])\)
最终答案：
完成逆向 DP 后，dp[0][0] 就是我们要求的答案——从起点出发，为了走完整个过程所需的最小初始金币数。
关键代码：
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<ll>> g(n + 10, vector<ll>(m + 10));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> g[i][j];
vector<int> p(n + m + 10);
for (int i = 0; i < n + m - 1; ++i)
cin >> p[i];
vector<vector<ll>> dp(n + 10, vector<ll>(m + 10, 1e18));
dp[n - 1][m - 1] = max(0ll, p[n + m - 2] - g[n - 1][m - 1]);
for (int i = n - 1; ~i; --i)
{
for (int j = m - 1; ~j; --j)
{
if (i)
dp[i - 1][j] = min(dp[i - 1][j],
max(0ll, p[i + j - 1] + dp[i][j] - g[i - 1][j]));
if (j)
dp[i][j - 1] = min(dp[i][j - 1],
max(0ll, p[i + j - 1] + dp[i][j] - g[i][j - 1]));
}
}
cout << dp[0][0] << endl;
}F – Max Combo
算法：
线段树。
思路：
定义线段树节点：
- l, r：区间左右端点。
- llen：从区间左边第一个字符开始，有多少个字符与第一个字符相同，直到遇到不同字符为止。
- rlen：从区间右边最后一个字符开始，有多少个字符与最后一个字符相同，直到遇到不同字符为止。
- alen：整个区间中，连续相同字符最长的一段的长度。
- lc, rc：区间左右端点字符。
合并操作（将两个区间合并为一个区间）：
- 新区间的llen：当左区间的全部字符都相等且与右区间的前面几个字符相等，就可将左区间的llen累加上右区间的llen赋值给新区间的rlen。
- 新区间的rlen：当右区间的全部字符都相等且与左区间的后面几个字符相等，就可将右区间的rlen累加上左区间的rlen赋值给新区间的rlen。
- 新区间的alen：当左区间的后缀与右区间的前缀相等且长度大于左区间的alen与右区间的alen，就可将新区间的alen更新。
修改操作：
递归到叶子节点，修改叶子节点信息，自底向上合并区间。
查询操作：
将区间拆分为线段树节点，合并拆分出的区间。
关键代码：
const int N = 5e5 + 10;
int n, q;
string s;
struct Node
{
int l, r;
int llen;
int rlen;
int alen;
char lc, rc;
} tr[N << 2];
Node merge(Node a, Node b)
{
Node ans = {a.l, b.r, a.llen, b.rlen, max({a.alen, b.alen}), a.lc, b.rc};
if (a.llen == a.r - a.l + 1 && a.rc == b.lc)
ans.llen += b.llen;
if (b.rlen == b.r - b.l + 1 && a.rc == b.lc)
ans.rlen += a.rlen;
if (a.rc == b.lc)
ans.alen = max(ans.alen, a.rlen + b.llen);
return ans;
}
void build(int u, int l, int r)
{
if (l == r)
{
tr[u] = {l, l, 1, 1, 1, s[l], s[l]};
return;
}
tr[u].l = l, tr[u].r = r;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}
void update(int u, int x, char c)
{
if (tr[u].l == tr[u].r)
{
s[x] = c;
tr[u].lc = tr[u].rc = c;
tr[u].llen = tr[u].rlen = tr[u].alen = 1;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid)
update(u << 1, x, c);
else
update(u << 1 | 1, x, c);
tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
}
Node query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
return query(u << 1, l, r);
if (l > mid)
return query(u << 1 | 1, l, r);
return merge(query(u << 1, l, r), query(u << 1 | 1, l, r));
}
void solve()
{
cin >> n >> q >> s;
s = ' ' + s;
build(1, 1, n);
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int pos;
char x;
cin >> pos >> x;
update(1, pos, x);
}
else
{
int l, r;
cin >> l >> r;
cout << query(1, l, r).alen << endl;
}
}
}G – Get Many Cola
还没补。
