## 返乡
#找规律 #数学 #三维偏序
首先观察 ${} 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\le a_2,b_1\le b_2$，而 $c_1=S-a_1-b_1$，$c_2=S-a_2-b_2$，所以有 $c_1\ge c_2$。
1. $c_1\ne c_2$，则有 $c_1>c_2$，不满足偏序条件；
2. $c_1=c_2$，那么 $a_1\ne a_2$ 或 $b_1\ne b_2$，则有 $a_1+b_1<a_2+b_2$，所以 $c_1>c_2$，不满足偏序条件。
综上不存在这种二元组，证明就成功了。
那么如何证明这种构造方案是最优的呢？我只会感性证明。
- [n] 如果现在前两维已经固定了，你需要选择第三维，那么第三维最多只能选一个，而我们选择 $c=S-a-b$ 是一定可以满足条件的，所以就选这个了。
现在我们需要找到最优的 $S$，可以通过简单 $\mathcal O(n^2)$ 或者 $\mathcal O(n^3)$ 找到，但是可以直接令 $S\gets\left\lfloor\cfrac{3n}{2}\right\rfloor$。
为什么这个最优呢？根据儒家思想当中的“中庸”不难想到，$S$ 为一个中间值的时候最佳，而 $a+b+c$ 的最大值为 $3n$，这就提示我们取 $3n$ 的一半是最优的，证明不会。
所以我们只需要 $\mathcal O(n^2)$ 枚举前两个再算出第三个即可。
```cpp
#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$ 块的左边作为左端点的答案。右端点的话是有可能不在连接处上的，但是汇总而来一共只有两种情况不在连接处上。
1. 质量不够 $L$ 往后吞一些。
2. 质量超出 $R$ 了删掉末尾一段。
由于 $i$ 单调递增，质量均为正，所以可以维护双指针 $s,t$，表示对于 $L$ 而言可以吞掉 $i\sim s$ 的所有整块、对于 $R$ 而言可以吞掉 $i\sim t$ 的所有整块，那么补充的散块可以通过 $s+1$ 和 $t+1$ 得到。
另外所有的情况均是右端点也在连接处上的情况。
- [n] 如果右端点属于 $(s,t)$ 但是不在连接处上，若该端点的密度大于答案密度，那么可以把这一整块都吞掉更优；反之删掉这一块。总之都不会更劣。
然而求最大的加权平均值比较复杂，于是我们就可以想到实数二分。
若当前期望的答案为 $x$，设右端点为 $j$，总长为 $S=\sum\limits_{k=i}^j l_k$，那么有
$
\sum_{k=i}^j \cfrac{l_kp_k}{S}-x\ge 0
$
两端同乘 $S$ 得
$
\sum\limits_{k=i}^j l_kp_k-\sum_{k=i}^j l_kx\ge 0\Leftrightarrow\sum_{k=i}^j l_k(p_k-x)\ge 0
$
可以先做前缀和，然后 ST 表维护区间最大值（也可以线段树、单调队列等），查询一下能否减成大于等于 $0$ 即可。
- [!] 注意一定要调用跑两遍的函数而非跑一遍，否则会和我一样挂 $95$ 分。
- [c] 数据太垃圾了。
时间复杂度 $\mathcal O(n\log_2 n\log_2 V)$，直接卡过。
```cpp
#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 因为硬性水平原因不会写，菜就多练。