2019 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.

题意：给定一个初始全为 $0$ 的矩阵，最多可以将其中两个子矩阵的值反转，给定矩阵长宽，问反转后的矩阵有多少种不同的形态。

题解：std：找规律。反转一次的答案+反转两次的答案-重复图形的个数，其中可能会出现重复的图形的形态一共有四种，枚举算系数即可。

野鸡做法：定义答案矩阵 $ans[n][m]$ 为长为 $n$，宽为 $m$ 时的答案，暴力求出 $10 \times 10$ 的答案矩阵，横向纵向分别求 $5$ 次差分，原本 $10 \times 10$ 的矩阵变成了只有左上角 $5 \times 5$，其他位置都是 $0$ 的矩阵。猜测这个无限大的答案矩阵在差分后也只有左上角 $5 \times 5$ 的部分，用这个 $5 \times 5$ 的矩阵 $O(5 \times 5 \times 10)$ 还原出答案矩阵每一位的值。

交上去，一发 A 了，那就是猜对了。

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

Upsolved by Kilo_5723.

题意：给定两个横截面为凸多边形的无限高的柱体，一个横着放一个竖着放，求体积交。

题解：沿着十字面切可以将这个柱体切成 $O(n)$ 个棱台，计算出每个棱台的体积求和。

Problem K

Upsolved by Xiejiadong.

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

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

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

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

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