Sun Yat-sen University Programming Contest

Problem A

Solved by Kilo_5723. 03:48:17 (+1)

题意：已知 $b_i=<\min,\max> (<a_x, b_j> , <a_y, b_k>)$ $(1 \le x,y \le n,1 \le j,k < i)$（$<a, b>$ 代表 $a,b$ 中任意一个都合法），如果 {$a_i$} 是 $1$ ～ $n$ 的随机一个全排列，求 $b_m \times n!$ 的数学期望值。

题解：题目的数据范围允许我们对于所有长度为 $n$ 的 $0,1$ 序列计算出 $b_m$ 的值。

显然，$b_m$ 一定等于 $a_1$ ~ $a_n$ 中的某个值。我们考虑 $b_m=k$ 的情况。

将所有 $a_i \ge k$ 设为 $1$, $a_i<k$ 设为 $0$，那么每个 $k-1$ 个 $0$, $n-k+1$ 个 $1$ 的序列对应着 $num(k)=(k-1)! \times (n-k-1)!$ 个 $1$ ～ $n$ 的全排列。对这个 $0,1$ 序列算出 $b_m$。如果 $b_m=0$，则 $b_m$ 的值不可能为 $k$。但是如果 $b_m=1$，我们也不能确定 $b_m=k$，只能判断 $b_m \ge k$。

但是，这 $num(k)$ 个全排列对应的 $b_m$ 值也一定大于 $k-1$。因此，如果我们假设 $num(k-1)$ 个全排列对应的 $b_m$ 值全是 $k-1$，我们相当于从 $num(k-1)$ 中找出了 $num(k)$ 个全排列，每个全排列的 $b_m$ 值都比假设多 $1$。

因此，只需要对所有长度为 $n$ 的 $0,1$ 序列计算出 $b_m$ 的值，如果 $b_m=1$，则 $ans+=cntbit(0)! \times cntbit(1)!$ 即可。

Problem B

Solved by Kilo_5723. 00:17:23 (+2)

题意：判断给出的一些长度能否构成三角形。

题解：当发现数量很多的时候一定是可以构成三角形的就赢了。

Problem C

Upsolved by Kilo_5723.

Problem D

Solved by Xiejiadong. 01:49:36 (+5)

题意：给出一些矩形覆盖平面，询问一个矩形区域，问是否已经被覆盖。

题解：二维平面差分。对于矩形\((a,b,c,d)\)，在位置\((a,b)\; +1\)、\((a,d+1)\; -1\)、\((c+1,b)\; -1\)、\((c+1,d+1)\; +1\)，进行一次前缀和，就能得到所有矩阵位置被覆盖的次数。

对于所有满足\(\ge 1\)的位置，即已经被覆盖的位置，改成\(1\)，其余为\(0\)，再进行一次前缀和即可支持子矩阵和查询。

对于每一个询问，只需要询问矩阵面积和子矩阵的面积相等即可。

又没看到多组数据， wa 爆了。

Problem E

Solved by Xiejiadong. 00:49:50 (+4)

不温暖的签到。

需要枚举 std 的输出格式，行末有空格，且没有换行。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 00:30:19 (+)

Problem I

Solved by Xiejiadong. 00:15:07 (+2)

温暖的签到。

没看到多组数据， wa 爆了。

Problem J

Unsolved.

Problem K

Upsolved by Xiejiadong.

题意：每次选择一个区间$[l,r]$，里面的人会两两认识，询问每次选择区间里面新增的认识的人。

题解：我们用线段树上的结点表示每一个位置认识的人的情况。

一个人认识的人一定是一个连续的区间，所以我们用$f_i$表示这个人认识的左边界，也就是这个人认识的人的区间是$[f_i,j]$。

这样一来，每次我们将区间$[l,r]$中所有$>l$的位置全部变成$l$，表示这些人认识的人至少已经拓展到了$l$，将修改前的区间和减去修改后的区间和就是这个区间新增的认识人的数量。

这部分操作用 Segment Beats 维护就好了。