A 小月的撤回
知识点:思维,分类讨论
撤回只有在目标消息此刻仍然存在时才真的少一条消息,而编号不会因为撤回而改变。所以第一次操作当且仅当 $1\le a\le n$ 生效,第二次当且仅当 $1\le b\le n$ 且 $b\ne a$ 生效:$a=b$ 时那条消息早在第一次就被撤回了,两次作用于不同编号时各减一条,其余情况不影响答案。
时间复杂度 $\mathcal O(1)$。
void solve() {
int n, a, b;
cin >> n >> a >> b;
cout << n - (a <= n) - (b <= n && b != a) << endl;
}
B 小月的打印
知识点:模拟
用一个变量记录坐标,一个变量记录方向,按题意模拟即可。
时间复杂度 $\mathcal O(|s|)$。
void solve() {
int n;
string s;
cin >> n >> s;
string ans(n, ' ');
int i = 0, d = 1;
for (char c : s) {
ans[i] = c;
i += d;
if (i == n || i == -1) d = -d, i += d;
}
cout << ans << endl;
}
C 小月的数差
知识点:前缀和,哈希表
把 1 记作 $+1$、0 记作 $-1$,前缀和 $p_0=0,\ p_i=p_{i-1}+w_i$。子串 $s[j+1..i]$ 的零一数量之差就是 $p_i-p_j$,合格当且仅当 $|p_i-p_j|=k$,也就是 $p_j=p_i-k$ 或 $p_j=p_i+k$。扫到 $i$ 时用哈希表查出这两种前缀和此前各出现过多少次并累加即可;$k=0$ 时两式相同,只累加一次,否则同一个子串会被数两遍。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n, k;
string s;
cin >> n >> k >> s;
unordered_map<int, int> cnt;
cnt[0] = 1;
int p = 0, ans = 0;
for (char c : s) {
p += c == '1' ? 1 : -1;
ans += cnt[p - k];
if (k) ans += cnt[p + k];
++cnt[p];
}
cout << ans << endl;
}
D 小月的总分
知识点:数学,前缀和
记 $S_i=\sum_{j\le i}a_j$。第 $i$ 次显示 $b_i$ 等价于
$$b_i(k+i)\le x+S_i<(b_i+1)(k+i),$$
也就是 $x$ 落在半开区间 $\bigl[b_i(k+i)-S_i,\ (b_i+1)(k+i)-S_i\bigr)$ 内。再加上 $x$ 是 $[0,km]$ 内的整数,所有显示给出的都是区间,它们的交仍然是一个半开区间 $[l,r)$,答案就是 $r-l$;交集为空则无解,输出 $0$。
时间复杂度 $\mathcal O(n)$。
void solve() {
int k, m, n;
cin >> k >> m >> n;
vector<int> a(n), b(n);
for (auto &v : a) cin >> v;
for (auto &v : b) cin >> v;
int l = 0, r = k * m + 1, s = 0;
for (int i = 0; i < n; ++i) {
s += a[i];
l = max(l, b[i] * (k + i + 1) - s);
r = min(r, (b[i] + 1) * (k + i + 1) - s);
}
cout << max(0LL, r - l) << endl;
}
E 小月的足迹
知识点:图论,思维
“边走边翻转方向”看似能扩大可达范围,实际不能。一条边每被通过一次就翻转一次,所以同一条边的各次使用在“原方向”和“反方向”之间严格交替,首次使用一定是原方向。若某一步是逆着原方向走的,那就是这条边的偶数次使用,说明此前已经顺着走过一次,两端也都到过了,这一步只是回头,不会踩到新结点;而顺着原方向走的一步恰是原图中的一条边。
于是从 $s$ 出发的每条原始有向路径都能直接走完(每条边只用一次),能访问的结点恰好是原图中从 $s$ 可达的结点,一次 BFS 统计即可。
时间复杂度 $\mathcal O(n+m)$。
void solve() {
int n, m, s;
cin >> n >> m >> s;
vector<vector<int>> g(n + 1);
for (int i = 0, u, v; i < m; ++i) cin >> u >> v, g[u].push_back(v);
vector<int> vis(n + 1);
queue<int> q;
vis[s] = 1, q.push(s);
while (q.size()) {
int u = q.front();
q.pop();
for (int v : g[u]) if (!vis[v]) vis[v] = 1, q.push(v);
}
cout << count(vis.begin(), vis.end(), 1) << endl;
}
F 小月的取物
知识点:动态规划,思维
一旦取了第二件 $a_{i+1}$,$a_i$ 就卡在队头,此后既可以继续取第二件 $a_{i+2},a_{i+3},\dots$ ,也可以随时回头把 $a_i$ 取走;回头之后紧接着取的那件又成了新的“队头待取”物品。所以整个取走顺序必然是若干段的拼接,段 $[l..r]$ 内的顺序固定为 $a_{l+1},a_{l+2},\dots,a_r,a_l$($l=r$ 时就是 $a_l$),各段恰好划分 $[1..n]$。
按段从左往右 DP。记 $d_i=|a_{i+1}-a_i|$,$pre_i=d_1+\dots+d_i$,用 $f[l]$ 表示已取完 $1..l-1$、且以 $l$ 开头的段已取了 $a_{l+1}$($l<n$),$g[l]$ 表示已取完 $1..l$、且 $l$ 所在段是单点段 $[l..l]$。若上一段是 $[p..l-1]$、收尾后停在 $a_p$,它的代价是
$$\text{cur}(p)=\begin{cases}g[p],&p=l-1,\\[2pt] f[p]+(pre_{l-2}-pre_p)+|a_{l-1}-a_p|,&p<l-1,\end{cases}$$
第二行是先沿 $a_{p+1},a_{p+2},\dots,a_{l-1}$ 往后推,再回头把 $a_p$ 取走。接下来若下一段是单点就接 $a_l$,否则先取 $a_{l+1}$:
$$g[l]=\min_p\bigl(\text{cur}(p)+|a_l-a_p|\bigr),\qquad f[l]=\min_p\bigl(\text{cur}(p)+|a_{l+1}-a_p|\bigr).$$
最后一段同样要收尾,答案为 $g[n]$ 与 $\min_{p<n}\bigl(f[p]+(pre_{n-1}-pre_p)+|a_n-a_p|\bigr)$ 中的较小值。
时间复杂度 $\mathcal O(n^2)$。
constexpr int inf = 2e18 + 9;
void solve() {
int n;
cin >> n;
vector<int> a(n + 2);
for (int i = 1; i <= n; ++i) cin >> a[i];
if (n == 1) return cout << 0 << endl, void();
vector<int> pre(n + 1), f(n + 1, inf), g(n + 1, inf);
for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + abs(a[i + 1] - a[i]);
f[1] = g[1] = 0;
for (int l = 2; l <= n; ++l) {
for (int p = 1; p < l; ++p) {
int cur = p == l - 1 ? g[p] : f[p] + pre[l - 2] - pre[p] + abs(a[l - 1] - a[p]);
g[l] = min(g[l], cur + abs(a[l] - a[p]));
if (l < n) f[l] = min(f[l], cur + abs(a[l + 1] - a[p]));
}
}
int ans = g[n];
for (int p = 1; p < n; ++p) ans = min(ans, f[p] + pre[n - 1] - pre[p] + abs(a[n] - a[p]));
cout << ans << endl;
}
约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
使用到的算法模板见 $\tt Github$ 仓库 林月的XCPC模板库