nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

阿里笔试

感觉很难受,笛卡尔树没写出来,气死了,我咋这么菜

第一题

有n个羊圈,第i个羊圈初始有a[i]个羊,每天早上每个羊圈会增加k的羊,每天晚上主人会选出羊圈中羊最多的那个,卖掉一半,变为$\lfloor \frac{a[i]}{2}\rfloor$个羊,问m天后剩下多少只羊。

n,k,m,a[i]<1e5

每天增加本质是区间加法,寻找羊最多的是区间最值查询,减半是单点修改,第一想到线段树,但是这么敲也太莽撞了,然后发现区间修改为全区间修改,考虑到可以懒惰化,即增加一个值add用来表示全区间增大的情况。区间加法的时候让add+=k即可,查询的时候是最值查询,修改的时候注意$\lfloor \frac{a[i]+add}{2}-add\rfloor$,这样用一个多重集合维护即可

第二题

给一个长度为n的数组,任意选择一个子串,问最大值的期望, n<1e6
笛卡尔树的板子题,太丢人了,没做出来,考虑建一颗笛卡尔树,那么区间最值就是树根,树形dp维护子树大小,dfs统计答案。
代码祭天,下次一定分情况讨论,先写个暴力偏点分,不然笛卡尔树没搞好,暴力也没写太惨了。

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

int read() {
int x;
scanf("%d", &x);
return x;
}

const int N = 1e6 + 6;
int l[N], r[N], siz[N], a[N];
int n;
int s[N], top;

double dfs(int rt) {
if (rt == 0) return 0;
double ans = dfs(l[rt]) + dfs(r[rt]);
siz[rt] = siz[l[rt]] + siz[r[rt]] + 1;
double ls = siz[l[rt]] + 1;
double rs = siz[r[rt]] + 1;
ans += a[rt] * ls * rs / n / (n + 1) * 2;
return ans;
}

double f2() {
top = 0;
s[++top] = 1;
for (int i = 2; i <= n; i++) {
while(top&&a[s[top]]<=a[i]) l[i]=s[top--];
if(top) r[s[top]]=i;
s[++top]=i;
}
return dfs(s[1]);
}

double f1() {
static int mx[10005][10005];
for (int i = 1; i <= n; i++) {
mx[i][i] = a[i];
for (int j = i + 1; j <= n; j++) mx[i][j] = max(mx[i][j - 1], a[j]);
}
double ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
ans += mx[i][j];
}
}
return ans / n / (n + 1) * 2;
}

int main() {
while (true) {
n = 1e3;
for (int i = 0; i <= n + 10; i++)
a[i] = rand() % 10, l[i] = r[i] = siz[i] = 0;
double ans1 = f1();
double ans2 = f2();
printf("%.6f %.6f\n", ans1, ans2);
fflush(stdout);
assert(fabs(ans1-ans2)<1e-8);
}
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
printf("%.6f\n", f2());
printf("%.6f\n", f1());
}