题解 | 牛客周赛 Round 171

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模板库

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇