随机

Posted on Edited on In

题目大意：给定一个长度为 𝑛 的序列，你会在 [1,𝑛] 范围内随机两个正整数 𝑙, 𝑟 ，然后若有 𝑙 > 𝑟 ，则交换 𝑙, 𝑟 。你想要知道区间 [𝑙, 𝑟] 内不同元素个数的期望。

暴力很好想 也很好写

但是\(n^2\)终究过不去，正解就是对暴力的优化

考虑枚举每一个i作为重点的贡献

或者说，以i为分界点，i之前的为L，i之后的一段为R，这都是i产生的贡献

至于为什么\(nex[i]-i\)但是不用加1？

因为nex[i]数组表示的是i这个位置之后第一个再次出现i的位置

如果加1的话，就会多算一个数字

又因为区间可以反过来再算一遍，所以要乘以2

减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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 66;

inline int read()
{
    int s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

int n;
int pos[N], nex[N], a[N];

signed main()
{
    int i, ret (0);
    n = read();
    for (i = 1; i <= n; ++ i) a[i] = read();

    for (i = 0; i <= N; ++ i) pos[i] = n + 1, nex[i] = n + 1;
    for (i = n; i >= 1; -- i)
    {
    if (pos[a[i]] == n + 1) pos[a[i]] = i;
    else nex[i] = pos[a[i]], pos[a[i]] = i;
    }

    for (i = 1; i <= n; ++ i) ret += i * (nex[i] - i);

    ret = ret * 2; ret -= n;

    printf ("%.3lf", 1.0 / (n * n) * ret);
    return 0;
}