实习►笔试

阿里笔试

阿里笔试

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

第一题

有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());
}