Haokee Note

2025.11.27 模拟赛

8 min read

王国边缘

模拟 倍增 二分

首先如果坐标都是在模 意义下的话，这 个位置的下一步走法是固定的。这个可以 或 处理出来。（注意对 和 的特别处理。我为了方便搞了 长的，但是当 时循环了需要特殊处理）

接下来我就开始发癫了。我想得是没错的，从一个地方走了若干步之后一定会到环上并且不会出来，所以维护环就行了。但是事情并没有这么简单。

因为我们不止需要知道模 意义下的位置，还需要知道实际的位置。这个实际位置有很多可能，我们不知道，所以需要记录走到下一步所进行的位移。于是我们就需要维护环上的位移前缀和、环周围的链的前缀和……非常复杂，而且讨论很多。

最后发现我是大煞笔。像这种走若干步的问题，直接倍增就行了。 预处理出倍增数组，然后每次走 步，最后拼出询问的 即可。时间复杂度 。

需要注意取模部分，因为输入的就有 了。

const LL kMaxN = 2e5 + 5, kLog = 63, kMod = 1e9 + 7;
 
// 走 2^k 步能到达的 (mod n) 的地方和 Δx
LL nxt[kLog][kMaxN], val[kLog][kMaxN], n, m, q;
vector<LL> v;
string a;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> q >> a;
  a = " " + a + a;
  for (LL i = 1; i <= 2 * n; i++) {
    if (a[i] == '1') {
      v.push_back(i);
    }
  }
  LL zrr = m / n, wyy = m % n;
  for (LL i = 1; i <= n; i++) {
    if (v.empty()) {
      nxt[0][i] = i % n + 1;
      val[0][i] = 1;
      continue;
    }
    if (m <= n) {
      auto p = upper_bound(v.begin(), v.end(), i + m);
      if (p == v.begin()) {
        nxt[0][i] = i % n + 1;
        val[0][i] = 1;
        continue;
      }
      LL x = *prev(p);
      if (x > i) {
        nxt[0][i] = (x - 1) % n + 1;
        val[0][i] = x - i;
      } else {
        nxt[0][i] = i % n + 1;
        val[0][i] = 1;
      }
    } else {
      auto p = upper_bound(v.begin(), v.end(), i + wyy);
      // 要么在 [1, i+wyy] 当中，如果没有必然 i+wyy<n 且在 (i+wyy,n] 中
      if (p == v.begin()) {
        p = upper_bound(v.begin(), v.end(), n);
        LL x = *prev(p);
        nxt[0][i] = x;
        val[0][i] = (zrr - 1) * n + x - i;
        continue;
      }
      LL x = *prev(p);
      nxt[0][i] = (x - 1) % n + 1;
      val[0][i] = zrr * n + x - i;
    }
    val[0][i] %= kMod;
  }
  for (LL i = 1; i < kLog; i++) {
    for (LL j = 1; j <= n; j++) {
      nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
      val[i][j] = (val[i - 1][j] + val[i - 1][nxt[i - 1][j]]) % kMod;
    }
  }
  for (LL x, k; q; q--) {
    cin >> x >> k;
    LL ans = x % kMod;
    x = (x - 1) % n + 1; 
    for (LL i = 0; i < kLog; i++) {
      if (k >> i & 1) {
        ans = (ans + val[i][x]) % kMod;
        x = nxt[i][x];
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

买东西题

贪心 优先队列

我最开始写了一个线段树的做法。

具体来说，我做个贪心，把折扣优惠 更多的排在前面，然后用线段树维护下标 所对应的 的区间最小值。按照 从大到小的顺序枚举每张优惠券，在所有 大于等于 的商品中取出 最小的买掉（这样实际收益更多），然后把它从线段树当中删除。其它的用 买。

这个算法不出意料地在大样例上面 TLE 了。 越大的放前面不一定好，因为 的限制，如果前一个限制更小，然后把 小的夺走了；后面一个 小一些，但是它限制大，被前面的夺走了。这样子本来这两张优惠券全部可以用上的，结果最后只能用上一张，答案就不对。

既然我们没办法一次就找出哪张优惠券对应哪个商品，所以回归老本行：反悔贪心。

首先，对于一个新物品，它有三种选择策略：

  1. 不使用优惠券用折扣价买；
  2. 把之前的一个物品的优惠券抢过来用，再给被抢的补一张（相当于新用一个然后交换）；
  3. 把之前的一个物品的优惠券抢过来用，但不补偿。

第二个操作最长，但是我们实际上只需要按照 从小到大的顺序排序处理就不会用到第二种情况了。因为在交换前后都是合法的情况下，交换前后的收益是一样大的。

所以我们只需要考虑第三种情况就行了。反悔贪心的本质就是把第三种情况变到第一种情况去。由于我们是按照 排序的，所以 抢 是一定符合条件的。

好的。假设 抢了 ，抢的优惠券优惠力度为 （由于 递增所以抢过来合法）。那么抢之前的收益：

抢之后的收益

我们要把抢的过程看作用了一个新的优惠券，那么这个优惠券具体是多少的优惠力度呢？设为 ，有

所以 。

代码就很简单了。由于 单调递增，我们给优惠券的限制 也排个序，那么可用的优惠券在序列中就是一个单调边长的前缀。优惠券用优先队列（大根堆）维护（因为维护的都是可以作用的，所以只需要优惠力度大的放前面即可）。

时间复杂度 。

const LL kMaxN = 1e6 + 5;
 
LL n, m, ans;
pair<LL, LL> a[kMaxN], b[kMaxN];
priority_queue<LL> q;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a + 1, a + n + 1);
  for (LL i = 1; i <= m; i++) {
    cin >> b[i].first >> b[i].second;
  }
  sort(b + 1, b + m + 1);
  for (LL i = 1, j = 1; i <= n; i++) {
    for (; j <= m && b[j].first <= a[i].first; j++) {
      q.push(b[j].second);
    }
    if (q.size() && q.top() > a[i].first - a[i].second) {
      ans += a[i].first - q.top();
      q.pop();
      q.push(a[i].first - a[i].second);
    } else {
      ans += a[i].second;
    }
  }
  cout << ans << '\n';
  return 0;
}

IMAWANOKIWA (Construction ver.)

不会写，暴力都没打。 分。

魔法少女们

不会写，暴力都没打。 分。

Graph View