2024.10.16 模拟赛

题目：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)$。

#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(\mathrm{mod}3)$，则可以将 $n$ 改为 $\frac{n-1}{3}$。

$q$ 次询问，每次询问给出目的地 $x$，求变换方案使得 $n=1$ 最终能够变换为 $x$。输出方案，变换次数不能超过 $1500$ 次。

---

仔细观察操作 $1$ 和操作 $3$，不难发现它正好为冰雹猜想的翻转版本。（冰雹猜想：对于任意正整数 $n$，若 $n$ 为偶数则 $n\leftarrow \frac{n}{2}$，否则 $n\leftarrow 3\times n+1$。在有限次操作内，$n$ 最终变为 $1$）那么，对于任意 $x\ge 1$，我们直接使用冰雹猜想即可；对于 $x=0$，我们让 $x\leftarrow 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$ 中循环，这也是为什么大多数题解都对这几个数进行了特判，如果满足则循环使用第二种性质，但是似乎没有题解指出这么做的意义何在。

#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 _{j=S_i}\mathrm{dis}(i,j{)}^2$ 的值，其中 $S_i=\{j\in \mathbb{Z}|\max (1,i-1)\le j<i\}\cup \{0\}$，$\mathrm{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 模拟赛，较好；
• 问题：容易红温。