题目：[[2024.10.16 题目]]
## 最终测试
$n$ 名选手正在参加比赛，第 $i$ 名选手作答了两道题，分值为 $a_{i,1}$ 与 $a_{i,2}$，每道题有 $50\%$ 的正确概率，求每个选手最终排名的期望，误差不超过 $10^{-6}$。选手的排名定义为比他分数高的人数 $+1$ 的值。
---
本题 $1\le n\le 1\times 5$，很显然出题人想要我们使用 $\mathcal O(n)$ 或 $\mathcal O(n\log_2 n)$ 解法。每个人有两道题，每道题有两种可能的状态，因此不难想到将一个人拆成四份（即四种不同的总分），这个人的期望就是每一份的期望的平均值。
接下来考虑怎么求每一份的期望。既然别人也可以有四份，那么我们就把别人的四份总分 $x$ 对应在数轴上的点计数器 $+1$，然后大于每一份的值的点的数量就是排名的总和，除以 $4$ 得到每一份的期望。然后再除以 $4$ 即可得到每个人的期望。由于第一名排名为 $1$，因此答案需要额外 $+1$。
该算法的时间复杂度为 $\mathcal O(n^2)$。不难想到使用树状数组来维护数轴上的点的数量（连离散化都不需要），先把每个人的每一份都加进去，然后对于每一个人 $i$ 将 $i$ 的 $4$ 份从树状数组中删除，再根据上面的过程模拟即可。时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <fstream>
#include <iomanip>
using namespace std;
using LL = long long;
const LL kMaxN = 1e5 + 5;
ifstream cin("test.in");
ofstream cout("test.out");
LL a[kMaxN][3], t[kMaxN], n;
void modify(LL x, LL y) {
for (x++; x <= 1e5; x += x & -x) {
t[x] += y;
}
}
LL query(LL x) {
LL res = 0;
for (x++; x; x -= x & -x) {
res += t[x];
}
return res;
}
LL get(LL x) {
return query(1e5) - query(x);
}
void fuck(LL a, LL b, LL v) {
modify(0, v);
modify(a, v);
modify(b, v);
modify(a + b, v);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (LL i = 1; i <= n; i++) {
cin >> a[i][1] >> a[i][2];
fuck(a[i][1], a[i][2], 1);
}
for (LL i = 1; i <= n; i++) {
fuck(a[i][1], a[i][2], -1);
cout << fixed << setprecision(6) << (get(0) + get(a[i][1]) + get(a[i][2]) + get(a[i][1] + a[i][2])) / 16.0 << '\n';
fuck(a[i][1], a[i][2], 1);
}
return 0;
}
```
## 空间跳跃
给定正整数 $d,l$，初始有整数 $n=1$，可以做以下三种操作：
- 将 $n$ 改变为 $2\times n$；
- 若 $\min(|n|,|n-d|)\le l$，可以将 $n$ 改为 $n-d$；
- 若 $n\equiv 1\pmod 3$，则可以将 $n$ 改为 $\cfrac{n-1}{3}$。
$q$ 次询问，每次询问给出目的地 $x$，求变换方案使得 $n=1$ 最终能够变换为 $x$。输出方案，变换次数不能超过 $1500$ 次。
---
仔细观察操作 $1$ 和操作 $3$，不难发现它正好为冰雹猜想的翻转版本。（冰雹猜想：对于任意正整数 $n$，若 $n$ 为偶数则 $n\gets \cfrac{n}{2}$，否则 $n\gets 3\times n+1$。在有限次操作内，$n$ 最终变为 $1$）那么，对于任意 $x\ge 1$，我们直接使用冰雹猜想即可；对于 $x=0$，我们让 $x\gets 3\times x+1$ 也可以。
现在最大的问题就是如何使得一个负数 $x<0$ 快速变为非负整数，因为冰雹猜想并不能在负数下成立，会在某几个数字间不断循环。观察第二种操作，在看看数据范围，发现 $1\le l\le 10^3$，这就代表着我们只需要变换到 $x\ge -10^3$ 即可直接使用第二种操作将其变为非负整数。根据验证，任意 $0\le x\le 10^6$ 都可以在不超过五百次操作 $1$ 和操作 $3$ 下变为 $1$。此时，题目已经解出来了，但是我们来考虑下负数情况下冰雹猜想的性质。
根据模拟，可以发现 $x<0$ 时 $x$ 会在 $0,-1,-5,-17$ 中循环，这也是为什么大多数题解都对这几个数进行了特判，如果满足则循环使用第二种性质，但是似乎没有题解指出这么做的意义何在。
```cpp
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
ifstream cin("jump.in");
ofstream cout("jump.out");
LL q, d, l, x;
vector<LL> ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> q >> d >> l; q; q--) {
cin >> x;
ans.clear();
if (x < 1) {
// Shabi Bingbao Caixiang
while (x < -1e3) { // 亦可设置成其它较大负数，如 -114
ans.push_back(x);
x = x % 2 ? x * 3 + 1 : x / 2;
}
// Zhijie Jia
while (x < 1) {
ans.push_back(x);
x += d;
}
}
// Shabi Bingbao Caixiang
while (x != 1) {
ans.push_back(x);
x = x % 2 ? x * 3 + 1 : x / 2;
}
cout << ans.size() << ' ';
ans.push_back(x);
reverse(ans.begin(), ans.end());
for (LL i : ans) {
cout << i << ' ';
}
cout << '\n';
}
return 0;
}
```
## 快速访问
有 $n+1$ 个结点的树，结点编号为 $0,1,\cdots,n$，第 $i$ 条边连接 $u_i$ 与 $v_i$。求对于 $i$ ${} (1\le i\le n) {}$，$A_i=\sum\limits_{j=S_i}\operatorname{dis}(i,j)^2$ 的值，其中 ${} S_i=\{j\in\mathbb{Z}|\max(1,i-1)\le j<i\}\cup\{0\} {}$，$\operatorname{dis}(i,j)$ 为 $i$ 到 $j$ 的简单路径经过的边的数量。
---
采用暴力。通过 dfs 预处理+倍增方法快速求出任意两点的最近公共祖先，在配合题意模拟并计算满足条件的两点长度和。时间复杂度 $\mathcal O(n^2\log_2 n)$，可以通过 Tarjan 的离线算法达到 $\mathcal O(n^2)$。得到 $40$ 分。
## 门童
牛牛去当志愿者。大厅沙发和大门距离为 $L$ 个单位，牛牛在每秒可以做以下事：
- 站在门口不动，开心度每秒减少 $x_1$；
- 从门口走向沙发一个单位，开心度每秒减少 $x_2$；
- 从沙发走向门口一个单位，开心度每秒减少 $x_3$；
- 在沙发上摸鱼，开心度每秒增加 $x_4$。
有 $n$ 名选手需要牛牛接待，第 $i$ 名选手会在第 $t_i$ 秒到达大门，它的耐心值为 $p_i$，友善值为 $f_i$，牛牛必须要在任意时刻 $T$ $(t_i\le T\le t_i+p_i)$ 接待，接待瞬间完成，开心值会在接待的瞬间上升 $f_i\times(t_i+p_i+T)$。
牛牛在第 $0$ 秒站在门口，开心度为 $0$。求牛牛在工作完成的时刻，开心度可以达到的最大值。
---
没有完全看懂题目，代码都没有写，出题人我喜欢你。
**后记**：发现模拟牛牛一直在大门口可以得到 $75$ 分。天地人，你我他，数据人我\_\_\_你\_\_\_。
## 总结
- **排名**：$2$；
- **比赛分数**：$240/400$；
- **情况**：相比 [[2024.10.14 模拟赛]]，较好；
- **问题**：容易红温。