专栏文章

2025-11-20 NOIP模拟赛总结

lliuyi0905
生活·游记参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min44s09
此快照首次捕获于
2025/12/01 20:15
3 个月前
此快照最后确认于
2025/12/01 20:15
3 个月前
查看原文

【MX-S6】梦熊 NOIP 2024 模拟赛 2 &「KDOI」Round 11（同步赛）

又挂在 T1 了……😭 痛失 4040 pts……什么时候给一组强一点的大样例😞 还好后面的题没有挂分，不然又要垫底了
只有 60+100+55+4=21960 + 100 + 55 + 4 = 219，好惨

A

比较简单的一道模拟题，很快就想到了。
直接存下每个打印机正在打印的文件，用优先队列或者 set 之类的东西维护，每次求一下最小值就可以了。
可真正开始写的时候才发现并没有想象中的那么容易，要处理的地方还挺多的。要对 tit_i 和 ti+sit_i + s_i 离散化，还要维护每个打印机正在打印的文件，每个打印机的文件的结束时间的最大值和最小值也要维护，还要求每个结束时间对应的打印机……一点也不好搞。
写了半个小时，再调试了一下，居然一遍就过了所有大样例！本来以为一道细节这么多的题要调好久的。看着样例还挺大的，简单分析了一下，感觉过了样例就没事了，于是看 T2 去了。
打印 / printCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;
const int N = 4e5 + 5;
LL n, m, k, b[N], l[N], r[N];
array<LL, 3> a[N];
vector<int> v[N];
unordered_map<LL, LL> f;
set<LL> p[N];
set<Pii> s;
priority_queue<LL, vector<LL>, greater<LL>> q[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (LL i = 1, x, y; i <= n; i++) {
    cin >> x >> y;
    a[i] = {y, x, i}, b[2 * i - 1] = y, b[2 * i] = x + y;
  }
  sort(b + 1, b + 2 * n + 1);
  int w = unique(b + 1, b + 2 * n + 1) - b - 1;
  for (int i = 1; i <= w; i++) f[b[i]] = i;
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= m; i++) r[i] = 1e18, s.insert({0, i});
  for (int i = 1; i <= n; i++) {
    auto [y, x, d] = a[i];
    for (int j = f[a[i - 1][0]] + 1; j <= f[y]; j++) {
      for (int k : p[j])
        for (; q[k].size() && q[k].top() <= f[y]; q[k].pop())
          q[k].size() == 1 && (s.erase({l[k], k}), s.insert({l[k] = 0, k}), r[k] = 1e18);
      p[j].clear();
    }
    int k = (*s.begin()).second;
    s.erase({l[k], k}), r[k] != 1e18 && (p[r[k]].erase(k));
    q[k].push(f[x + y]), v[k].push_back(d);
    l[k] = max(l[k], x + y), r[k] = min(r[k], f[x + y]);
    s.insert({l[k], k}), p[r[k]].insert(k);
  }
  for (int i = 1; i <= m; i++) {
    sort(v[i].begin(), v[i].end());
    cout << v[i].size() << " ";
    for (int x : v[i]) cout << x << " ";
    cout << "\n";
  }
  return 0;
}
当时也是太糖了，没有意识到一个打印机的结束时间并不是 max⁡{ti+si}\max\{t_i + s_i\}，因为打印机并不能同时处理多个文件，而是得一个一个单独处理。可这么简单的错误为什么大样例都过了呢？想不明白。
打印 / printCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;
const int N = 4e5 + 5;
LL n, m;
array<LL, 3> a[N];
set<int> v[N];
priority_queue<int, vector<int>, greater<int>> t;
priority_queue<Pii, vector<Pii>, greater<Pii>> q;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i][1] >> a[i][0], a[i][2] = i;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= m; i++) t.push(i);
  for (int i = 1; i <= n; i++) {
    auto [x, s, p] = a[i];
    for (; q.size() && q.top().first <= x; q.pop()) t.push(q.top().second);
    if (t.size()) {
      v[t.top()].insert(p);
      q.push({x + s, t.top()}), t.pop();
    } else {
      auto [t, k] = q.top();
      v[k].insert(p), q.pop(), q.push({t + s, k});
    }
  }
  for (int i = 1; i <= m; i++) {
    cout << v[i].size() << " ";
    for (int x : v[i]) cout << x << " ";
    cout << "\n";
  }
  return 0;
}

B

最开始没想到，感觉是什么神秘 dp 题，不过感觉状态非常不好设计，也不好处理，就先写 T3 去了。T3 一写就是写到十一点，都没什么时间做 T2 了。
好在在 zrr 的帮助下，一下子就发现了一个神秘小结论：vv 最多乘 3030 次 22 或者 2020 次 33，因为 2302 ^ {30} 和 3203 ^ {20} 已经超过 10910^9 了，而且 ti≤1t_i \le 1，所以没有必要继续加速。
有了这个结论，简直不要太高兴。感觉马上就可以写出来了，设 fi,j,kf_{i, j, k} 表示到点 ii 且速度为 2j×3k2^j \times 3^k 所需的最小时间，状态转移方程：
fi,j,k=fi−1,j,k+pi−pi−12j×3kf_{i, j, k} = f_{i - 1, j, k} + \frac{p_i - p_{i - 1}}{2^j \times 3^k}
和
fi,j,k=ti+{fi,j,kxi=1fi,j−1,kxi=2fi,j,k−1xi=3fi,j−2,kxi=4f_{i, j, k} = t_i + \begin{cases}f_{i, j, k} & x_i = 1\\f_{i, j - 1, k} & x_i = 2\\f_{i, j, k - 1} & x_i = 3\\f_{i, j - 2, k} & x_i = 4\end{cases}
把 pp 和 yy 放到一起排序，跑一遍 dp 就可以了。zrr 还是太可爱了，我一遍就写了出来。
发现 MLE 了，不过都是小问题，直接把第一维干掉就可以了。发现 TLE 了，该范围，预处理，卡卡常。最终在洛谷跑了 400ms，也不算慢啊。
飞船 / shipCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5;
int n, q;
double f[31][21], s[N], p[2][31];
array<LL, 3> a[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++)
    cin >> a[i][0] >> a[i][2] >> a[i][1];
  for (int i = 1; i <= q; i++) {
    cin >> a[n + i][0], a[n + i][2] = i, s[i] = 1e18;
  }
  sort(a + 1, a + n + q + 1);
  for (int i = p[0][0] = p[1][0] = 1; i <= 30; i++) {
    p[0][i] = p[0][i - 1] * 2, p[1][i] = p[1][i - 1] * 3;
  }
  fill(f[0] + 1, f[0] + 31 * 21, 1e18);
  for (int i = 1; i <= n + q; i++)
    for (int x = 30; ~x; x--)
      for (int y = 20; ~y; y--) {
        f[x][y] += (a[i][0] - a[i - 1][0]) / (p[0][x] * p[1][y]);
        if (a[i][1]) {
          int u = x + (a[i][1] == 2 ? 1 : (a[i][1] == 4 ? 2 : 0));
          int v = y + (a[i][1] == 3 ? 1 : 0);
          u <= 30 && v <= 20 && (f[u][v] = min(f[u][v], f[x][y] + a[i][2]));
        } else {
          s[a[i][2]] = min(s[a[i][2]], f[x][y]);
        }
      }
  for (int i = 1; i <= q; i++) {
    cout << fixed << setprecision(9) << s[i] << "\n";
  }
  return 0;
}

C

非常困难的一道题，甚至在题面上就花了我十多分钟时间……
最开始毫无头绪，注意力涣散。突然发现定义一个字符串是好的，它也可以是空串。所以对于每个 [l,r][l, r]，求出使 R1+R2+⋯+Rk=T[l,r]R_1 + R_2 + \cdots + R_k = T[l, r] 的最小的 kk，那么三元组 (l,r,k),(l,r,k+1),⋯ ,(l,r,K)(l, r, k), (l, r, k + 1), \cdots, (l, r, K) 应该都是好的。于是就可以愉快的 dp 了。
因为一个好字符串必须是 SiS_i 的前缀，所以考虑把 SiS_i 的所有前缀都调出来作为最终的字符串。设 fi,jf_{i, j} 表示使得三元组 (l,r,k)(l, r, k) 是好的的最小的 kk，则状态转移方程为
fi,j=min⁡1≤k≤n∧sk=T[j−∣sk∣+1,j]{fj−∣sk∣+1}f_{i, j} = \min_{1 \le k \le n \land s_k = T[j - |s_k| + 1, j]}\{f_{j - |s_k|} + 1\}
第二问就可以直接差分，时间复杂度 O(n∣T∣2∣S∣)\mathcal{O}(n|T|^2|S|)，于是就愉快的得到了 3030 分😁
突然脑抽想到一个神秘做法：对于每一种满足 si=T[j−∣si∣+1,j]s_i = T[j - |s_i| + 1, j] 的 i,ji, j，连一条 j−∣si∣+1→jj - |s_i| + 1 \to j 的边。对于每一个起点 ii 跑广搜，则 fi,j=djf_{i, j} = d_j。这样就可以做到 O(∣T∣(∣T∣+n∣S∣))\mathcal{O}(|T|(|T| + n|S|)) 求出答案。
还有一个特殊性质：所有字符均为 a。容易发现，所有长度小于等于 max⁡{∣Si∣}\max\{|S_i|\} 的 a 串都有，所以一个区间 [l,r][l, r] 的最小 kk 应该是 ⌈r−l+1max⁡{∣Si∣}⌉\lceil{\frac{r - l + 1}{\max\{|S_i|\}}\rceil}。再通过一下奇怪的观察和计算贡献就可以做出来。
ez 55 pts
字符串 / stringCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ull = unsigned long long;
const int N = 5e5 + 5;
LL T, n, m, k, o[N], f[N], d[N];
vector<int> e[N];
ull h[N], v[N], p[N];
string s, t;
ull H(int l, int r) {
  return v[r] - v[l - 1] * p[r - l + 1];
}
void B(int s) {
  fill(f + 1, f + n + 1, 1e18);
  queue<int> q;
  for (q.push(s), f[s] = 0; q.size(); q.pop()) {
    int u = q.front();
    for (int v : e[u])
      f[u] + 1 < f[v] && (f[v] = f[u] + 1, q.push(v), 1);
  }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> T >> n >> m;
  if (T == 15) {
    for (int i = 1; i <= n; i++)
      cin >> s, k = max(k, LL(s.size()));
    cin >> t, n = t.size();
    LL c = 0;
    for (int i = 1; i <= n; i++) {
      f[i] = f[i - 1] + max(0ll, m - (i + k - 1) / k + 1), c += f[i];
    }
    cout << c << "\n";
    for (int i = 1; i <= (n + 1) / 2; i++) {
      d[i] = d[i - 1] + f[n - i + 1] - f[i - 1];
      cout << d[i] << " ";
    }
    for (int i = n / 2; i; i--) cout << d[i] << " ";
    exit(0);
  }
  for (int i = 1; i <= n; i++) {
    cin >> s;
    for (int i = h[0] = 0; i < s.size(); i++) {
      o[++k] = i + 1, h[k] = (h[0] = h[0] * 131 + s[i]);
    }
  }
  cin >> t, n = t.size(), t = " " + t;
  for (int i = p[0] = 1; i <= n; i++) {
    v[i] = v[i - 1] * 131 + t[i], p[i] = p[i - 1] * 131;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= k; j++)
      o[j] <= i && H(i - o[j] + 1, i) == h[j] && (e[i - o[j]].push_back(i), 1);
  LL c = 0;
  for (int l = 1; l <= n; l++) {
    B(l - 1);
    for (int r = l; r <= n; r++) {
      LL w = max(0ll, m - f[r] + 1);
      c += w, d[l] += w, d[r + 1] -= w;
    }
  }
  cout << c << "\n";
  for (int i = 1; i <= n; i++) cout << (d[i] += d[i - 1]) << " ";
  return 0;
}

D

没太多时间了，先写了一个纯暴力，再写了 l=1l = 1 的特殊性质。可 l=1l = 1 的特殊性质因为底数少减了一个 11 导致大样例未过，一直没有调出，只得放弃。
彩灯晚会 / partyCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 305, M = 998244353;
LL T, n, k, l, m, a[N], c[N], s, f[N];
vector<int> e[N];
void S(int u, int k, int d) {
  if (d == l) return c[k]++, void();
  for (int v : e[u]) a[v] == k && (S(v, k, d + 1), 1);
}
LL C() {
  fill(c + 1, c + k + 1, 0);
  for (int i = 1; i <= n; i++) S(i, a[i], 1);
  LL s = 0;
  for (int i = 1; i <= k; i++) s = (s + c[i] * c[i] % M) % M;
  return s;
}
void D(int x) {
  if (x > n) return s = (s + C()) % M, void();
  for (int i = 1; i <= k; i++) a[x] = i, D(x + 1);
}
LL P(LL x, LL y) {
  LL s = 1;
  for (; y; x = x * x % M, y >>= 1) y & 1 && (s = s * x % M);
  return s;
}
LL Z(int n, int m) {
  return f[n] * P(f[m] * f[n - m] % M, M - 2) % M;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> T >> n >> k >> l >> m;
  if (l == 1) {
    for (int i = f[0] = 1; i <= n; i++) f[i] = f[i - 1] * i % M;
    for (int i = 1; i <= n; i++) {
      s = (s + i * i % M * Z(n, i) % M * P(k - 1, n - i) % M) % M;
    }
    cout << s * k % M;
  } else {
    for (int u, v, c; m; m--)
      for (cin >> u >> v >> c; c; c--) e[u].push_back(v);
    D(1), cout << s;
  }
  return 0;
}

评论

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

正在加载评论...