洛谷虚拟赛-5的总结

分数 & 排名

预期分数：

$$ 100+100+50+20=270 $$

实际分数：

$$ 100+100+40+30=270 $$

排名 $10$

分析

T1 真的在送分

确实是‘在送分’，写个桶或是map就可以了

string s;
cin >> s;
int ss = s.size(), ans = 0;
for (int i = 0; i < 26; ++i) t[i] = false;
for (int i = 0; i < ss; ++i)
  if (!t[s[i] - 'A']) t[s[i] - 'A'] = true, ++ans;
cout << ss << ' ' << ans << '\n';

T2 你为什么不空间跳跃

一个分类讨论，三个min就了事了

bool t[26];
while (n--) {
  string s;
  cin >> s;
  int ss = s.size(), ans = 0;
  for (int i = 0; i < 26; ++i) t[i] = false;
  for (int i = 0; i < ss; ++i)
    if (!t[s[i] - 'A']) t[s[i] - 'A'] = true, ++ans;
  cout << ss << ' ' << ans << '\n';
}

T3 搬家到月球

nowtime就是当前的时间，优先队列顶就是下一个要取行李的人到 $0$ 的时间。

开始时，把每个人根据情况放入优先队列：

• 如果他在下行，那只要走下去就好了：l
• 如果他在上行，下次到的时间为 (m - l) + m，即到 $m$ 楼再下来的时间

对于每一次搬行李，我们只要取出优先队列顶，将 nowtime 设为它，nowtime + m * 2 就是他下一次回到 $0$ 层取行李的时间，所以我们要把他push回去

priority_queue<long long, std::vector<long long>, std::greater<long long>> q;
long long n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; ++i) {
  int l;
  bool o;
  cin >> l >> o;
  if (o)
      q.push((m - l) + m);
  else
      q.push(l);
}
long long nowtime;
for (int i = 0; i < k; ++i) {
  nowtime = q.top();
  q.pop();
  q.push(nowtime + m * 2);
}
cout << nowtime + m << '\n';

T4 两朵不具名的花

我们都知道，$ |x-y| $ 的取值有两种可能：$x-y$ or $ y-x$

如果我们知道 $ x<y $，此时 $ |x-y| $ 的取值是 $ y-x $，那么 $ x-y \leqslant 0 \leqslant y-x $

…未完