专栏文章

洛谷NOIP模拟赛总结

DDFbd
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min7pacy
此快照首次捕获于
2025/12/01 21:55
3 个月前
此快照最后确认于
2025/12/01 21:55
3 个月前
查看原文
复出第一场模拟赛，也是炸掉了。
预期：100 + 4 + 20 + 24
实际：100 + 0 + 20 + 24

T1

zrr题目，我还做了2h。
很多人写的二分，但是我想到了个离线的。
首先我们尽量选 mex⁡\operatorname{mex} 最大，大小最小的集合，直到没有 mex⁡\operatorname{mex} 大于 00 的，选的时候把 mex⁡\operatorname{mex} 的值和 mex⁡\operatorname{mex} 为该值的集合的数量组成一个二元组，按值从小到大插入一个数据结构里（我用的是栈）。
那么我们就把所有询问从大到小排序，然后从 mex⁡\operatorname{mex} 最小的集合里删就可以了。
还有一个问题，在一开始我们选集合的时候，是到没有 mex⁡\operatorname{mex} 大于 00 的集合时停下。而这样会剩下多余的数，这些数有可能需要新开一个集合，也有可能和选了的合并。
显然，只有选的集合只有一个，且多余的数中有这个集合的 mex⁡\operatorname{mex}，才会多开一个。
所以就做完了。
CPP
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 1e5 + 5;

struct node {
  ll v, id;
} m[kMaxN];

int t, n, q, a[kMaxN];
ll ans[kMaxN], mn[kMaxN], b[kMaxN];

bool cmp(node a, node b) {
  return a.v > b.v;
}

void solve() {
  cin >> n >> q;
  stack<node> st;
  ll r = 0, mx = 0, sum = 0;
  a[0] = -1;
  mn[0] = 1e9;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    if (a[i] == a[i - 1] + 1) {
      mn[i] = min(mn[i - 1], b[i]);
      if (mn[i])
        r = i;
    } else
      mn[i] = 0;
  }
  mn[r + 1] = 0;
  for (ll i = r; i; i--)
    if (mn[i] > mn[i + 1]) {
      st.push((node){i, mn[i] - mn[i + 1]});
      mx += i * (mn[i] - mn[i + 1]);
      sum += mn[i] - mn[i + 1];
    }
  for (int i = 1; i <= q; i++) {
    cin >> m[i].v;
    m[i].id = i;
  }
  sort(m + 1, m + q + 1, cmp);
  m[0].v = 1e18;
  for (int i = 1; i <= q; i++) {
    if (r && !m[i].v || m[i].v && st.empty()) {
      ans[m[i].id] = -1;
      continue;
    }
    if (m[i].v > mx)
      ans[m[i].id] = -1;
    else {
      ll l = min(m[i - 1].v, mx) - m[i].v;
      while (st.size() && st.top().v * st.top().id <= l) {
        l -= st.top().v * st.top().id;
        sum -= st.top().id;
        st.pop();
      }
      if (l) {
        node tmp = st.top();
        st.pop();
        ll x = l / tmp.v;
        tmp.id -= x;
        l -= x * tmp.v;
        sum -= x;
        if (l) {
          tmp.id--;
          if (tmp.id)
            st.push(tmp);
          st.push((node){tmp.v - l, 1});
        } else
          st.push(tmp);
      }
      ans[m[i].id] = sum + (st.size() == 1 && st.top().id == 1 && st.top().v != r || !st.size());
    }
  }
  for (int i = 1; i <= q; i++)
    cout << ans[i] << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for (cin >> t; t; t--)
    solve();
  return 0;
}

T2

比较弱智的是：我忘记完全背包了。
赛时思路和这个（怎么还被hack了）是一样的。
然后只能打暴力，发现暴力不会打，于是打特殊性质A，于是挂掉4pts。

T3

不是很会，只能20pts。

T4

没时间了，暴力赶紧跑路。

总结

看来忘记了不少基础知识，我的大脑大概是个滑动窗口。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...