跳转至

250808 模拟赛

T2 beacon

数轴上有 \(n\) 个点，第 \(i\) 个点位于坐标 \(x_i\)（\(x_i\in [1,10^6]\)）。你可以在第一秒初点亮一个点，然后在每一秒末，每个已经点亮的点点亮所有距离它不超过 \(k\) 的点（被点亮的点不会在一轮内点亮其它点）。请你对每个 \(k\)（\(k\in [1,10^6]\)）算出，最少需要多长时间可以点亮所有节点。

\(n\le 10^6\)

首先猜测和调和级数有关。注意到扩展两次移动的距离一定大于 \(k\)，因此确实是一个调和级数。依次处理每个 \(k\) 然后暴力扩展，扩展次数为 \(O(n\log n)\) 级别。

考虑如何快速扩展。注意到值域不大，只需预处理每个位置左侧和右侧最近的点即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
const int V = 1e6;

int n, q, mxd;
int x[N], lp[N], rp[N];

int ans[N];

int main() {

    freopen("beacon.in", "r", stdin);
    freopen("beacon.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 2; i <= n; i++) mxd = max(mxd, x[i] - x[i - 1]);

    for(int i = 1; i <= V; i++) rp[i] = n + 1;
    for(int i = 1; i <= n; i++) lp[x[i]] = rp[x[i]] = i;
    for(int i = 2; i <= V; i++) lp[i] = max(lp[i - 1], lp[i]);
    for(int i = V - 1; i >= 1; i--) rp[i] = min(rp[i + 1], rp[i]);

    if(n == 1) {

        throw;
        int k;
        while(q--) cin >> k, cout << "1 ";
        cout << '\n';
        return 0;
    }

    for(int k = mxd; k <= V; k++) {
        if(x[n] - x[1] <= k) { ans[k] = 1; continue; }
        int cl = 1, cr = n;
        ans[k] = 0;
        while(1) {
            cl = lp[x[cl] + k];
            cr = rp[x[cr] - k];
            ++ans[k];
            if(cl >= cr) break;
        }
    }

    while(q--) {
        int k;
        cin >> k;
        if(k < mxd) { cout << "-1 "; continue; }
        cout << ans[k] << ' ';            
    }
    cout << '\n';

    return 0;
}

T3 wizard

给定两组整数区间 \([l_1,r_1],[l_2,r_2],\cdots[l_n,r_n]\) 和 \([l'_1,r'_1],[l'_2,r'_2],\cdots[l'_n,r'_n]\)；保证 \(l_i,r_i,l'_i,r'_i\) 分别严格单调递增；区间长度至少为 \(1\)。

考虑一个实数序列 \(b\)，满足 \(b_i\in [l_i,r_i]\) 且 \(b\) 单调递增。现在 \(b\) 在所有的合法序列中均匀随机选择一个，问满足 \(\forall i,\ b_i\in [l'_i,r'_i]\) 的概率是多少。答案对 \(10^9+7\) 取模。

\(n\le 500,~l_i,r_i,l'_i,r'_i\le 10^9\)

将每个 \([l'_i,r'_i]\gets [l'_i,r'_i]\cap [l_i,r_i]\)，在离散意义上，我们只需求出 \(b\) 分布于 \([l',r']\) 的方案数以及 \(b\) 分布在 \([l,r]\) 的方案数，两者之比即是概率。在连续意义上，方案数可以表示为 \(\prod db_i\) 的积分。

考虑拆贡献，先将所有区间端点离散化，然后对于每一段小区间，枚举落在其中的 \(b_i\) 数量。发现对于每一段都是独立的，贡献为 \(\frac{1}{n!}len^n\)，因此对于一种分布方案，容易计算其贡献。

考虑对小区间进行 dp，设 \(f_{i,j}\) 表示前 \(i\) 个小区间包含了 \(b_{1\sim j}\)，对应 \(\prod_{k=1}^j db_k\) 的值。发现容易实现转移，复杂度是 \(O(n^3)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 510;
const int MOD = 1e9 + 7;

inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

inline int get_inv(int a) { return qpow(a, MOD - 2); }

int inv[2 * N], ifact[2 * N];

int n, ans;
int l[N], r[N];
int l1[2 * N], r1[2 * N];

int num[2 * N], nn;
int pw[2 * N];
int f[2 * N][2 * N];

int calc() {
    for(int i = 0; i < 2 * N; i++) {
        for(int j = 0; j < 2 * N; j++) {
            f[i][j] = 0;
        }
    }
    nn = 0;
    f[1][0] = 1;
    pw[0] = 1;
    for(int i = 1; i <= n; i++) num[++nn] = l[i];
    for(int i = 1; i <= n; i++) num[++nn] = r[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 2; i <= nn; i++) {
        int l0 = num[i - 1], r0 = num[i];
        r1[i] = upper_bound(l + 1, l + 1 + n, l0) - l - 1;
        l1[i] = upper_bound(r + 1, r + 1 + n, r0) - r - 1;
    }
    for(int i = 2; i <= nn; i++) {
        pw[1] = num[i] - num[i - 1];
        for(int k = 2; k <= nn; k++) pw[k] = pw[k - 1] * pw[1] % MOD;
        for(int j = l1[i]; j <= r1[i]; j++) {
            for(int k = l1[i - 1]; k <= r1[i - 1] && k <= j; k++) {
                f[i][j] = (f[i][j] + f[i - 1][k] * pw[j - k] % MOD * ifact[j - k] % MOD) % MOD;
            }
        }
    }
    // cout << f[nn][n] << '\n';
    return f[nn][n];
}

int d;
int a[N], fl[N], fr[N];

signed main() {

    freopen("wizard.in", "r", stdin);
    freopen("wizard.out", "w", stdout);

    inv[1] = ifact[0] = 1;
    for(int i = 2; i < 2 * N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < 2 * N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    cin >> n >> d;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> fl[i] >> fr[i];

    for(int i = 1; i <= n; i++) l[i] = fl[i];
    for(int i = 1; i <= n; i++) r[i] = fr[i];

    ans = calc();

    for(int i = 1; i <= n; i++) l[i] = max(fl[i], a[i] - d);
    for(int i = 1; i <= n; i++) r[i] = min(fr[i], a[i] + d);

    ans = calc() * get_inv(ans) % MOD;

    cout << ans << '\n';

    return 0;
}

T4 rider

咕咕咕

err-tag