2024/10/16 模拟赛总结

\(30+0+40+40=100\)，T4 没看到输入不按顺序痛失 \(35\) pts

#A. 最终测试

很少见到不要 dp 的期望了

直接枚举每一个人的四种情况，二分查找有多少种情况有多少人分比他高，最后除以 \(16\) 即可

• \(16\) 是两个人的所有情况，即 \(4\times 4\)

  // BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using DB = double;

const int kMaxN = 1e5 + 5;

int n, a, b, f[kMaxN << 2], g[kMaxN][4], cnt;

int main() {
  freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a >> b, g[i][0] = f[4 * (i - 1) + 1] = 0, g[i][1] = f[4 * (i - 1) + 2] = min(a, b), g[i][2] = f[4 * (i - 1) + 3] = max(a, b), g[i][3] = f[i << 2] = a + b;
  }
  sort(f + 1, f + (n << 2) + 1);
  for (int i = 1; i <= n; i++, cnt = 0) {
    for (int j = 0; j <= 3; j++) {
      cnt += (n << 2) - (upper_bound(f + 1, f + (n << 2) + 1, g[i][j]) - f - 1);
    }
    for (int j = 0; j < 3; j++) {
      for (int k = j + 1; k <= 3; k++) {
        cnt -= g[i][k] > g[i][j];
      }
    }
    cout << fixed << setprecision(7) << 1.0 + cnt / 16.0 << '\n';
  }
  return 0;
}

#B. 空间跳跃

考虑正难则反，后两种操作即为 \(x\to \frac{x}{2},x\to 3x+1\)，由于答案要为 \(1\)，那么尽量多用第二种操作，因为它可以让数的绝对值更小

那么这道题就变成了扩展版冰雹猜想了

对于正数，直接跑冰雹猜想即可；对于负数可以先用冰雹猜想让其的绝对值较小，用第一种操作使其变成正数再使用冰雹猜想

事实证明并不会超过 \(1500\) 次

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1.5e3 + 5;

LL q, l, d, x, k, a[kMaxN];
vector<int> ans;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("jump.in", "r", stdin), freopen("jump.out", "w", stdout);
  for (cin >> q >> d >> l; q; q--, ans.clear()) {
    for ( cin >> x, ans.push_back(x); x && ~x && x != 1 && x != -5 && x != -17; ans.push_back(x)) {
      x % 2 == 0 ? x >>= 1 : (x *= 3) += 1;
    }
    for (; x <= 0; x += d, ans.push_back(x)) {
    }
    for (; x - 1; ans.push_back(x)) {
      x % 2 == 0 ? x >>= 1 : (x *= 3) += 1;
    }
    cout << ans.size() - 1 << ' ', reverse(ans.begin(), ans.end());
    for (int f : ans) {
      cout << f << ' ';
    }
    cout << '\n';
  }
  return 0;
}

#C. 快速访问

懒得写树剖，拿 \(40\) 分跑路

#D. 门童

懒得写李超线段树，拿 \(75\) 分跑路

我立正了