Haokee Note

2025.7.22 模拟赛

9 min read

LIS

优先队列 序列dp

首先注意到每次从 跳到 其中的 都会是最小的一个，因此不难维护一个优先队列，按照 从小到大排序，附加维护编号 。从前往后依次遍历每一个元素 ，规定优先队列里面维护的是所有 的还没有进行没有转移的元素，此时我们在优先队列头依次取出若干个满足 的元素，进行 的转移。那么问题来了，如何进行转移呢？

维护两个值 和 ，分别表示以 为结尾的转移序列的数量和总和，那么很显然 ，而我们要转移到 时 的每一个序列都会在末尾增加一个元素，因此 。初始时 。

现在我们已经算出了所有的 和 ，该如何统计答案呢？实际上，我们可以在转移的途中顺便统计答案。对于 的转移，如果 中的 正好 ，那么这个状态实际上是转移不了的，这时候就可以对 统计答案了，。时间复杂度 。

对于最后无法继续转移但是没有被 限制的状态，我们可以添加一个哨兵 ，这样遍历到 时就会全部转移。

#include <iostream>
#include <queue>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 4e5 + 5;
 
LL a[kMaxN], f[kMaxN], dp[kMaxN], t, n, ans;
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<pair<LL, LL>>> q;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
    }
    a[n + 1] = 1e18;
    f[1] = dp[1] = 1;
    for (; q.size(); q.pop()) { }
    q.emplace(a[1], 1);
    ans = 0;
    for (LL i = 2; i <= n + 1; i++) {
      f[i] = dp[i] = 1;
      for (; q.size() && q.top().first < a[i]; q.pop()) {
        f[i] += f[q.top().second];
        dp[i] += dp[q.top().second] + f[q.top().second];
        ans += (i - q.top().second) * dp[q.top().second];
      }
      q.emplace(a[i], i);
    }
    cout << ans << '\n';
  }
  return 0;
}

碰瓷

序列dp

本题我的方法错误。

我最开始的方法是，枚举 的每一个可能的起始点 ，然后设计 dp 状态 表示为 可以与 进行匹配，但是这个算法不仅转移困难，而且时间复杂度高达 。

我成功地获得了 分的好成绩的原因是我的转移过程写错了。具体而言，对于在 中相同位置插入多个新元素的转移，我没有一个好的转移方式能够满足所有的可能。比如 后面添加 再添加 这种。

旋律

unknow

此题我采用的是暴力。

对于向前插入和向后插入的操作，我手动维护一个双端队列，分别用 和 表示队列的头和尾。为了防止一直往前面插入，我初始化 ，然后将数组大小初始化为 。

接下来考虑统计答案。观察样例，可以发现，如果我们选择前 个数作为旋律，那么 的数都必须满足 。因此我们使用 vector 的数组维护每一个 ，满足 ，的 的数量（即当前位置满足条件的所有的 ）。

然后进行倒叙枚举 ，使用一个表 记录 被”命中”的次数，将 的我们之前记录过的所有满足条件的 的值，对应的 加上 。如果有 的值正好等于我们已经遍历过的元素数量（），那么这个答案就是符合要求的。

我这个方法最坏时间复杂度高达 ，因为虽然单次修改是 的，但是所有 vector 里面的元素数量最坏是 量级的（即所有字母都一样的情况），因此时间复杂度为 ，只能通过 分。

#include <iostream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 2e6 + 5;
 
int f[kMaxN], n, l, r, ans;
char s[kMaxN], c;
vector<int> v[kMaxN];
 
void insertLeft(char c) {
  s[--l] = c;
}
 
void insertRight(char c) {
  s[++r] = c;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  l = 1e6, r = l - 1;
  for (int i = 1, o; i <= n; i++) {
    cin >> o >> c;
    if (o == 1) {
      insertLeft(c);
      for (int i = l + 1; i <= r; i++) {
        if (s[i] == c) {
          v[i].push_back(i - l);
        }
      }
    } else {
      insertRight(c);
      for (int i = l; i < r; i++) {
        if (s[i] == c) {
          v[r].push_back(r - i);
        }
      }
    }
    fill(f + 1, f + r - l + 1, 0);
    ans = 1;
    for (int i = r; i > l; i--) {
      for (int j : v[i]) {
        f[j]++;
      }
      ans += f[i - l] == r - i + 1;
    }
    cout << ans << '\n';
  }
  return 0;
}

非负

unknow

这道题目我只骗了 分，即 的情况。

对于这种情况，首先如果 或 等于 那 肯定是不满足条件的，因为长度为 的前缀和后缀不大于等于 ，此时我们直接 或 ，这样因为 是 交替出现，所以在我们操作之后 和 都是 。

接下来，既然 是 和 交替出现了，那么前缀和后缀的值是 交替出现的，满足条件，直接输出 ，成功获得 分。

#include <iostream>
#include <set>
 
using namespace std;
 
const int kMaxN = 5e5 + 5;
 
int a[kMaxN], p[kMaxN], dp[kMaxN], n, q;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int o, p, l, r; q; q--) {
    cin >> o;
    if (o == 1) {
      cin >> p;
      a[p] = -a[p];
    } else {
      cin >> l >> r;
      if (a[l] == -1) {
        l++;
      }
      if (a[r] == -1) {
        r--;
      }
      cout << max(0, r - l + 1) << '\n';
    }
  }
  return 0;
}

总结

本次得分 。

问题就是，第二题暴力写挂了，直接蒸发 分；第四题最开始看错题了，写了一个小时之后才发现，后面就没有时间写正经暴力，连 分的大爆搜也没写。

以后再次遇到像第二题这样的题目时，我应该更仔细地进行转移，避免犯同样的错误。同时稳住心态，多尝试不同的转移方式，因为我当时的状态设计和转移思路已经和正确的暴力 dp 一样了。下次再次遇到这种题目时，我应该更加冷静地思考，避免犯同样的错误，争取把该拿的分拿到手，之后再去写后面的题目。

Graph View