2025.10.7 模拟赛

返乡

找规律数学三维偏序

首先观察 $n = 2$ 的样例，先猜测 $k$ 的值，发现和 $n$ 还有 $n + 1$ 没有比较直接的关系，所以直接去看方案的规律。看之前按照字典序排一下，不然很难看。

最开始我是竖着看的，观察 $a, b, c$ 组内的规律，但是发现组之间是有关联的所以失败了。于是就可以想到横着看，不难发现每一行的和都是 $3$ ，所以我们可以想出一种构造方案：选择一个正整数 $S$ 让每一组的和都是 $S$ 。

首先证明这种构造方案不会产生偏序二元组。

[n] 考虑任意两个不同的三元组 $(a_{1}, b_{1}, c_{1})$ 和 $(a_{2}, b_{2}, c_{2})$ 均满足和为 $S$ ，假定第一个三维均小于等于第二个，那么前两维就是满足的，即 $a_{1} \leq a_{2}, b_{1} \leq b_{2}$ ，而 $c_{1} = S - a_{1} - b_{1}$ ， $c_{2} = S - a_{2} - b_{2}$ ，所以有 $c_{1} \geq c_{2}$ 。
1. $c_{1} \neq = c_{2}$ ，则有 $c_{1} > c_{2}$ ，不满足偏序条件；
2. $c_{1} = c_{2}$ ，那么 $a_{1} \neq = a_{2}$ 或 $b_{1} \neq = b_{2}$ ，则有 $a_{1} + b_{1} < a_{2} + b_{2}$ ，所以 $c_{1} > c_{2}$ ，不满足偏序条件。
综上不存在这种二元组，证明就成功了。

那么如何证明这种构造方案是最优的呢？我只会感性证明。

[n] 如果现在前两维已经固定了，你需要选择第三维，那么第三维最多只能选一个，而我们选择 $c = S - a - b$ 是一定可以满足条件的，所以就选这个了。

现在我们需要找到最优的 $S$ ，可以通过简单 $O (n^{2})$ 或者 $O (n^{3})$ 找到，但是可以直接令 $S \leftarrow ⌊ \frac{3 n}{2} ⌋$ 。

为什么这个最优呢？根据儒家思想当中的“中庸”不难想到， $S$ 为一个中间值的时候最佳，而 $a + b + c$ 的最大值为 $3 n$ ，这就提示我们取 $3 n$ 的一半是最优的，证明不会。

所以我们只需要 $O (n^{2})$ 枚举前两个再算出第三个即可。

#include <fstream>
#include <vector>
#include <tuple>
 
using namespace std;
 
ifstream cin("home.in");
ofstream cout("home.out");
 
int k, s;
vector<tuple<int, int, int>> v; 
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> k;
  s = 3 * k / 2; 
  for (int a = 0; a <= k; a++) {
    for (int b = 0; b <= k; b++) {
      int c = s - a - b;
      if (0 <= c && c <= k) {
        v.emplace_back(a, b, c);
      }
    }
  }
  cout << v.size() << '\n';
  for (const auto &i : v) {
    cout << get<0>(i) << ' ' << get<1>(i) << ' ' << get<2>(i) << '\n';
  }
  return 0;
}

连接

找规律数学 ST表线段树单调队列二分

首先取的一段，它两边的至少一边是正好卡在连接处的。

[n] 因为如果两边均不在连接处上，可以去掉密度小的那一边，吞掉密度大的那一边，同时保证总质量不变。

所以可以正反跑两边，每一遍枚举 $i$ 表示以第 $i$ 块的左边作为左端点的答案。右端点的话是有可能不在连接处上的，但是汇总而来一共只有两种情况不在连接处上。

质量不够 $L$ 往后吞一些。
质量超出 $R$ 了删掉末尾一段。

由于 $i$ 单调递增，质量均为正，所以可以维护双指针 $s, t$ ，表示对于 $L$ 而言可以吞掉 $i \sim s$ 的所有整块、对于 $R$ 而言可以吞掉 $i \sim t$ 的所有整块，那么补充的散块可以通过 $s + 1$ 和 $t + 1$ 得到。

另外所有的情况均是右端点也在连接处上的情况。

[n] 如果右端点属于 $(s, t)$ 但是不在连接处上，若该端点的密度大于答案密度，那么可以把这一整块都吞掉更优；反之删掉这一块。总之都不会更劣。

然而求最大的加权平均值比较复杂，于是我们就可以想到实数二分。

若当前期望的答案为 $x$ ，设右端点为 $j$ ，总长为 $S = k = i \sum j l_{k}$ ，那么有

k = i \sum j \frac{l _{k} p _{k}}{S} - x \geq 0

两端同乘 $S$ 得

k = i \sum j l_{k} p_{k} - k = i \sum j l_{k} x \geq 0 \Leftrightarrow k = i \sum j l_{k} (p_{k} - x) \geq 0

可以先做前缀和，然后 ST 表维护区间最大值（也可以线段树、单调队列等），查询一下能否减成大于等于 $0$ 即可。

[!] 注意一定要调用跑两遍的函数而非跑一遍，否则会和我一样挂 $95$ 分。
[c] 数据太垃圾了。

时间复杂度 $O (n lo g_{2} n lo g_{2} V)$ ，直接卡过。

#include <fstream>
#include <algorithm>
#include <iomanip>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 3e5 + 5, kLog = 20;
const double eps = 1e-7;
 
ifstream cin("connect.in");
ofstream cout("connect.out");
 
LL l[kMaxN], p[kMaxN], sum[kMaxN], pl[kMaxN], lg[kMaxN], n, low, high;
double dp[kMaxN][kLog], ans;
 
LL query(LL p[], LL l, LL r) {
  return p[r] - p[l - 1];
}
 
double queryMax(LL l, LL r) {
  LL k = lg[r - l + 1];
  return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
 
bool solve(double x) {
  for (LL i = 1; i <= n; i++) {
    pl[i] = pl[i - 1] + l[i];
    dp[i][0] = dp[i - 1][0] + 1.0 * l[i] * (p[i] - x);
    sum[i] = sum[i - 1] + l[i] * p[i];
  }
  for (LL j = 1; j < kLog; j++) {
    for (LL i = 1; i + (1 << j) - 1 <= n; i++) {
      dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (LL i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  for (LL i = 1, s = 0, t = 0; i <= n; i++) {
    for (; s < n && query(sum, i, s + 1) <= low; s++) { }
    for (; t < n && query(sum, i, t + 1) <= high; t++) { }
    LL res = low - query(sum, i, s);
    if (!res && query(sum, i, s) >= x * query(pl, i, s) || 
        s < n && low >= x * (query(pl, i, s) + 1.0 * res / p[s + 1])) {
      return 1;
    }
    res = high - query(sum, i, t);
    if (!res && query(sum, i, t) >= x * query(pl, i, t) ||
        t < n && high >= x * (query(pl, i, t) + 1.0 * res / p[t + 1])) {
      return 1;
    }
    if (s < t && queryMax(s + 1, t) - dp[i - 1][0] >= 0) {
      return 1;
    }
  }
  return 0;
}
 
bool check(double x) {
  if (solve(x)) {
    return 1;
  }
  reverse(l + 1, l + n + 1);
  reverse(p + 1, p + n + 1);
  return solve(x);
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> low >> high;
  for (LL i = 1; i <= n; i++) {
    cin >> l[i];
  }
  for (LL i = 1; i <= n; i++) {
    cin >> p[i];
  }
  for (double l = 1, r = 1e6; r - l > eps; ) {
    double m = (l + r) / 2;
    if (check(m)) {
      ans = m;
      l = m;
    } else {
      r = m;
    }
  }
  cout << fixed << setprecision(10) << ans << '\n';
  return 0;
}

习惯孤独

我写的纯暴力。

vector 存图，暴力 dfs 模拟搞一搞，居然直接获得了 $55$ 的高分。

车站

输出 $- 1$ ， $0$ 分光荣的好成绩。

总结

总分： $100 + 95 + 55 + 0 = 250$ 。

T2 太不小心了，居然没写反着的情况（具体是写了但是没调用），下次一定要小心。T3 T4 因为硬性水平原因不会写，菜就多练。

Haokee Note

Explorer

2025.10.7 模拟赛

返乡

连接

习惯孤独

车站

总结

Graph View

Table of Contents